The Convergence Theorem of Mission II says an irreducible aperiodic chain mixes geometrically, but with constants coming from a crude Doeblin decomposition — useless for actual chains, whose state spaces are exponentially large. Chapters 5–6 of Levin–Peres–Wilmer, Markov Chains and Mixing Times (AMS, 2009) develop the two classic probabilistic techniques that give useful upper bounds: coupling — run two copies of the chain jointly so that they meet quickly, and read a TV bound off the meeting time — and strong stationary times — random times at which the chain is exactly stationary, independent of the time. The flagship application is the top-to-random shuffle: repeatedly take the top card of a deck of cards and reinsert it at a uniform position; the deck is well mixed after shuffles, with error at most .
A Markovian coupling of a chain (with the stay-together convention (5.2)) is a chain on pairs whose coordinate marginals are both and which moves diagonal states to diagonal states. The coupling time is the hitting time of the diagonal; its tails are expressed with the trajectory calculus of Mission I.
A randomized stopping time is presented by its stopping rule: for each time and trajectory prefix , a number , the conditional probability of stopping at given the trajectory so far and no earlier stop. A strong stationary time for the chain started at is an almost surely finite such with
i.e. independent of . The separation distance is .
The mission also fixes the concrete chains it bounds: the lazy walk on the discrete torus , the Metropolis chain on proper -colorings of a graph, the Glauber dynamics of the hardcore model with fugacity , and the top-to-random shuffle on decks of cards (states are arrangements, i.e. permutations; position is the top).
Let ,
for the top-to-random shuffle on cards — display (6.16) of the book, the chapter's flagship bound, proved by combining the strong stationary time with the coupon collector tail of Mission I.
Theorem 5.2 and Corollary 5.3 (the coupling bound: , hence ); Theorem 5.5 ( for the lazy torus walk); Theorem 5.7 (Metropolis colorings, : mixing in ); Theorem 5.8 (hardcore Glauber, : mixing in ); Proposition 6.1 with Example 6.7 ( is a strong stationary time); Lemma 6.11 (); Lemma 6.13 (); Proposition 6.10 ().
The results. The coupling bound is the single most used upper-bound technique in the subject: Missions VIII (path coupling), IX (Ising) and XI (cutoff examples) all instantiate it. Strong stationary times and separation distance return in Mission XI (separation cutoff) and underlie perfect sampling in Mission XIII. The three concrete bounds (torus, colorings, hardcore) are the standard first applications and give the first polynomial mixing results of the series; the colorings and hardcore chains are the objects of intense ongoing research on sampling thresholds.
Formalizing them. Nothing here exists in Mathlib. The novel infrastructure is the stopping-rule formalization of randomized stopping times over trajectory prefixes — measure-theory-free, but expressive enough for the strong stationarity identity — and the Markovian-coupling predicate on pair chains. Both are reused later in the series (Matthews method, cutoff, CFTP).
The coupling bound itself is short once Proposition 4.7 (Mission II) is available; the work is in the applications. For the torus, the coordinatewise coupling requires assembling one-dimensional couplings and bounding the coupling time by a sum of one-dimensional meeting times — the formal bookkeeping of "couple coordinate by coordinate" is the real cost, and the constant absorbs it. For Theorem 5.7 and 5.8 the argument is a grand coupling over all colorings/configurations simultaneously; the formal statements quantify only over the resulting bound, but a solver must build the coupling. For Proposition 6.1, the crux is the induction "given cards under the original bottom card, all orders are equally likely" — an exchangeability argument that must be carried through the stopping-rule encoding. Lemma 6.11 is where the definition of strong stationarity does its work; the naive attempt to prove Proposition 6.10 directly from the coupling characterization fails, which is exactly why separation distance is introduced.
Couplings of chains are transition matrices on with marginal conditions stated row by row; the stay-together convention is part of the predicate, matching (5.2). Stopping rules take the trajectory prefix (which includes the starting state), so times "depending on the starting position" are covered; strong stationarity packages the stopping rule bounds, almost-sure finiteness (), and the product identity. The colorings chain lives on the subtype of proper colorings; the hardcore chain is the Glauber dynamics of Mission II restricted to the subtype of hardcore configurations (transitions never leave it). Mixing-time upper bounds carry an explicit for integer rounding where the book's real-valued display would otherwise be false for the integer-valued . The torus statement fixes ; for near the display is false as stated in the book.
Welcome contributions: interface lemmas between setAvoidTailProb of the pair chain and the two coordinates; the taboo-matrix form of coupling-time tails; exchangeability infrastructure for the deck chains (reused in Mission V).
namespace MarkovMixing
/-- **§6.5.3, Eq. (6.16)** (LPW), the capstone of Chapters 5–6: for the
top-to-random shuffle on `n` cards,
`d(⌈n log n + α n⌉) ≤ e^{-α}` for every `α > 0`. -/
theorem top_to_random_mixing (n : ℕ) (hn : 2 ≤ n) (α : ℝ) (hα : 0 < α) :
distStationary (topToRandom n) (uniformDist (Equiv.Perm (Fin n)))
⌈(n : ℝ) * Real.log n + α * n⌉₊ ≤ Real.exp (-α) := by
sorry
end MarkovMixing
Consider the top-to-random shuffle of a deck of cards: at each step the top card is removed and reinserted at a uniformly random position. Its stationary distribution is uniform over all orderings. Write for the law of the deck after shuffles started from the ordering , for the total variation distance, and for the worst-case distance to uniformity.
The theorem (§6.5.3, display (6.16) of Levin–Peres–Wilmer, the capstone of Chapters 5–6) asserts: for every ,
After shuffles plus any linear-in- margin, the deck is exponentially close to uniform in the margin: top-to-random shuffles suffice. The proof runs through the strong stationary time of this mission — one shuffle after the original bottom card surfaces — whose tail is controlled by the coupon-collector bounds of Mission I.
No open leaves. Every sub-goal is proved or awaiting decomposition.