The first mission of this series established that an irreducible finite Markov chain has a unique stationary distribution . The present mission, covering Chapters 3–4 of Levin–Peres–Wilmer, Markov Chains and Mixing Times (AMS, 2009), answers the two questions that make that fact useful. First, the inverse problem of sampling: given a target distribution — uniform over proper colorings, a Gibbs measure, a posterior — how does one build a chain whose stationary distribution is ? The Metropolis and Glauber constructions of Chapter 3 are the universal answers, and they are the engine of Markov chain Monte Carlo across statistical physics, Bayesian statistics, and approximate counting. Second, the convergence question: in what sense, and how fast, does an irreducible aperiodic chain approach ? Chapter 4 introduces the total variation distance, proves the Convergence Theorem — geometric convergence to stationarity — and defines the mixing time, the parameter the entire remainder of the book estimates.
All chains live on a finite state space and are presented by row-stochastic matrices, with the definitions of Mission I. The total variation distance between distributions and is
the maximal discrepancy over events. A coupling of and is a distribution on whose marginals are and . For a chain with stationary one sets
and the mixing time is , with .
The Metropolis chain for a target and a symmetric proposal chain accepts a proposed move with probability ; a general (not necessarily symmetric) base chain is handled by the ratio . The Glauber dynamics for a distribution on configurations picks a uniform site and re-samples its value from conditioned on the rest.
This is Theorem 4.9, the Convergence Theorem. It asserts only the geometric shape of convergence, leaving all quantitative rates to later missions, which is why it is the goal.
The milestones are the chapter's working parts: stationarity and reversibility of the Metropolis chain for symmetric and general base chains (§3.2, Exercise 3.1), stationarity and reversibility of the Glauber dynamics (§3.3, Exercise 3.2); the three characterizations of total variation distance — the half- formula (Proposition 4.2 with Remark 4.3), the supremum over -bounded test functions (Proposition 4.5), and the coupling characterization with an optimal coupling attaining it (Proposition 4.7 with Remark 4.8); the comparison (Lemma 4.11) and submultiplicativity (Lemma 4.12); the standard mixing-time consequences and (§4.5); and the equality of distance to stationarity for a group walk and its inverse walk (Lemma 4.13 and Corollary 4.14).
The results. The Convergence Theorem is the qualitative foundation on which quantitative mixing theory stands: it guarantees that is finite, so every bound in Missions III–XIII is a bound on a well-defined quantity. The TV characterizations are used constantly — the coupling characterization is the engine of Mission III, the half- formula of every explicit computation. The Metropolis and Glauber stationarity results justify the chains analyzed in Missions III (colorings, hardcore), VIII (path coupling) and IX (Ising). Submultiplicativity of is what makes a meaningful single number.
Formalizing them. None of this exists in Mathlib: there is no total variation distance for finitely supported distributions, no coupling theory, no mixing time, no MCMC correctness statement. The definition layer published here (TV distance, , , , couplings, Metropolis, Glauber) is imported by every subsequent mission of the series.
The tempting proof of Theorem 4.9 via spectral decomposition fails twice: it needs reversibility, which the theorem does not assume, and spectral machinery that arrives only in Mission VII. The book's proof is the Doeblin decomposition: by Proposition 1.7 some power satisfies , so with the rank-one matrix of rows , and induction gives . The formal work is matrix algebra with careful bookkeeping of the remainder chain , plus the monotonicity of needed to interpolate between multiples of . For Proposition 4.7 the delicate half is constructing the optimal coupling: mass on the diagonal and the normalized product of the positive parts off it, with the degenerate case handled separately. The Glauber stationarity statement must be phrased with care because configurations outside the support of have junk rows; the formalization asserts stochasticity only at supported configurations, and detailed balance globally.
Total variation distance is defined as the supremum over events, over Finset V, exactly as in (4.1); the half- formula is a milestone, not the definition. The mixing time is sInf of the set in (junk value if empty — impossible under the goal theorem). Couplings are distributions on the product with prescribed marginals; no probability-space machinery is used. The mixing-time inequalities are stated with the integer-rounding slack made explicit (e.g. via Nat.ceil of a real logarithm) so that no statement is true only "up to rounding". The Metropolis definitions use total real division, so the hypotheses require pointwise; this matches the book, which divides by throughout.
Welcome contributions beyond the milestones: simp lemmas for tvDist, monotonicity of and in , and triangle-inequality infrastructure — all reused by Missions III–XIII.
namespace MarkovMixing
/-- **Theorem 4.9, the Convergence Theorem** (LPW), the capstone of
Chapter 4: an irreducible, aperiodic finite chain converges to its stationary
distribution geometrically fast in total variation:
`max_x ‖P^t(x,·) − π‖_TV ≤ C αᵗ` for some `α ∈ (0,1)` and `C > 0`. -/
theorem convergence_theorem {V : Type*} [Fintype V] [DecidableEq V] [Nonempty V]
(P : Matrix V V ℝ) (hP : IsStochastic P) (hirr : Irreducible P)
(hap : Aperiodic P) (π : V → ℝ) (hπ : IsStationary P π) :
∃ α : ℝ, α ∈ Set.Ioo (0 : ℝ) 1 ∧ ∃ C : ℝ, 0 < C ∧
∀ t : ℕ, distStationary P π t ≤ C * α ^ t := by
sorry
end MarkovMixing
Let be the transition matrix of an irreducible and aperiodic Markov chain on a finite state space — irreducible meaning every state can reach every other in some number of steps, aperiodic meaning the return times to a state have greatest common divisor one — and let be a stationary distribution for , i.e. for all . Write for the distribution of the chain at time started at , and for the total variation distance.
The theorem — the Convergence Theorem (Theorem 4.9 of Levin–Peres–Wilmer), the capstone of Chapter 4 — asserts that the chain converges to geometrically fast, uniformly in the starting state: there exist a rate and a constant such that
In particular the stationary distribution of an irreducible aperiodic chain is unique and is reached from every starting point, with an error decaying exponentially in time — the statement that gives the mixing time its meaning, and the result all later chapters quantify.
No open leaves. Every sub-goal is proved or awaiting decomposition.