Markov Chains, Stationarity, and Stochastic Processes

These properties answer different questions about long-run behavior, and only one of them carries a number. Irreducibility and aperiodicity decide whether a chain converges at all. The modulus of the second eigenvalue decides how fast. For the best-known chain in the world, that modulus has been computed exactly.

The Google matrix is A = [cP + (1-c)E]^T. Haveliwala and Kamvar proved in 2003 that its second eigenvalue satisfies |lambda2| <= c, and that it equals c exactly whenever P has at least two irreducible closed subsets. The web hyperlink matrix has them. Their paper states the consequence: “For PageRank, the typical value of c has been given as 0.85; for this value of c, Theorem 2 thus implies that the convergence rate of the power method |λ2/λ1| for any web link matrix A is 0.85.”

The rate is 0.85 however large the web grows. Adding pages does not slow the arithmetic down.

Bryan and Leise reproduced the bound independently in 2006, in the form |lambda2| <= 1 - m, and watched it happen on a five-page example web. The error ratio ||M^k x0 - q||/||M^(k-1) x0 - q|| settles at 0.85 by iteration 5. It is still 0.85 at iterations 10 and 50.

Irreducible and aperiodic tell you the chain arrives. Only 0.85 tells you when.

A random variable describes one uncertain quantity. A stochastic process describes a collection of random variables indexed by time, space, or another ordered set. A Markov chain assumes that the next-state distribution depends on the present state rather than the entire observed past. The assumption belongs to the chosen state representation. If relevant history is omitted, the process may appear non-Markov even when a richer state would make the dependence local.

That is a claim about information, and it can be measured. The first person to measure it counted letters in a poem.

A chain satisfies detailed balance with π when πᵢPᵢⱼ = πⱼPⱼᵢ for every pair. The probability flow between each pair is then balanced, and summing those equalities shows that π is stationary. Some stationary chains, however, have circulating probability flows and do not satisfy detailed balance.

The man who generalised the sampler said as much in print. Hastings built his transition matrix in 1970 by imposing the reversibility condition, and noted that doing so “ensures” pi is a stationary distribution of P. That is a construction device, not a law. He wrote it down plainly: “For simplicity we have considered reversible Markov chains only.” He then pointed the reader to Handscomb for an irreversible P.

Thirty years later the point was made empirically rather than parenthetically. Diaconis and two co-authors analysed a deliberately nonreversible sampler in 2000, and found that it converges better than the reversible alternative. Reversible MCMC methods use detailed balance because it simplifies design, not because every valid chain must be reversible. Giving it up can buy speed.

The Dry/Wet chain is not a teaching toy. It is the ancestor of daily-rainfall modelling. In 1962 Gabriel and Neumann fitted a two-state, first-order wet/dry Markov chain to Tel Aviv data, and the field still dates itself from that paper. A 2026 paper on long dry spells opens by saying so: “Early developments in this line of research employed two-state first-order Markov chains to represent rainfall occurrences [Gabriel and Neumann, 1962].” The whole model is two numbers, p01 and p11.

Use these checks before interpreting long-run or multi-step conclusions. Steps 4 and 5 are listed separately because the first MCMC calculation ever run kept them separate.

That calculation was published in June 1953 by Metropolis and four co-authors. Convergence to the Boltzmann distribution rested on two facts, argued one at a time: a symmetric proposal, P_rs = P_sr, balancing the flow between states, and irreducibility, which they called ergodicity. Then they join the two: “We have seen already that the method is ergodic; i.e., that any state can be reached from any other, albeit in several moves. These two facts mean that our ensemble must approach the canonical distribution.” They also conceded what the argument does not deliver. It “does not, of course, specify how rapidly the canonical distribution is approached”.

Rate was not an academic worry for them. The run used N = 224 rigid spheres in two dimensions on the Los Alamos MANIAC, at about three minutes per cycle. Fewer than sixteen cycles were discarded for burn-in and about forty-eight to sixty-four were kept. That bought one point on the pressure curve every four to five hours. Communication and mixing are different audits because they were different arguments from the beginning.

A finite chain is specified by states, transitions, and an initial distribution — and both cases in this lesson fill the same five slots at very different scales. Markov's state space had two members, vowel and consonant, and his counts filled a transition row directly: 0.128 for a vowel after a vowel, 0.663 for a vowel after a consonant. The random surfer's state space held 24 million pages. Its transition matrix was built from as many as 518 million hyperlinks with d = 0.85, and its stationary distribution π was the product — a probability distribution over Web pages summing to one, sold to the world as a ranking. The n-step matrix Pⁿ carries an initial distribution μ₀ towards π. The second eigenvalue says how many steps that takes.