Missions II–III produce upper bounds on mixing times. Whether such a bound is sharp is a different question: an bound on a chain that actually mixes in steps hides the truth. Chapter 7 of Levin–Peres–Wilmer, Markov Chains and Mixing Times (AMS, 2009) develops the standard toolkit of lower bounds: the counting and diameter bounds (a chain cannot spread faster than its transition graph allows), the bottleneck ratio (a chain cannot mix faster than it crosses its worst cut), and distinguishing statistics (a chain is far from stationarity as long as some statistic separates from by several standard deviations). The bottleneck bound — closely related to the conductance of the chain and, via Mission VII, to the Cheeger inequality — is the single most important obstruction result in the subject: it is how slow mixing (torpid mixing of Ising at low temperature, in Mission IX) is proved.
For a chain with stationary distribution , the edge measure is , the bottleneck ratio of a set of states is
and the bottleneck ratio of the chain is . The maximal one-step out-degree is ; the diameter is measured in the graph joining when . For a statistic and distribution , and are the finite-sum expectation and variance, and denotes the pushforward of under .
This is Theorem 7.3, the bottleneck-ratio lower bound, the chapter's central theorem.
The counting bound for chains with uniform stationary distribution (§7.1.1, display (7.2)); the diameter bound: any two states satisfy for (§7.1.2, display (7.3)); Proposition 7.8 (a statistic separating means by standard deviations forces ); Lemma 7.9 (projection under a statistic does not increase TV distance); Proposition 7.13 (the lazy hypercube walk satisfies ); and Proposition 7.14 (the top-to-random shuffle needs shuffles, matching the upper bound of Mission III).
The results. Together with Mission III this pins the top-to-random shuffle at — the first sharp mixing result of the series, and the prototype of the cutoff phenomenon formalized in Mission XI. Proposition 7.13 similarly matches the hypercube upper bound and feeds the cutoff analysis. The bottleneck bound is used in Mission IX to prove exponentially slow mixing of the mean-field Ising model at low temperature, and its two-sided refinement is the Cheeger inequality of Mission VII.
Formalizing them. Mathlib has no notion of conductance/bottleneck ratio of a chain, no distinguishing-statistic method, and no mixing-time lower bound of any kind. The pushforward and variance infrastructure over finitely supported distributions is elementary but new, and reusable wherever second-moment methods appear (Wilson's method in Mission VII).
The bottleneck theorem's proof is short but exact: it hinges on the identity for conditioned on , followed by a telescoping estimate of ; the formal cost is manipulating conditioned measures and one-sided TV sums (Remark 4.3 from Mission II). For Proposition 7.8, the second-moment argument runs through Chebyshev on both distributions plus optimization of a threshold — the constants are exact, not asymptotic, so the formal inequalities must be done carefully. Proposition 7.13 requires the binomial mean/variance computation for Hamming weight under both and , including the negative-correlation bound for unrefreshed coordinates. The naive route to a lower bound — "the chain has not left a small set, so it is far from " — is precisely the counting bound and is too weak for the sharp results; the statistics method is what closes the gap.
is an infimum over the subtype of nonempty sets with ; on a one-point space this subtype is empty and the infimum takes a junk value, making the goal trivially true there (the bound carries content only for , as in the book). The counting bound divides by with total division ( gives a trivially true statement). The diameter bound is stated for arbitrary pairs of states through SimpleGraph.dist of the transition graph, which subsumes the book's diameter formulation. Propositions 7.13 and 7.14 are stated for all integer times (resp. ), using monotonicity of instead of evaluating at a real-valued time — this avoids floor artifacts while keeping the book's content. Proposition 7.14 quantifies " large, then large" exactly as the book's iterated limit.
Welcome contributions: monotonicity of in ; conditioned-measure lemmas; variance API for distExp/distVar.
namespace MarkovMixing
/-- **Theorem 7.3** (LPW), the bottleneck-ratio bound and capstone of
Chapter 7: `t_mix ≥ 1/(4 Φ⋆)`. -/
theorem bottleneck_lower_bound {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 π) :
(4 * bottleneckStar P π)⁻¹ ≤ (tMix P π : ℝ) := by
sorry
end MarkovMixing
Let be an irreducible, aperiodic Markov chain on a finite state space with stationary distribution . The edge measure is the stationary flow along ; the bottleneck ratio of a set of states is
the conditional probability at stationarity of escaping in one step; and the bottleneck constant is . The mixing time is the first at which , with the total variation distance.
The theorem (Theorem 7.3 of Levin–Peres–Wilmer, the capstone of Chapter 7) asserts:
A chain with a bottleneck — a half-space it leaves only reluctantly — mixes slowly: started inside such a set, the chain needs order steps to transfer the requisite mass out. This is the qualitative converse of the Cheeger inequality of Mission VII.
No open leaves. Every sub-goal is proved or awaiting decomposition.