Markov chains
A random walk takes independent steps, so it has no memory at all. A Markov chain gives it just enough memory to be interesting: the next state may depend on where you are now, but never on how you got there. That one clause — the future depends on the present alone — is enough to specify an entire stochastic process with a matrix, and the matrix is something you can edit by hand. Once you can edit it, you can watch two things happen at once: a single token wandering between states, and the crowd of probabilities it obeys. The token looks random; the crowd is deterministic, and after enough steps it forgets where it started. That convergence is the engine behind PageRank, behind hidden Markov models, and behind the Monte Carlo methods in the rest of this volume.
The question
Randomness that remembers a little
Part 9 built the random walk: flip a coin, step left or right, repeat. Every step was independent of every other, which is why the walk stayed centred and why its distance from home grew like the square root of the number of steps. But most processes in the world are not like that. Tomorrow's weather is not independent of today's; the next word in a sentence is not independent of the words before it; the next page a web surfer visits is not independent of where she is now. Independence is a modelling convenience, and often the wrong one.
Markov chains relax independence in the smallest possible way. We allow the next outcome to depend on the current one — and only the current one. This is the Markov property: once you know the present state, the past adds nothing. A patient's diagnosis tomorrow depends on their diagnosis today, but not on the sequence of diagnoses that led here. A chess position summarises the game, so the next move depends on the position and not on the move order that produced it. When the state is chosen well, the extra history really is redundant, and the process collapses to a compact description.
That description is a table. If there are three possible states, the table is a 3×3 matrix P whose entry in row i, column j says how likely a move from i to j is. Every row is a probability distribution over the next state, so every row sums to one. The whole process — every possible trajectory, every long-run average — is encoded in those few numbers. Change one entry and you have changed the world.
The questions we want to answer are the natural ones. If a token hops according to P forever, does the fraction of time it spends in each state settle down? If so, what determines that long-run mix, and how fast does the settling happen? And what happens when the token cannot reach every state, or gets trapped cycling? Section 2 makes the mechanics precise, Section 3 finds the long-run mix as a fixed point, Section 4 asks how quickly it arrives, and Section 5 points the whole machine at the web.
The Markov property and the transition matrix
One matrix, every trajectory
Fix a finite set of states $\{1,\dots,N\}$ and let X_n be the state at time n. The process is a Markov chain when the probability of the next state depends on the current state and on nothing else. Written as a conditional probability, that is the whole definition.
The numbers P_{ij} are the transition probabilities and the matrix they form is the transition matrix. Row i lists where you can go from state i, and it is a distribution, hence the two constraints: entries are never negative, and every row sums to exactly one. A matrix with non-negative rows that sum to one is called row-stochastic, and any row-stochastic matrix is a legal Markov chain.
A subtle point that trips people up: P_{ij} is read "row i, column j", meaning from i to j. Probability flows across a row, not down a column. If you keep a distribution $\pi$ as a row vector, one step of the chain updates it by multiplying on the right: $\pi' = \pi P$. The j-th entry of $\pi'$ collects the probability of landing in j from every possible starting state, exactly the law of total probability applied one step ahead.
Two ingredients complete the specification: an initial distribution $\pi_0$ and the matrix P. Given both, the probability of any finite trajectory is a product of transition probabilities, and the distribution after n steps is $\pi_0 P^n$. Iterating the matrix is the same as running the process in distribution, and this is what the demo below does twice over — once as a real token taking random hops, and once as the exact distribution marching forward.
Edit the matrix by hand. Each entry is a probability; the page renormalises its row the instant it stops summing to one, so the chain stays legal no matter what you type. Below the heatmap, the bars are the empirical frequency of visits for the actual token, the hollow markers are the stationary distribution, and the tiny dots are the exact distribution after the current number of steps. Press play and watch the three converge.
Rows are the state you are in, columns the state you move to. The ringed row is the token's current state; darker cells are more likely transitions.
Bars: fraction of visits so far. Hollow markers: $\pi$. Small dots: the exact law after n steps from the start state.
The sticky preset makes each state hug itself, so the token stays put for long stretches; the well-mixed preset lets it roam, so visits spread out quickly. The cyclic preset is the interesting one: each state sends the token deterministically to the next, so the chain marches $A\to B\to C\to A$ forever. The empirical frequencies still average to a third each, and the fixed point is still uniform, but the exact distribution after n steps never settles — it orbits with period three. That gap between "the time average converges" and "the distribution converges" is exactly what Section 4 has to untangle.
Stationary distributions
The distribution that one step leaves unchanged
Watch the running frequencies long enough and they drift toward a fixed mix: the fraction of time in each state stops moving even though the token never stops moving. That limiting mix is the stationary distribution, the distribution $\pi$ that the chain maps to itself. One step must leave it unchanged, which gives a single clean equation.
Read the equation as a linear-algebra statement and it is familiar. A row vector fixed by P is a left eigenvector with eigenvalue one, the transpose of an ordinary eigenvector of $P^{\top}$. Every stochastic matrix has eigenvalue one — its rows sum to one, so the vector of all ones is a right eigenvector — and the Perron–Frobenius theorem guarantees a non-negative eigenvector for that eigenvalue. Turning it into a distribution is just a matter of dividing by its sum. So a stationary distribution always exists; the real questions are whether it is unique and whether a given chain actually reaches it. The linear algebra guide builds the eigenvector machinery this fixed-point equation depends on.
Uniqueness is a reachability question. Call the chain irreducible if every state can reach every other state in some number of steps. If some states form a closed club that can never be left, and another club is only reachable from outside, there is no reason for their long-run shares to be pinned down, and indeed the chain can have several stationary distributions, one per closed communicating class. Irreducibility kills that possibility: when the whole state space is one communicating class, the stationary distribution is unique.
There is a slick way to solve for $\pi$ that sidesteps the eigenvector computation. If the chain satisfies detailed balance, $\pi_i P_{ij} = \pi_j P_{ji}$ for every pair, then probability flowing from i to j is exactly matched by the reverse flow, and summing over i confirms $\pi=\pi P$ immediately. A chain that satisfies detailed balance is called reversible, and reversible chains are the ones MCMC is built on: in Part 11 we will design a chain whose stationary distribution is a posterior we want to sample, precisely by engineering detailed balance. Not every chain is reversible, but every irreducible chain has a unique stationary distribution whether or not it is.
One more observation that pays off everywhere. A stochastic matrix always has eigenvalue one; irreducibility makes it simple as an eigenvalue of the relevant block; but the other eigenvalues govern the transient. In the demo, switching between the sticky and well-mixed presets changes how quickly the exact dots slide onto the hollow stationary markers. That speed is a property of the whole spectrum, and Section 4 reads it off.
Convergence and mixing
Why the start stops mattering
Suppose the chain is irreducible and, to keep things tidy, aperiodic: it is not forced to return to particular states on a fixed cycle. Then the distribution after n steps converges to the stationary distribution from any starting point, i.e. every row of P^n converges to the same vector $\pi$. This is the convergence theorem, and it is what makes long runs forget their initial conditions.
The rate is set by the eigenvalues. Order them by modulus, $1=|\lambda_1|>|\lambda_2|\ge\cdots\ge|\lambda_N|$. The deviation from stationarity shrinks at each step by roughly the factor $|\lambda_2|$, the second largest eigenvalue modulus. If $|\lambda_2|$ is close to one — a nearly periodic or nearly disconnected chain — convergence is glacial; if it is small, the chain forgets almost immediately. The gap $1-|\lambda_2|$ is called the spectral gap, and it is the standard currency for how well a Markov chain mixes. The sticky preset is a chain with a large second eigenvalue: it crawls around the space because leaving a state is rare.
Periodicity is the failure mode that irreducibility alone does not cure. The cyclic preset is irreducible — from any state you can eventually reach any other — but the distribution after n steps cycles through three values forever, so P^n never converges. The time average still converges, and the stationary equation still has the unique solution $\pi=(1/3,1/3,1/3)$, but the distribution itself has no limit. Adding aperiodicity, for instance by letting the token occasionally stay put, breaks the cycle and restores convergence of P^n. The standard fix is a tiny self-loop, and it is exactly the trick PageRank uses in Section 5.
Mixings are measured, not just bounded. The total variation distance between the law at time n and $\pi$ is half the sum of the absolute differences of the probabilities, and the mixing time is the first n at which that distance drops below a tolerance from the worst start. When you run an MCMC sampler, the early iterations are this transient — the "burn-in" you throw away — and the reason burn-in exists is precisely that no chain starts in its stationary distribution. Everything in Part 11 rests on the guarantees built here: an irreducible, aperiodic chain is guaranteed to converge, and the spectral gap tells you roughly when.
A useful sanity check that the same machinery describes random walks. The simple symmetric walk on a finite line is an aperiodic, irreducible chain once we allow it to stay put, and its stationary distribution is uniform, because every state has the same number of neighbours to move to. The $\sqrt{n}$ spread from Part 9 is a statement about the transient; the uniform stationary distribution is a statement about the limit. Both live in the same matrix.
PageRank as a Markov chain
The web surfer who never gets bored
Imagine a surfer who sits on a web page and, at each click, picks one of the page's outgoing links uniformly at random. The page she is on is the state, and the links define the transition matrix. Her long-run distribution is the fraction of time she spends on each page, which is a sensible notion of importance: a page is important if a random walker keeps landing on it. That is the original insight behind PageRank, and it turns ranking into the stationary distribution of a Markov chain.
Two problems spoil the naive version. First, some pages have no outgoing links at all — dangling nodes. A surfer who reaches one has nowhere to go, so probability leaks out of the system and the matrix stops being stochastic; follow enough steps and the total mass quietly drains away. Second, the real web has pages and clusters that link only among themselves, trapping the surfer in a small closed region that would get all the rank. The fix handles both at once: with probability d the surfer follows a link, and with probability 1-d she teleports to a page chosen uniformly at random, including dangling pages, from which she then resumes following links.
Here N is the number of pages, $\mathbf{1}$ is the vector of all ones, and M is the link-following transition matrix, with dangling rows replaced by the uniform distribution so that M is genuinely row-stochastic. The damping factor d is usually set near 0.85; it is the marketing name for the probability of clicking a link rather than jumping. Teleportation makes the chain irreducible and aperiodic — from anywhere you can reach anywhere in one teleport, and you can always idle — so the convergence theorem applies and there is a unique ranking. The update above is exactly the power iteration of Section 4 with a little uniform mass mixed in at every step.
The demo builds this from a five-page link graph. Slide the damping factor and drag the toggle that disables the dangling-node fix: with it off, watch the total mass fall below one and the ranking distort, which is the leak made visible. The convergence plot on the right tracks each page's rank across iterations, so you can see the ordering settle before the numbers stop changing.
A directed link graph. Circle area grows with PageRank; dashed red means the page is dangling and the teleport fix is off.
Rank of each page against iteration. Every curve climbs or falls and then flattens onto its long-run value.
Two design choices deserve a second look. Teleporting with probability 1-d is not a hack bolted onto a clean model; it is what makes the chain a proper Markov chain with a unique stationary distribution, and the price is a slight flattening of the ranking, because every page gets the same uniform baseline of (1-d)/N before link quality is counted. Setting d to one removes that damping and with it the guarantee. And dangling pages are not a curiosity — on the real web they are everywhere, and the standard remedy is exactly the uniform jump used here. The same three objects — a stochastic matrix, a fixed-point equation, and a power iteration — will reappear in Part 11 as the proposal-and-accept machinery of Markov chain Monte Carlo.
Where this shows up
The hidden matrix behind the process
Sampling as a walk
A language model emits one token at a time, and each next-token distribution is conditioned on the tokens already generated. That is a chain over the vocabulary with an enormous, context-dependent transition matrix. The decode loop is the sampler stepping through it, and the temperature and top-p knobs are edits to the same transition probabilities this page lets you type by hand.
N-grams and smoothing
The classic statistical language model is an explicit Markov chain: the state is the last few words, and the transition matrix is a table of next-word counts. In language modelling the sparsity of that table is the whole problem, and the smoothing tricks that fill in unseen transitions are the ancestors of the neural models that replaced them.
Fixed points as eigenvectors
The equation $\pi=\pi P$ says the stationary distribution is a left eigenvector with eigenvalue one, and the mixing rate is governed by the second eigenvalue. The linear algebra guide develops the spectral tools — Perron–Frobenius, the eigenvalue ordering, the gap — that this convergence claim quietly relies on.
Accept and reject
A draft model proposes several tokens and the target model accepts or rejects each one. Whether a proposal survives is a random event whose chance depends on how far along the draft has gone, and the walk of accepted prefixes is a small Markov chain. Speculative decoding is the speed-up that falls out of analysing it.
Cheat sheet
Every formula in one place
| Idea | Formula | Reading |
|---|---|---|
| Markov property | $P(X_{n+1}\mid X_n,\dots,X_0)=P(X_{n+1}\mid X_n)$ | The present already contains the whole relevant past. |
| Transition probability | $P_{ij}=P(X_{n+1}=j\mid X_n=i)$ | Row i, column j: from i to j. |
| Stochastic rows | $P_{ij}\ge 0,\;\sum_j P_{ij}=1$ | Each row is a distribution over the next state. |
| Distribution update | $\pi_{n+1}=\pi_n P$, so $\pi_n=\pi_0 P^n$ | Multiply on the right by the transition matrix. |
| Stationary distribution | $\pi=\pi P,\;\sum_i \pi_i=1$ | Left eigenvector for eigenvalue one; the long-run time shares. |
| Convergence | $\pi_0 P^n\to\pi$ if irreducible and aperiodic | Starts stop mattering in the limit. |
| Mixing rate | factor $|\lambda_2|$, gap $1-|\lambda_2|$ | Second eigenvalue sets how fast forgetting happens. |
| Detailed balance | $\pi_i P_{ij}=\pi_j P_{ji}$ | Reversible chain; the design target for MCMC. |
| PageRank | $\pi=\frac{1-d}{N}\mathbf{1}+d\,\pi M$ | Follow a link with prob. d, teleport otherwise. |
Further reading
Where to go deeper
- J. R. Norris, Markov Chains, Cambridge University Press, 1997 — the rigorous backbone: irreducibility, recurrence and convergence, written with unusual clarity.
- David A. Levin, Yuval Peres and Elizabeth L. Wilmer, Markov Chains and Mixing Times, AMS, 2009 — everything about how fast chains converge, the spectral gap and coupling arguments.
- Lawrence Page, Sergey Brin, Rajeev Motwani and Terry Winograd, "The PageRank Citation Ranking", Stanford, 1999 — the original paper, where the random surfer and the damping factor are introduced.
- John G. Kemeny and J. Laurie Snell, Finite Markov Chains, 1960 — the classical treatment of stationary distributions and absorbing chains.
- Grant Sanderson, "Markov chains", 3Blue1Brown — the visual intuition for state distributions flowing to a fixed point.