Markov Chains

A Russian mathematician picked a fight with a theologian, and in the process invented the way we now model weather, web pages, language, and almost any process where the next step depends on the present one.

Most of probability theory begins with an assumption that is almost never true: that the events you are studying are independent of each other. Coin flips. Dice rolls. Card draws from a perfectly shuffled deck. The mathematics is clean because each trial forgets the one before. But the world rarely cooperates. Tomorrow's weather depends on today's. The next word in a sentence depends on the last. The price of a stock at noon depends on its price at 11:59. If you insist on independence, you have already left the interesting problems behind.

In 1906 a 50-year-old mathematician in St Petersburg, Andrey Markov, decided to find out what could still be said when independence was dropped. The answer changed how we model essentially everything.

A quarrel with theology

Markov's motivation was unusually personal. A rival mathematician, Pavel Nekrasov, had argued in print that the law of large numbers — the result that says averages of many independent random trials settle down to a stable mean — required independence as a precondition. From this Nekrasov drew a startlingly large conclusion: since human behaviour also exhibits statistical regularities (suicide rates, marriage rates, crime rates all converge year after year), human acts must therefore be independent of each other, and therefore must each be expressions of free will.

Markov, an atheist with a famously short temper, was unimpressed. He set out to prove that you do not need independence to get the law of large numbers. To do it cleanly, he invented a minimal model of dependent randomness: a sequence of states in which the probability of the next state depends only on the current state, not on the whole history that led to it.

That assumption — the future is independent of the past, given the present — is the Markov property. A process that satisfies it is a Markov chain. It is the smallest possible departure from independence: just enough memory to be interesting, just little enough to remain tractable.

“The future is independent of the past, given the present.”

States and transitions

The cleanest way to picture a Markov chain is as a small map of states, with arrows between them labelled by probabilities. From any state, the arrows leaving it must sum to one — something has to happen next.

Already, simple machinery falls out. If today is Sunny, what is the probability that the day after tomorrow is Rainy? You enumerate the paths — Sunny → Sunny → Rainy, Sunny → Cloudy → Rainy, Sunny → Rainy → Rainy — and add up the products of the probabilities along each path. Stacking the one-step probabilities into a square transition matrix turns this into a matrix multiplication. Multi-step questions become powers of the matrix. The whole subject is, in a sense, a single linear-algebra problem in disguise.

Where the chain settles

Run the chain long enough and an interesting thing happens. For most well-behaved chains, it forgets where it started. The fraction of time it spends in each state stops depending on the initial state and converges to a fixed distribution — the stationary distribution. It is the unique probability vector that the transition matrix leaves unchanged.

This is the deep content of Markov's argument against Nekrasov. The law of large numbers continues to hold for dependent processes, as long as they mix in the right sense. Free will is safe (or doomed) on quite different grounds.

The same skeleton, everywhere

What makes Markov chains feel almost suspiciously useful is that the same skeleton — states, transitions, a stationary distribution — describes processes that look, on the surface, to have nothing in common.

Google's original PageRank algorithm imagines a random surfer clicking links uniformly at random forever. The web is a directed graph; the surfer is a Markov chain on it; the stationary distribution gives the probability of being on any given page in the long run. Pages with high stationary probability are, by definition, the ones the rest of the web points at. PageRank is a Markov chain.

Markov chain Monte Carlo (MCMC) inverts the trick. If you want samples from a complicated probability distribution — one you cannot draw from directly — you design a Markov chain whose stationary distribution is the one you want, and then just run it. After a burn-in period, every step is an approximate sample. Bayesian statistics, statistical physics, and modern protein-structure inference all lean heavily on this single move.

The simplest language models are bigram Markov chains: the next word depends on the current one. Modern transformers break the strict Markov property by attending to longer histories, but the basic mental picture — a process moving through a state space according to learned transition probabilities — is still the right one to start from. Speech recognition, gene-finding, and the Viterbi algorithm in your cellphone's error-correction code are all built on hidden Markov models, which add one twist: you do not see the state directly, only a noisy signal it emits.

The reason this one idea reaches so far is structural. The Markov property is the mathematical statement of a memoryless world — or a world that can be re-described in enough detail that what remains is memoryless. That is almost the definition of a useful model. Markov did not set out to invent a tool. He set out to make a point about theology. What he left behind is the most quietly ubiquitous mathematical object of the twentieth century.