Markov Chains
A system that forgets everything except where it is now. Start it anywhere and it settles in the same place.
Overview
The property
A process is Markov when the next state depends only on the current state, not on the path that led there. The present screens off the past.
That is a strong assumption and a liberating one. Instead of a history of arbitrary length you carry one thing — where you are — and everything about the future follows from it.
Markov Chains
Worth knowing
Markov Chains
Memoryless processes, the distribution they settle into, and why so many algorithms are one.
The transition matrix
Collect the probabilities into a matrix P, where P[i][j] is the chance of moving from state i to state j. Every row sums to 1, because from any state you go somewhere, possibly back to where you were.
If the current distribution over states is a row vector d, then after one step it is d P. After k steps, d P^k. That is all the arithmetic there is, and the visualisation is doing exactly it, forty steps at a time.
Convergence
Watch the three curves. They start apart — all the probability on one state — and within a few steps they flatten out and stop moving. The readout shows the last step changing things by around 10⁻¹⁰.
Now change the starting state. The curves begin somewhere completely different and arrive at the same values.
That limit is the stationary distribution: the pi with pi P = pi. Read as an eigenvector problem, it is the left eigenvector of P with eigenvalue 1, and the [eigenvalue module](eigenvalues_and_eigenvectors.html) is the same mathematics in another costume.
The convergence is not automatic. It needs the chain to be irreducible — every state reachable from every other — and aperiodic, not trapped in a fixed cycle. Drag a transition probability to its minimum and convergence slows visibly; a chain that could not leave a state at all would never mix.
The speed is governed by the second-largest eigenvalue: the closer it is to 1, the slower the mixing. That number has a name, the *spectral gap*, and it is what people mean by a chain mixing slowly.
The whole thing on two states
Everything above fits on a chain with two states, small enough to do on paper and still large enough to show all three claims.
Weather, where a sunny day is usually followed by another and rain clears half the time:
| from \ to | sunny | rainy |
|---|---|---|
| sunny | 0.9 | 0.1 |
| rainy | 0.5 | 0.5 |
The stationary distribution, solved exactly. πP = π on two states is just πs = 0.9πs + 0.5πr, which rearranges to 0.1πs = 0.5πr, so πs = 5πr. With the two summing to 1 that gives π = (5/6, 1/6), or (0.8333, 0.1667). No iteration, no eigenvalue routine — two lines of algebra.
The same answer by iterating. Start with certainty and multiply by P repeatedly:
| step | from sunny | from rainy |
|---|---|---|
| 0 | (1.000, 0.000) | (0.000, 1.000) |
| 1 | (0.900, 0.100) | (0.500, 0.500) |
| 2 | (0.860, 0.140) | (0.700, 0.300) |
| 3 | (0.844, 0.156) | (0.780, 0.220) |
| 4 | (0.838, 0.162) | (0.812, 0.188) |
| 5 | (0.835, 0.165) | (0.825, 0.175) |
Two starting points that could not be further apart, converging on the same (0.8333, 0.1667). The chain forgets where it began, which is the whole content of the claim that the limit does not depend on the start.
And the mixing speed, which is not a metaphor. The eigenvalues of a 2×2 stochastic matrix are 1 and (trace − 1), so here the second eigenvalue is 0.9 + 0.5 − 1 = 0.4. Now measure how far the sunny column is from 0.8333 at each step:
0.1667, 0.0667, 0.0267, 0.0107, 0.0043, 0.0017
Each is exactly 0.4 times the one before it. The second eigenvalue is not merely *related* to the mixing rate; it is the factor by which the remaining error shrinks per step. A chain with a second eigenvalue of 0.99 needs 365 steps to shrink the error as far as this one does in four, which is why the spectral gap is the number MCMC practitioners worry about.
One more reading falls out of π for free, and it is the one that makes the numbers concrete. The expected time to return to a state is 1 / πi, so rain recurs every 1 / (1/6) = 6 days on average and sun every 1 / (5/6) = 1.2 days. The stationary distribution is not only the long-run share of time spent in each state; it is the reciprocal of how long you wait to come back to it.
Where they appear
PageRank is the stationary distribution of a random surfer following links. The damping factor exists to make the chain irreducible, so a page with no outbound links cannot swallow all the probability.
MCMC — Metropolis-Hastings, Gibbs sampling, Hamiltonian Monte Carlo — runs the idea backwards: construct a chain whose stationary distribution *is* the posterior you want, run it, and treat the states it visits as samples. Nearly all Bayesian computation is this.
Hidden Markov models put a Markov chain behind observations you can see, and were the backbone of speech recognition for decades.
Reinforcement learning. A Markov decision process is a Markov chain with actions and rewards attached. The "Markov" in MDP is this property, and it is what makes value functions of the state alone sufficient.
n-gram language models are Markov chains over words — and their limitation is precisely the property: a bigram model cannot remember anything beyond the previous word, which is why long-range coherence needed something else.
Where it goes wrong
Assuming the property holds. Most real processes have memory. Widening the state to include recent history restores the property at the cost of a much larger state space.
Assuming convergence. Check irreducibility and aperiodicity.
Stopping an MCMC run too early. Samples before the chain has mixed reflect where you started, which is what burn-in discards and why convergence diagnostics exist.
Confusing the stationary distribution with the most likely state. It is the long-run fraction of time spent in each state, not a prediction of where the chain is now.
Walk the chain to its steady state
A three-state weather chain, stepped forward until the distribution stops moving, then checked against the eigenvector that predicts it.
Check yourself
0 of …Answer without scrolling back up.
What does the Markov property say?
What is the stationary distribution?
What does MCMC do with this idea?
Markov Chains
A process is Markov when the next state depends only on the current state, not on the path that led there. The present screens off the past.