Simple Algorithm
Artificial Intelligence · Deep Layer · 28 min

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 α\alpha, and relate mixing to the design and diagnosis of MCMC.

Convergence in total variation

DerivationProof by a Doeblin minorization (after Levin & Peres)
  1. Pr ≥ δ Π  entrywise,soPr=δ Π+(1−δ) Q  with Q stochasticP^r\ \ge\ \delta\,\Pi\ \ \text{entrywise},\qquad\text{so}\qquad P^r=\delta\,\Pi+(1-\delta)\,Q\ \ \text{with}\ Q\ \text{stochastic}

    For an irreducible aperiodic finite chain, some power has all entries positive: Pr(x,y)>0P^r(x,y)>0 for all x,yx,y (a number-theoretic lemma about return times). Let Π\Pi be the matrix whose rows all equal π\pi, and choose δ>0\delta>0 so that

  2. Prk=(1−θk) Π+θk QkP^{rk}=(1-\theta^k)\,\Pi+\theta^k\,Q^k

    Two identities do the work: MΠ=ΠM\Pi=\Pi for any stochastic MM, and ΠP=Π\Pi P=\Pi because π\pi is stationary (hence also ΠQ=Π\Pi Q=\Pi). By induction on kk, with θ=1−δ\theta=1-\delta:

  3. Prk+j−Π=θk(QkPj−Π)⟹d(rk+j)≤(1−δ)kP^{rk+j}-\Pi=\theta^k\big(Q^kP^j-\Pi\big)\quad\Longrightarrow\quad d(rk+j)\le(1-\delta)^k

    Multiply by PjP^j for 0≤j<r0\le j<r. Every row of QkPj−ΠQ^kP^j-\Pi is a difference of two distributions, so it has total-variation norm at most 1:

  4. d(t)≤(1−δ)⌊t/r⌋d(t)\le(1-\delta)^{\lfloor t/r\rfloor}

    That is geometric decay with α=(1−δ)1/r\alpha=(1-\delta)^{1/r} and C=(1−δ)−1C=(1-\delta)^{-1}. ∎ Aperiodicity is essential: the chain that alternates between two states has d(t)=12d(t)=\tfrac12 forever.

Three companions of the theorem:

  • Ergodic theorem. For an irreducible chain, 1t∑s<tf(Xs)→Eπf\frac1t\sum_{s<t}f(X_s)\to\E_\pi f almost surely from any start; aperiodicity is not needed for time averages.
  • Kac's formula. π(x)=1/Ex[τx+]\pi(x)=1/\E_x[\tau_x^+], where τx+\tau_x^+ is the first return time to xx: frequent states are revisited quickly.
  • Submultiplicativity. With dˉ(t)=max⁡x,y∥Pt(x,⋅)−Pt(y,⋅)∥TV\bar d(t)=\max_{x,y}\|P^t(x,\cdot)-P^t(y,\cdot)\|_{\mathrm{TV}}, one has d(t)≤dˉ(t)≤2d(t)d(t)\le\bar d(t)\le2d(t) and dˉ(s+t)≤dˉ(s) dˉ(t)\bar d(s+t)\le\bar d(s)\,\bar d(t). Hence tmix(ε)≤⌈log⁡2(1/ε)⌉ tmixt_{\mathrm{mix}}(\varepsilon)\le\lceil\log_2(1/\varepsilon)\rceil\,t_{\mathrm{mix}}: once a chain has mixed to 14\tfrac14, each further tmixt_{\mathrm{mix}} steps at least halves the distance.

Spectral gap and relaxation time

A chain is reversible if it satisfies detailed balance, π(x)P(x,y)=π(y)P(y,x)\pi(x)P(x,y)=\pi(y)P(y,x). Then PP is self-adjoint in the inner product ⟨f,g⟩π=∑xπ(x)f(x)g(x)\langle f,g\rangle_\pi=\sum_x\pi(x)f(x)g(x), so its eigenvalues are real, 1=λ1>λ2≥⋯≥λn≥−11=\lambda_1>\lambda_2\ge\dots\ge\lambda_n\ge-1, with an orthonormal basis of eigenfunctions fjf_j (and f1≡1f_1\equiv1). Let λ∗=max⁡j≥2∣λj∣\lambda_*=\max_{j\ge2}|\lambda_j|, the absolute spectral gap γ∗=1−λ∗\gamma_*=1-\lambda_*, and the relaxation time trel=1/γ∗t_{\mathrm{rel}}=1/\gamma_*.

