Markov Chains
“A Markov chain is memoryless motion — knowing 'where you are now' is all it takes to set what comes next.”
The formula
P(Xₙ₊₁ | X₀…Xₙ) = P(Xₙ₊₁ | Xₙ); πP = πHow to read it: Where you go next depends only on 'where you are now', not on the past path of how you got there
- Xₙ
- — The state (position) at step n
- P
- — Transition matrix — the table of probabilities of moving from each state to the next
- π
- — Stationary distribution — the long-run fraction of time spent in each state
The hook
You do not need the whole past to predict the future — a Markov chain is a memoryless world where knowing 'where you are now' is enough.
In plain words
It is a process that hops randomly among states, where the probability of the next state depends only on the current state and not at all on the path taken to get there. This 'memorylessness' is the Markov property.
The intuition
Think of a board-game piece — the next square is set by your current square and a die roll; how you arrived does not matter. A weather model is the classic case: knowing only 'today is sunny/rainy' fixes tomorrow's probabilities, and last week can be forgotten. Write the probability of going from each state to the next as a table (the transition matrix) and the whole system is specified.
How it's built
The key tool is the transition matrix P — each row is a 'current state', its entries are probabilities of moving to the next state, so each row sums to 1. Multiply the current distribution by P to get the distribution one step later. Repeat long enough and it settles into a stationary distribution π that no longer changes, found by solving πP = π.
Example
Weather: sunny→sunny 0.8, sunny→rainy 0.2, rainy→sunny 0.6, rainy→rainy 0.4, i.e. P=[[0.8,0.2],[0.6,0.4]]. For the stationary π=(s,r) with s+r=1 to satisfy πP=π: s=0.8s+0.6r → 0.2s=0.6r → s=3r. Combined with s+r=1: r=0.25, s=0.75. In the long run, 75% sunny days, 25% rainy.
Common mistake
'Memoryless' does not mean 'the past has no effect on the outcome' — the past is already summarized inside the current state. It is just that, once you know the present, the earlier details add no further information.
Where it's used
Google PageRank (web surfing as a Markov chain), speech and text prediction, credit-rating transitions in finance, gene-sequence analysis, state transitions in reinforcement learning — anywhere the next step is set probabilistically from the current state alone.
Where it came from
In 1906 Andrei Markov introduced it while probing whether the law of large numbers holds without independence. He analyzed the chain of letters in Russian poetry (Pushkin) as a concrete example.
Prerequisites
Quick check
In a Markov chain, what does the probability of the next state depend on?
- all past states visited
- only the current state✓
- only the initial starting state
- nothing at all
Practice
Today is sunny and P(sunny→rainy) = 0.3. In a Markov chain, what is the probability of rain tomorrow?
Answer: 0.3
- The next state depends only on the current state (today = sunny)
- The sunny→rainy probability is simply 0.3
Takeaway: A one-step prediction just reads off the transition probability from the current state.
For the transition matrix P=[[0.5,0.5],[0.5,0.5]], find the fraction of state A in the stationary distribution.
Answer: 0.5
- From any state the next is A 0.5, B 0.5
- By perfect symmetry the stationary distribution is (0.5, 0.5)
- Fraction of state A = 0.5
Takeaway: A symmetric transition matrix has a uniform stationary distribution — 0.5 each.
For P=[[0.8,0.2],[0.6,0.4]], find the long-run fraction s of state 1 (sunny) in the stationary distribution.
Answer: 0.75
- From πP=π: s = 0.8s + 0.6r
- 0.2s = 0.6r → s = 3r
- s + r = 1 → 3r + r = 1 → r = 0.25, s = 0.75
Takeaway: Solve the two equations together — πP=π and the total = 1 — to get the stationary distribution.
Explain in your notebook why 'a Markov chain is memoryless' is different from 'the past is meaningless'.
Answer: undefined
- The next probability is determined given only the current state (memorylessness)
- But the current state was itself produced by the past
- So the past is already baked into the summary called 'now' — given the present, earlier details are redundant
Takeaway: Memorylessness = 'the present is a sufficient summary of the past' — the past is not meaningless.