Every mixing bound in Missions II–IX ultimately leaned on either coupling or the spectrum, and the spectral route demanded reversibility. Chapter 17 of Levin–Peres–Wilmer, Markov Chains and Mixing Times (AMS, 2009) opens a third route: martingales — processes whose conditional expected increment vanishes — and the beautiful evolving-set process of Morris and Peres built from them. The payoff theorem of the chapter bounds the mixing time of any lazy irreducible chain by its bottleneck constant, with no reversibility hypothesis anywhere — an honest strengthening of the spectral route through the Cheeger inequality, whose proof is a martingale analysis of a random sequence of sets growing and shrinking under the chain's flow. The same chapter proves the optional stopping theorem in the exact discrete form the rest of the series consumes, and applies the machinery to sharp return-probability estimates for lazy walks.
Throughout, is a chain on a finite state space with stationary distribution ; , , and as in the earlier missions; . The chain is lazy when at every state.
A martingale adapted to the chain is a family of functions of the trajectory up to time such that the conditional expectation of , given the trajectory so far, equals — for a finite chain, a pointwise finite-sum identity. A stopping time is a -valued stopping rule in the sense of Mission III: whether to stop at time depends only on the trajectory up to .
From Mission IV: the edge measure is , with , and the bottleneck constant is the minimum over sets with of . The evolving-set process is the Markov chain on subsets of in which, from the current set , one draws uniform on and passes to the superlevel set
— states currently receiving a large share of the flow out of are likely to join, states receiving little are likely to leave.
Theorem 17.10 (Morris–Peres), the capstone of Chapter 17: for any lazy irreducible chain — reversibility not assumed —
The results. The optional stopping theorem is the workhorse identity of discrete probability — the earlier missions' gambler's-ruin and hitting-time computations are all instances, and Missions XI–XII cite it again. The Morris–Peres theorem is the strongest known elementary relation between geometry and mixing: for reversible chains it recovers the Cheeger-based bound of Mission VII, but it needs no reversibility, and its proof technique — controlling the root as a supermartingale — introduced evolving sets as a tool that has since produced heat-kernel decay, isoperimetric mixing profiles, and bounds for non-reversible and time-inhomogeneous chains well beyond the book.
Formalizing them. Mathlib's martingale library lives in measure-theoretic generality; this mission's chain-adapted martingales are self-contained finite objects (families of functions on trajectory spaces), so the optional stopping theorem here is independent of, and complementary to, the measure-theoretic one. Evolving sets exist in no proof assistant; the process is a genuinely novel formalization target — a Markov chain whose states are Finsets, defined through interval lengths of a uniform variable.
The optional stopping theorem needs the dominated-convergence step (bounded martingale, a.s. finite time) rendered as an elementary tail estimate — the series must be shown summable and equal to by an exchange of finite sums with a limit. The evolving-set transition probabilities are interval lengths: the probability of passing from to is the length of the set of whose superlevel set is exactly , which the formalization encodes by explicit upper and lower thresholds (a min over and a max over of the clipped ratios ); establishing that these lengths sum to one over , and that the process has the two martingale properties, is delicate finite-order-statistics reasoning. The goal theorem then runs a supermartingale argument on : laziness keeps the thresholds in , an expansion estimate converts the bottleneck constant into a per-step multiplicative decay of , and Lemma 17.12 converts that decay into a total-variation bound. Theorem 17.17 composes the same machinery with a Cauchy–Schwarz step. None of this exists in any library; the auxiliary supermartingale lemmas are welcome as separate contributions.
Martingales, stopping times, and stopped expectations are the trajectory-calculus objects of Missions I and III: finite sums over paths weighted by , with expectations over the stopping time as tsums in (non-summable families sum to ; the a.s.-finiteness hypothesis is the statement that the stopping mass sums to ). The evolving-set matrix is defined by the clipped-threshold formula described above — an explicit real matrix on Finset V — and the goal and lemmas assume positive and lazy exactly where the book does. Theorem 17.17 is stated for the lazy walk on a connected graph with positive degrees, with written out. Real-valued bounds on the natural-valued are direct inequalities on the cast, with no hidden rounding.
namespace MarkovMixing
/-- **Theorem 17.10** (Morris–Peres; LPW), the capstone of Chapter 17: for a
lazy irreducible chain (no reversibility required!),
`t_mix(ε) ≤ ⌈(2/Φ⋆²) log(1/(ε π_min))⌉` (the ceiling absorbs
integer rounding). -/
theorem evolving_sets_mixing {V : Type*} [Fintype V] [DecidableEq V] [Nonempty V]
(P : Matrix V V ℝ) (hP : IsStochastic P) (hirr : Irreducible P)
(hlazy : ∀ x : V, 2⁻¹ ≤ P x x)
(π : V → ℝ) (hπ : IsStationary P π)
(ε : ℝ) (hε : 0 < ε) (hε1 : ε < 1) :
(mixingTime P π ε : ℝ) ≤
⌈2 / bottleneckStar P π ^ 2 * Real.log (1 / (ε * ⨅ x : V, π x))⌉₊ := by
sorry
end MarkovMixingLet be an irreducible Markov chain on a finite state space that is lazy — at every state — with stationary distribution ; write . Reversibility is not assumed. The bottleneck constant (Mission IV) is
the worst conditional escape probability of a half-space at stationarity. For a tolerance , the mixing time is the first with , where is the total variation distance.
The theorem (Theorem 17.10, Morris–Peres; Levin–Peres–Wilmer — the capstone of Chapter 17) asserts: for every ,
(the ceiling absorbs the rounding of the real-valued bound to an integer time).
For reversible chains this recovers the Cheeger-route bound of Mission VII — but no reversibility is needed, which is the theorem's point: geometry controls mixing for every lazy chain. The proof analyzes the evolving-set process of this mission: laziness keeps the thresholds tame, the bottleneck constant forces a per-step multiplicative decay of , and the identity converts that decay into total-variation mixing.
No open leaves. Every sub-goal is proved or awaiting decomposition.