How fast does a Markov chain forget its starting point? For a reversible chain the complete answer is coded in the eigenvalues of its transition matrix: the largest eigenvalue is always , and the size of the gap between and the rest of the spectrum is the chain's fundamental time constant — a large gap means fast mixing, a small gap means slow mixing. Chapters 12–13 of Levin–Peres–Wilmer, Markov Chains and Mixing Times (AMS, 2009) develop this spectral theory and culminate in the discrete Cheeger inequality of Jerrum–Sinclair and Lawler–Sokal, which says that the spectral gap (an analytic quantity, defined below) and the bottleneck constant (a geometric quantity from Mission IV, also recalled below) control each other:
A chain mixes rapidly exactly when its state space has no bottleneck. This inequality is the backbone of the Markov-chain approach to approximate counting and of spectral graph theory at large; alongside it the chapters provide Wilson's method — the sharpest general technique for mixing-time lower bounds — and the comparison machinery that transfers spectral estimates between chains.
All chains live on a finite state space . A chain with transition matrix and stationary distribution is reversible when the detailed balance equations hold; reversibility is the standing assumption of both chapters. The yardsticks of the series are the total variation distance , the worst-case distance to stationarity , and the mixing time , with ; we write .
The spectral vocabulary: an eigenfunction of is a nonzero with , where ; the number is then an eigenvalue. Out of the spectrum one forms
Functions on carry the weighted inner product — the geometry, denoted , in which a reversible is self-adjoint — and the Dirichlet form
the average squared variation of along the chain's transitions. Finally, from Mission IV: the bottleneck ratio of a set of states is , the conditional probability at stationarity of escaping in one step, and the bottleneck constant is .
Theorem 13.14, the discrete Cheeger inequality: for a reversible irreducible chain,
The results. Theorems 12.3–12.4 sandwich the mixing time between and — the fundamental equivalence of spectral and mixing estimates for reversible chains, prerequisite for the cutoff criterion of Mission XI. The Cheeger inequality converts isoperimetry into spectral bounds; it is the mathematical core of the Jerrum–Sinclair program of polynomial-time approximate counting, and its graph version underlies expander theory. Wilson's method produced the sharp lower bounds for adjacent transpositions and hypercube-type chains; the comparison lemma is the engine behind the shuffle bounds cited in Mission V (§16.1).
Formalizing them. Mathlib has the spectral theorem for symmetric matrices but nothing connecting spectra to Markov chains: no spectral gap, no relaxation time, no Dirichlet forms, no Cheeger inequality in any form. A formalized discrete Cheeger inequality would be a landmark reusable well outside this series (spectral graph theory, expanders); the eigenvalue and Rayleigh-quotient layer built here is what Missions IX (tree relaxation, block dynamics) and XI (cutoff criterion) consume.
Everything routes through one change of basis: conjugating by the diagonal matrix with entries produces a matrix that is symmetric precisely because the chain is reversible, so Mathlib's spectral theorem applies — but transporting the resulting eigenbasis back to , keeping track of orthonormality with respect to the weighted inner product, is a genuine formal-linear-algebra project; nothing about it is deep, all of it is fussy. The definitions of and as suprema over the set of non-unit eigenvalues (finite, and nonempty once ) must be reconciled with the eigenbasis enumeration before any variational argument runs. The upper half of Cheeger is direct from the variational characterization — test it on the indicator function of a bottleneck set , recentred to have mean zero; the lower half is the hard half: the standard proof takes an optimal , decomposes it over its level sets , and applies Cauchy–Schwarz twice, and formalizing that level-set sweep is the main effort of the mission. Wilson's method needs a supermartingale-style iteration of the eigenfunction estimate; its constants are exact, so the inequalities cannot be rounded.
Eigenvalues are defined by real eigenvectors (); for reversible chains this captures the whole spectrum, and all statements assume reversibility wherever the book does. and are suprema of explicit sets of reals; on a one-point space these sets are empty and the supremum takes a junk value, so the affected statements carry the explicit hypothesis , matching the book's implicit assumption of a non-degenerate chain. with total inverse. Theorem 12.3 carries an explicit absorbing the rounding of a real-valued bound to an integer time. The cycle eigenvalue statement exhibits eigenvalues (existence of eigenfunctions); completeness of that list is not asserted. The variational characterization asserts both the minimization identity and its attainment, so it can be used in either direction.
Welcome contributions: the symmetrization API (conjugation by ), Rayleigh-quotient lemmas, level-set (layer-cake) infrastructure — all reused by Missions IX and XI.
namespace MarkovMixing
/-- **Theorem 13.14** (Jerrum–Sinclair, Lawler–Sokal; LPW), the capstone of
Chapters 12–13: the spectral gap and the bottleneck ratio of a reversible
chain satisfy `Φ⋆²/2 ≤ γ ≤ 2Φ⋆`. -/
theorem cheeger_inequality {V : Type*} [Fintype V] [DecidableEq V] [Nonempty V]
(hV : 2 ≤ Fintype.card V) (P : Matrix V V ℝ) (hP : IsStochastic P) (hirr : Irreducible P)
(π : V → ℝ) (hπ : IsStationary P π) (hrev : DetailedBalance P π) :
bottleneckStar P π ^ 2 / 2 ≤ spectralGap P ∧
spectralGap P ≤ 2 * bottleneckStar P π := by
sorry
end MarkovMixing
Let be an irreducible Markov chain on a finite state space with at least two states, reversible with respect to its stationary distribution (detailed balance: ). Two quantities measure how quickly the chain can move:
The theorem (Theorem 13.14 of Levin–Peres–Wilmer; Jerrum–Sinclair, Lawler–Sokal — the discrete Cheeger inequality, capstone of Chapters 12–13) asserts:
Bottlenecks and spectral gaps control each other up to a square: a chain mixes rapidly exactly when it has no bottleneck. This equivalence is the backbone of the Markov-chain approach to approximate counting and of expander graph theory.
No open leaves. Every sub-goal is proved or awaiting decomposition.