DerivationProof of the upper bound
  1. Pt(x,y)π(y)=1+∑j≥2λjt fj(x) fj(y)\frac{P^t(x,y)}{\pi(y)}=1+\sum_{j\ge2}\lambda_j^t\,f_j(x)\,f_j(y)

    Expand the tt-step transition density in the eigenbasis. Orthonormality in L2(π)L^2(\pi) makes the matrix (fj(x)π(x))\big(f_j(x)\sqrt{\pi(x)}\big) orthogonal, so ∑jfj(x)2=1/π(x)\sum_jf_j(x)^2=1/\pi(x):

  2. ∣Pt(x,y)π(y)−1∣ ≤ λ∗t∑jfj(x)2∑jfj(y)2 ≤ λ∗tπ(x) π(y) ≤ λ∗tπmin⁡\Big|\frac{P^t(x,y)}{\pi(y)}-1\Big|\ \le\ \lambda_*^t\sqrt{\sum_jf_j(x)^2}\sqrt{\sum_jf_j(y)^2}\ \le\ \frac{\lambda_*^t}{\sqrt{\pi(x)\,\pi(y)}}\ \le\ \frac{\lambda_*^t}{\pi_{\min}}

    Bound the sum by Cauchy–Schwarz:

  3. ∥Pt(x,⋅)−π∥TV=12∑yπ(y)∣Pt(x,y)π(y)−1∣ ≤ e−t/trelπmin⁡\|P^t(x,\cdot)-\pi\|_{\mathrm{TV}}=\tfrac12\sum_y\pi(y)\Big|\frac{P^t(x,y)}{\pi(y)}-1\Big|\ \le\ \frac{e^{-t/t_{\mathrm{rel}}}}{\pi_{\min}}

    Average over y∼πy\sim\pi, and use λ∗t=(1−γ∗)t≤e−t/trel\lambda_*^t=(1-\gamma_*)^t\le e^{-t/t_{\mathrm{rel}}}. The right side is at most ε\varepsilon once t≥trelln⁡1επmin⁡t\ge t_{\mathrm{rel}}\ln\frac1{\varepsilon\pi_{\min}}. ∎

ChainSpectral gapMixing time
Two states, P(1→2)=aP(1\to2)=a, P(2→1)=bP(2\to1)=ba+ba+b (when a+b≤1a+b\le1)order 1/(a+b)1/(a+b)
Lazy random walk on the nn-cycle12(1−cos⁡2πn)≈π2/n2\tfrac12\big(1-\cos\tfrac{2\pi}n\big)\approx\pi^2/n^2order n2n^2
Lazy walk on the hypercube {0,1}n\{0,1\}^n (re-randomize a random coordinate)1/n1/n12nln⁡n\tfrac12n\ln n, with cutoff
Random transpositions of nn cards2/n2/n12nln⁡n\tfrac12n\ln n, with cutoff (Diaconis & Shahshahani, 1981)
Riffle shuffles of nn cards12\tfrac1232log⁡2n\tfrac32\log_2n, with cutoff (Bayer & Diaconis, 1992)
The relaxation time can underestimate the mixing time by the logarithmic factor in the theorem: riffle shuffles have trel=2t_{\mathrm{rel}}=2 yet need about 32log⁡2n\tfrac32\log_2n shuffles. Conductance gives another handle: for the bottleneck ratio Φ∗\Phi_*, Φ∗2/2≤γ≤2Φ∗\Phi_*^2/2\le\gamma\le2\Phi_* (Jerrum & Sinclair, 1989; Lawler & Sokal, 1988), so a chain mixes slowly exactly when its state space has a bottleneck.

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 τ\tau is at most the coupon-collector time, and a union bound gives P(τ>nln⁡n+cn)≤n(1−1n)nln⁡n+cn≤e−cP(\tau>n\ln n+cn)\le n(1-\tfrac1n)^{n\ln n+cn}\le e^{-c}. Therefore tmix≤nln⁡n+nln⁡4t_{\mathrm{mix}}\le n\ln n+n\ln4, within a factor of 2 of the truth, 12nln⁡n\tfrac12n\ln n, using no eigenvalues at all.

Many natural chains show cutoff (Aldous & Diaconis, 1986): d(t)d(t) stays near 1 and then falls to near 0 within a window much shorter than tmixt_{\mathrm{mix}}. Bayer and Diaconis computed the distance to uniform after kk riffle shuffles of 52 cards exactly:

Shuffles kk1–45678910
d(k)d(k)1.0000.9240.6140.3340.1670.0850.043
After the cutoff, each extra shuffle halves the distance, the eigenvalue 12\tfrac12 at work. For reversible chains, cutoff requires tmix⋅γ→∞t_{\mathrm{mix}}\cdot\gamma\to\infty (Peres's product condition), so the two-state chain and the cycle have none.
Check your understanding

For the lazy walk on {0,1}n\{0,1\}^n, the relaxation time is nn and the mixing time is about 12nln⁡n\tfrac12n\ln n. What does the gap between them reflect?

  1. The spectral upper bound is wrong for this chain
  2. The chain starts far from stationarity in a high-dimensional sense: about 12ln⁡n\tfrac12\ln n relaxation times are needed to wash out the start, which is what produces cutoff
  3. The walk is periodic, which slows mixing
  4. Mixing time and relaxation time always differ by a factor ln⁡n\ln n
Show the answer

B. The chain starts far from stationarity in a high-dimensional sense: about 12ln⁡n\tfrac12\ln n relaxation times are needed to wash out the start, which is what produces cutoff

From a corner, all nn coordinates must be refreshed: after tt steps a coordinate is still untouched with probability about e−t/ne^{-t/n}, and the expected number of untouched coordinates, ne−t/nne^{-t/n}, must drop below about n\sqrt n (the size of typical fluctuations), which happens at t≈12nln⁡nt\approx\tfrac12n\ln n. The theorem's upper bound trelln⁡(1/επmin⁡)≈n2ln⁡2t_{\mathrm{rel}}\ln(1/\varepsilon\pi_{\min})\approx n^2\ln2 is correct but loose.

Chains by design: PageRank and MCMC

Predict before you look

With α=0.85\alpha=0.85, how many power iterations guarantee a total-variation error below 10−610^{-6}, for a web of any size?

Show the answer

86

The total-variation error is half the ℓ1\ell_1 error, so it is at most 0.85t0.85^t. Solve 0.85t<10−60.85^t<10^{-6}: t>ln⁡(106)/ln⁡(1/0.85)=13.82/0.1625≈85.0t>\ln(10^6)/\ln(1/0.85)=13.82/0.1625\approx85.0, so 86 iterations. After 50 iterations the bound is 0.8550≈3×10−40.85^{50}\approx3\times10^{-4}. 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 π\pi 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 π\pi 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-R^\hat R 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 Pr≥δΠP^r\ge\delta\Pi gives d(t)≤(1−δ)⌊t/r⌋d(t)\le(1-\delta)^{\lfloor t/r\rfloor}. Periodicity breaks convergence of PtP^t, not of time averages.
  • For reversible chains, (trel−1)ln⁡12ε≤tmix(ε)≤trelln⁡1επmin⁡(t_{\mathrm{rel}}-1)\ln\frac1{2\varepsilon}\le t_{\mathrm{mix}}(\varepsilon)\le t_{\mathrm{rel}}\ln\frac1{\varepsilon\pi_{\min}}, with trel=1/γ∗t_{\mathrm{rel}}=1/\gamma_*; bottlenecks (low conductance) are what make chains slow.
  • Coupling bounds mixing without eigenvalues (tmix≤nln⁡n+nln⁡4t_{\mathrm{mix}}\le n\ln n+n\ln4 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 α\alpha for any web: ∥πt−π∥1≤2αt\|\pi_t-\pi\|_1\le2\alpha^t. 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.

Question 1

A simple random walk on a cycle of 10 nodes moves to a uniformly random neighbor at every step. Does Pt(x,⋅)P^t(x,\cdot) converge to the uniform distribution?

  1. Yes, because the walk is irreducible
  2. Yes, at rate set by the second-largest eigenvalue cos⁡(2π/10)\cos(2\pi/10)
  3. No: the cycle has even length, so the walk alternates between even and odd nodes; making it lazy fixes this
  4. 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: Pt(x,⋅)P^t(x,\cdot) is supported on nodes of one parity, and d(t)≥12d(t)\ge\tfrac12 forever. The eigenvalue −1-1 (for k=5k=5) is the culprit. Holding still with probability 12\tfrac12 shifts the spectrum into [0,1][0,1] and restores convergence.

Question 2

Under a coupling of two copies of a chain started at xx and yy, the probability that they have not met by time 100 is at most 0.05. What can you conclude?

  1. ∥P100(x,⋅)−P100(y,⋅)∥TV≤0.05\|P^{100}(x,\cdot)-P^{100}(y,\cdot)\|_{\mathrm{TV}}\le0.05
  2. tmix≤100t_{\mathrm{mix}}\le100 exactly
  3. ∥P100(x,⋅)−P100(y,⋅)∥TV≥0.05\|P^{100}(x,\cdot)-P^{100}(y,\cdot)\|_{\mathrm{TV}}\ge0.05
  4. The chain is reversible
Show the answer

A. ∥P100(x,⋅)−P100(y,⋅)∥TV≤0.05\|P^{100}(x,\cdot)-P^{100}(y,\cdot)\|_{\mathrm{TV}}\le0.05

The coupling inequality: total variation is at most the probability that the copies differ, which is at most P(τ>100)P(\tau>100). Bounding d(t)d(t) needs the same bound for all pairs of starting states.

Question 3

For the two-state chain with a=b=0.3a=b=0.3 (the umbrella world's weather), what are the absolute spectral gap and the relaxation time?

  1. Gap 0.30.3, relaxation time 3.33.3
  2. Gap 0.40.4, relaxation time 2.52.5
  3. Gap 0.60.6, relaxation time 1.71.7
  4. Gap 0.70.7, relaxation time 1.41.4
Show the answer

C. Gap 0.60.6, relaxation time 1.71.7

λ2=1−a−b=0.4\lambda_2=1-a-b=0.4, so γ∗=1−0.4=0.6\gamma_*=1-0.4=0.6 and trel=1/0.6≈1.7t_{\mathrm{rel}}=1/0.6\approx1.7 days. The deviation from stationarity shrinks by the factor 0.40.4 per day: 1, 0.7, 0.58, 0.532,…1,\ 0.7,\ 0.58,\ 0.532,\dots toward 0.50.5.

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).