Part II · Markov Chains — dependence, and the math that predicts almost anything

One idea — the future depends on the present, and nothing before it — turns out to rank the web, simulate nuclear reactors, shuffle cards, and predict the next word you type. This chapter is the theory of that idea, from the feud that created it to the theorems that make it work. Its two companions put the theory to work: Monte Carlo & MCMC and PageRank.

1. The feud: a fight about free will that created a field

Markov chains were born from an argument. Around 1902, Pavel Nekrasov — a former seminarian leading the conservative, religious Moscow mathematical school — put probability to work in the free-will debate. His syllogism: voluntary human acts are like the independent events of probability theory; the law of large numbers applies only to independent events; social statistics (crime, marriage, harvest rates) do obey the law of large numbers; therefore human acts must be independent — evidence for free will. In short, Nekrasov claimed "stable long-run averages ⇒ independence."

Andrey Markov (1856–1922) — a student of Chebyshev, professor at secular, liberal St. Petersburg, and a combative atheist — read this as an abuse of mathematics. (In 1912 Markov requested his own excommunication from the Orthodox Church in solidarity with Tolstoy; in 1908 he refused a government order to spy on students.) He set out to destroy Nekrasov's premise by constructing sequences of dependent events that still obey the law of large numbers. Those sequences are what we now call Markov chains (papers from 1906 through 1912). The theological quarrel was the provocation; the theorem — the law of large numbers does not require independence — was the lasting result.

2. The law of large numbers, and Markov's crack in it

The law of large numbers (LLN) was first proved by Jacob Bernoulli in *Ars Conjectandi, published posthumously in *1713 — he called it his "golden theorem." Its weak*form: for independent trials with success probability \(p\), the empirical frequency \(S_n/n\) converges in probability to \(p\):

