THE MIXING TIME how fast the chain forgets where it started
Convergence to π is geometric, and its rate is set by the second-largest eigenvalueλ₂ of P: the total-variation distance to π shrinks by about λ₂ each step. The mixing time — steps until you are within ε of stationary — is roughly ln(1/ε)/(1−λ₂). The gap 1−λ₂ (the spectral gap) is the whole story of fast versus slow mixing.
THE TECHNIQUE TV distance to π decays ~ λ₂ per step; t_mix ≈ ln(1/ε)/(1−λ₂)
Watch the total-variation distance to π fall geometrically, each step exactly λ₂ times the last — and read off the mixing time to reach a chosen tolerance: live demo
HISTORY & CREDIT Aldous & Diaconis, 1986
“Given enough steps any chain is as good as random.” — enough is the question, and it can be sharp. Many chains show a cutoff: almost no mixing for a while, then a sudden collapse to random over a narrow window — the famous “seven riffle shuffles randomise a deck” result. Mixing time, not eventual convergence, is what matters. cited
1981 · Diaconis & Shahshahani and Landau & Odlyzko — eigenvalue bounds on Markov-chain mixing; the spectral gap 1−λ₂ controls relaxation. 1986 · Aldous & Diaconis — “Shuffling cards and stopping times” formalises mixing time and the cutoff phenomenon. 1992 · Bayer & Diaconis — seven riffle shuffles suffice for 52 cards, and the approach to random is a sharp cutoff, not a slow fade.
The spectral gap is the clock of forgetting: a big gap mixes fast, a gap near zero (a near-disconnected chain, a bottleneck) mixes agonisingly slowly. Same stationary π, wildly different waiting. Aldous–Diaconis 1986
RECOMMEND FOR I-13 TV distance decays at exactly λ₂, computed
On the canonical compiler, the total-variation distance to π for the weather chain falls by exactly λ₂ = 0.4 every step — geometric convergence, measured:
$ i13 run mixing.i13 # P=[[.9,.1],[.5,.5]], pi=[5/6,1/6], lambda2 = .9+.5-1 = 0.4
TV(0) = 0.16666666666666674
TV(1) = 0.06666666666666674 ratio TV(1)/TV(0) = 0.40000000000000024
TV(2) = 0.02666666666666677 ratio TV(2)/TV(1) = 0.40000000000000113
TV(3) = 0.010666666666666755 -- each step exactly lambda2 = 0.4
Recommend: mixing time is LIT for I-13 — verified the TV distance to π decays 1/6 → 0.0667 → 0.0267 → 0.0107, each ratio 0.40000, i.e. exactly the second eigenvalue λ₂ = 0.4. From that single number the mixing time to any tolerance follows as ln(1/ε)/(1−λ₂) — the spectral gap made visible.