Markov Chains & Mixing
Stationary distributions, ergodicity and mixing times.
About seven riffle shuffles are needed to mix a 52-card deck, and six visibly do not suffice. A robot's motion model on a 16-cell loop forgets its starting cell after about 76 steps. PageRank's power iteration gets within 0.03% of its answer in 50 iterations, however large the web. Mixing-time theory explains all three: it measures how fast a Markov chain forgets where it started, and it gives the tools to prove it.
What you’ll learn
- Define total-variation distance and mixing time, and prove the convergence theorem for finite irreducible aperiodic chains.
- Bound mixing times of reversible chains by the spectral gap, from both sides, and compute gaps for standard examples.
- Bound mixing times by coupling, and describe the cutoff phenomenon for card shuffling and the hypercube.
- Prove that PageRank's power iteration converges at rate , and relate mixing to the design and diagnosis of MCMC.
Convergence in total variation
For an irreducible aperiodic finite chain, some power has all entries positive: for all (a number-theoretic lemma about return times). Let be the matrix whose rows all equal , and choose so that
Two identities do the work: for any stochastic , and because is stationary (hence also ). By induction on , with :
Multiply by for . Every row of is a difference of two distributions, so it has total-variation norm at most 1:
That is geometric decay with and . ∎ Aperiodicity is essential: the chain that alternates between two states has forever.
Three companions of the theorem:
- Ergodic theorem. For an irreducible chain, almost surely from any start; aperiodicity is not needed for time averages.
- Kac's formula. , where is the first return time to : frequent states are revisited quickly.
- Submultiplicativity. With , one has and . Hence : once a chain has mixed to , each further steps at least halves the distance.
Spectral gap and relaxation time
A chain is reversible if it satisfies detailed balance, . Then is self-adjoint in the inner product , so its eigenvalues are real, , with an orthonormal basis of eigenfunctions (and ). Let , the absolute spectral gap , and the relaxation time .
Expand the -step transition density in the eigenbasis. Orthonormality in makes the matrix orthogonal, so :
Bound the sum by Cauchy–Schwarz:
Average over , and use . The right side is at most once . ∎
| Chain | Spectral gap | Mixing time |
|---|---|---|
| Two states, , | (when ) | order |
| Lazy random walk on the -cycle | order | |
| Lazy walk on the hypercube (re-randomize a random coordinate) | , with cutoff | |
| Random transpositions of cards | , with cutoff (Diaconis & Shahshahani, 1981) | |
| Riffle shuffles of cards | , with cutoff (Bayer & Diaconis, 1992) |
Coupling and cutoff
On the hypercube, let both copies pick the same coordinate and set it to the same fresh random bit. Once every coordinate has been picked, the copies agree, so is at most the coupon-collector time, and a union bound gives . Therefore , within a factor of 2 of the truth, , using no eigenvalues at all.
Many natural chains show cutoff (Aldous & Diaconis, 1986): stays near 1 and then falls to near 0 within a window much shorter than . Bayer and Diaconis computed the distance to uniform after riffle shuffles of 52 cards exactly:
| Shuffles | 1–4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|
| 1.000 | 0.924 | 0.614 | 0.334 | 0.167 | 0.085 | 0.043 |
For the lazy walk on , the relaxation time is and the mixing time is about . What does the gap between them reflect?
- The spectral upper bound is wrong for this chain
- The chain starts far from stationarity in a high-dimensional sense: about relaxation times are needed to wash out the start, which is what produces cutoff
- The walk is periodic, which slows mixing
- Mixing time and relaxation time always differ by a factor
Show the answer
B. The chain starts far from stationarity in a high-dimensional sense: about relaxation times are needed to wash out the start, which is what produces cutoff
From a corner, all coordinates must be refreshed: after steps a coordinate is still untouched with probability about , and the expected number of untouched coordinates, , must drop below about (the size of typical fluctuations), which happens at . The theorem's upper bound is correct but loose.
Chains by design: PageRank and MCMC
With , how many power iterations guarantee a total-variation error below , for a web of any size?
Show the answer
86
The total-variation error is half the error, so it is at most . Solve : , so 86 iterations. After 50 iterations the bound is . The damping factor buys this uniform rate; without it, convergence depends on the structure of the link graph and can fail for periodic or disconnected webs.
MCMC turns the question around: the target is given, and the chain is designed to have it as stationary distribution, via detailed balance (Metropolis–Hastings, Gibbs). Everything then hinges on the mixing time. Landmark rapid-mixing results made previously intractable counting problems approximable in polynomial time: matchings and the permanent of non-negative matrices (Jerrum & Sinclair, 1989; Jerrum, Sinclair & Vigoda, 2004) and the volume of convex bodies (Dyer, Frieze & Kannan, 1991). Coupling from the past (Propp & Wilson, 1996) even produces exact samples from for monotone chains, stopping at a random time that certifies mixing.
In applied Bayesian statistics, mixing is diagnosed rather than proved: several chains are started from dispersed points and compared, and the split- statistic flags chains that disagree. A diagnostic can reveal non-convergence but never certify convergence, since a chain stuck in one mode of a bimodal posterior looks perfectly stationary.
Key takeaways
- Finite irreducible aperiodic chains converge to their unique stationary distribution geometrically in total variation; the Doeblin minorization gives . Periodicity breaks convergence of , not of time averages.
- For reversible chains, , with ; bottlenecks (low conductance) are what make chains slow.
- Coupling bounds mixing without eigenvalues ( on the hypercube). Many chains show cutoff: 52 cards go from distance 0.61 to 0.33 between six and seven riffle shuffles.
- PageRank's iteration converges at rate for any web: . MCMC needs rapid mixing, which can sometimes be proved (permanent, volume, spectral independence) but in practice is only diagnosed.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
A simple random walk on a cycle of 10 nodes moves to a uniformly random neighbor at every step. Does converge to the uniform distribution?
- Yes, because the walk is irreducible
- Yes, at rate set by the second-largest eigenvalue
- No: the cycle has even length, so the walk alternates between even and odd nodes; making it lazy fixes this
- No, because the uniform distribution is not stationary for this walk
Show the answer
C. No: the cycle has even length, so the walk alternates between even and odd nodes; making it lazy fixes this
The walk is irreducible but has period 2: is supported on nodes of one parity, and forever. The eigenvalue (for ) is the culprit. Holding still with probability shifts the spectrum into and restores convergence.
Under a coupling of two copies of a chain started at and , the probability that they have not met by time 100 is at most 0.05. What can you conclude?
- exactly
- The chain is reversible
Show the answer
A.
The coupling inequality: total variation is at most the probability that the copies differ, which is at most . Bounding needs the same bound for all pairs of starting states.
For the two-state chain with (the umbrella world's weather), what are the absolute spectral gap and the relaxation time?
- Gap , relaxation time
- Gap , relaxation time
- Gap , relaxation time
- Gap , relaxation time
Show the answer
C. Gap , relaxation time
, so and days. The deviation from stationarity shrinks by the factor per day: toward .
Further reading
- D. A. Levin & Y. Peres, Markov Chains and Mixing Times, 2nd ed., with contributions by E. L. Wilmer (American Mathematical Society, 2017).
- D. Aldous & P. Diaconis, "Shuffling cards and stopping times," American Mathematical Monthly 93(5), 333–348 (1986).
- D. Bayer & P. Diaconis, "Trailing the dovetail shuffle to its lair," Annals of Applied Probability 2(2), 294–313 (1992).
- M. Jerrum & A. Sinclair, "Approximating the permanent," SIAM Journal on Computing 18(6), 1149–1178 (1989).
- L. Page, S. Brin, R. Motwani & T. Winograd, "The PageRank citation ranking: Bringing order to the web," Stanford InfoLab technical report (1999).