The strong law (Borel 1909; Kolmogorov, 1930s) strengthens this to almost-sure convergence, \(\Pr(\lim_n S_n/n = p)=1\). (The name "law of large numbers" is Poisson's, 1837.)

Every classical statement assumed independence. Markov's contribution was to prove the LLN survives dependence: for a suitable sequence of dependent variables — in particular a well-behaved Markov chain — the sample average \(\frac1n\sum_i X_i\) still converges, now to the chain's stationary mean. That single generalization is the mathematical rebuttal to Nekrasov: observing stable averages tells you nothing about whether the underlying events are independent.

3. Eugene Onegin: the first Markov chain fit to real data

To show dependence with stable averages in the wild, Markov reached for poetry. In an address to the St. Petersburg Academy on 23 January 1913 (Julian; = 5 February Gregorian), he took the first 20,000 letters of Pushkin's Eugene Onegin, discarded spaces and punctuation, and labelled each letter vowel (V) or consonant (C). Then, by hand, he counted single letters and consecutive pairs.

• 8,638 vowels / 11,362 consonants → \(P(V)\approx 0.43\), \(P(C)\approx 0.57\).
• Vowel-followed-by-vowel pairs: 1,104 observed, versus *,698 expected under

  independence — barely a third. Letters are strongly dependent*

The two-state transition matrix he estimated:

Its stationary distribution is ≈ 43% vowels / 57% consonants — matching the observed marginals. Dependent letters, stable long-run frequency: exactly the point. This is the first application of Markov chains to empirical data, and arguably the first statistical model of natural-language text — the direct ancestor of Shannon's information theory and n-gram language models (AI Compendium, ch. 35).

4. The formal object

A discrete-time Markov chain is a sequence of random variables \(X_0, X_1, X_2,\dots\) over a countable state space \(S\) (finite: \(S=\{1,\dots,N\}\)) satisfying the Markov / memoryless property:

The future depends on the past only through the present state.

Transition matrix. \(P=(p_{ij})\), \(p_{ij}=\Pr(X_{n+1}=j\mid X_n=i)\), is row-stochastic: \(p_{ij}\ge0\) and each row sums to 1. Time-homogeneous chains have a single \(P\) for all steps.

Chapman–Kolmogorov & \(n\) steps. The \(m\)-step probabilities compose: \(P^{(m+r)}=P^{(m)}P^{(r)}\), so the \(n\)-step transition matrix is just the matrix power \(P^n\). If \(\mu_0\) is the initial (row) distribution, the distribution after \(n\) steps is \(\mu_n = \mu_0 P^n\). Prediction is matrix multiplication.

Classifying states.

• Irreducible — every state reaches every other; one communicating class.
• Period \(d(i)=\gcd\{n\ge1: p_{ii}^{(n)}>0\}\); aperiodic if \(d(i)=1\).
• Recurrent — return is certain; transient — return probability \(<1\).
• Positive recurrent — recurrent with finite mean return time. (In a finite

  irreducible chain, every state is automatically positive recurrent.)

• Ergodic — aperiodic and positive recurrent. Finite + irreducible + aperiodic

  \(\Rightarrow\) ergodic.

5. Stationary distribution and the fundamental theorem

A probability vector \(\pi\) is stationary if it is unchanged by a step:

\(\pi\) is the left eigenvector of \(P\) with eigenvalue 1 — the chain's long-run equilibrium.

Perron–Frobenius guarantees it exists and is well-behaved: for a stochastic \(P\) every eigenvalue has \(|\lambda|\le1\) and \(\lambda=1\) is present. If \(P\) is irreducible, that eigenvalue is simple and its eigenvector \(\pi\) is unique and strictly positive. If also aperiodic, \(1\) is the only eigenvalue on the unit circle, which forces convergence.

The fundamental theorem of Markov chains (ergodic theorem). For a finite, irreducible, aperiodic chain:

1. a unique stationary distribution \(\pi\) exists, with \(\pi_i = 1/M_i\) (inverse

   mean return time);

2. it forgets where it started: \(\lim_{n\to\infty}p_{ij}^{(n)} = \pi_j\) for every

   \(i\) — every row of \(P^n\) converges to \(\pi\);

3. time-average = space-average (Markov's LLN for dependent variables):

   \(\frac1n\sum_{k=1}^n f(X_k) \to \sum_i \pi_i f(i)\) almost surely.

Point 3 is the whole story of this compendium's applications: run one long trajectory and average, and you recover an expectation under \(\pi\). Monte Carlo integration (ch. 02) is this theorem; PageRank (ch. 03) is the \(\pi\) of a web-sized chain.

How fast? The spectral gap. Convergence \(\|\mu_0 P^n - \pi\|\) decays like \(|\lambda_2|^n\), where \(\lambda_2\) is the second-largest eigenvalue modulus. A big gap (\(\lambda_2\) small) means fast mixing. (A periodic irreducible chain still has a unique \(\pi\), but \(P^n\) never settles — it cycles.)

6. Mixing time: how long until "random"?

To measure distance to equilibrium, use total-variation distance:

With \(d(t)=\max_x\|P^t(x,\cdot)-\pi\|_{\mathrm{TV}}\), the mixing time is \(t_{\mathrm{mix}}(\varepsilon)=\min\{t: d(t)\le\varepsilon\}\), conventionally at \(\varepsilon=\tfrac14\). Some chains display a cutoff phenomenon: \(d(t)\) stays near 1, then plunges to near 0 over a window negligible next to \(t_{\mathrm{mix}}\) — the approach to randomness is a sharp step, not a gentle fade. That is exactly what makes the next example famous.

7. Seven shuffles: the cutoff you can hold in your hands

How many riffle shuffles randomize a 52-card deck? David Bayer and Persi Diaconis answered it precisely in "Trailing the Dovetail Shuffle to its Lair" (*Annals of Applied Probability, 1992), modelling the riffle by the *Gilbert–Shannon–Reeds*process (cut binomially, interleave in proportion to packet sizes; \(k\) riffles compose into one \(2^k\)-shuffle). The total-variation distance from a perfectly shuffled deck:

The deck stays essentially unshuffled (TV ≈ 1) through four shuffles, collapses across five and six, and first drops below \(\tfrac12\) at seven — the textbook "seven riffle shuffles suffice," a cutoff you can see in the table. Asymptotically the mixing time obeys \(t_{\mathrm{mix}} \sim \tfrac32\log_2 n\) shuffles (for \(n=52\) that formula gives ≈8.5; the exact finite computation crosses \(\tfrac12\) at 7 — keep both, they answer slightly different questions).

The contrast makes the point: the clumsy overhand shuffle mixes in \(\Theta(n^2\log n)\) steps (Pemantle; Jonasson 2006) — on the order of thousands of overhand shuffles for a 52-card deck to reach what seven riffles achieve. Same deck, same goal; an \(O(\log n)\) method versus an \(O(n^2\log n)\) one. Choosing the right chain is everything.

8. Where the chain leads

The memoryless walk is a substrate, not a single algorithm. From here the compendium follows two of its most consequential uses:

• Monte Carlo & MCMC — design a chain whose

  stationary distribution is a target you want to sample, then let the ergodic theorem do the integration. The engine of statistical physics and Bayesian ML.

• PageRank — make the states web

  pages and the walk a random surfer; the stationary distribution is the ranking.

And in the AI Compendium, the same chain over text becomes the n-gram language model — the memoryless ancestor of the LLM. Where Markov chains struggle is exactly where memory matters: systems with long feedback loops (climate, with its compounding CO₂→temperature→water-vapor amplification) break the one-step assumption, which is why richer models exist. But the reach of the plain idea — future from present alone — is the reason it predicts almost anything.

Why it matters to the Stack

Ranking (Hub/kode-rag search), sampling (any probabilistic estimate in kdb or the AI layer), and sequence prediction all reduce to a Markov chain plus its stationary distribution. This chapter is the encyclopedic ground those decisions cite — one fact, one home (reference-vs-decision, per the main INDEX).

Sources

• Seneta, E. (2007). Markov and the Creation of Markov Chains.
• Hayes, B. (2013). First Links in the Markov Chain. American Scientist 101(2):92.
• Bernoulli, J. (1713). Ars Conjectandi; Seneta, E. (2013). A Tricentenary History of the Law of Large Numbers (arXiv:1309.6488).
• Markov, A. A. (1913). An Example of Statistical Investigation of the Text Eugene Onegin… (Eng. trans. Link, Science in Context, 2006).
• Levin, D., Peres, Y. & Wilmer, E. (2009). Markov Chains and Mixing Times, AMS.
• Bayer, D. & Diaconis, P. (1992). Trailing the Dovetail Shuffle to its Lair. Ann. Appl. Probab. 2(2):294–313.
• Jonasson, J. (2006). The overhand shuffle mixes in \(\Theta(n^2\log n)\) steps. Ann. Appl. Probab. (arXiv:math/0501401).