Prove2Me
Navigate
DiscoverCollectionsFormalpediaBlogsUsersMomentumMy Missions+
Prove2Me
⌕
Log in
← Formalpedia

Cutoff is a step-function profile

Proved
MarkovMixing.cutoff_iff_step

by Shuze Chen · Aug 22, 2026 · Mathlib 0df444a (Lean v4.33.1)

markov-chainsmixing-timesprobability

Consider a family of chains: for each nnn, an irreducible and aperiodic chain P(n)P^{(n)}P(n) on a finite state space with stationary distribution πn\pi_nπn​ — irreducible and aperiodic so that it does converge to πn\pi_nπn​ and its mixing times are genuine finite times. Write dn(t)=max⁡x∥P(n)t(x,⋅)−πn∥TVd_n(t)=\max_x\|P^{(n)t}(x,\cdot)-\pi_n\|_{TV}dn​(t)=maxx​∥P(n)t(x,⋅)−πn​∥TV​ for the worst-case total variation distance to stationarity (∥μ−ν∥TV=max⁡A∣μ(A)−ν(A)∣\|\mu-\nu\|_{TV}=\max_A|\mu(A)-\nu(A)|∥μ−ν∥TV​=maxA​∣μ(A)−ν(A)∣), tmix(n)(ε)=min⁡{t:dn(t)≤ε}t^{(n)}_{\mathrm{mix}}(\varepsilon)=\min\{t:d_n(t)\le\varepsilon\}tmix(n)​(ε)=min{t:dn​(t)≤ε}, and tmix(n)=tmix(n)(1/4)t^{(n)}_{\mathrm{mix}}=t^{(n)}_{\mathrm{mix}}(1/4)tmix(n)​=tmix(n)​(1/4). The family has a cutoff when tmix(n)(ε)/tmix(n)(1−ε)→1t^{(n)}_{\mathrm{mix}}(\varepsilon)/t^{(n)}_{\mathrm{mix}}(1-\varepsilon)\to1tmix(n)​(ε)/tmix(n)​(1−ε)→1 for every 0<ε<10<\varepsilon<10<ε<1: the times to mix well and to mix barely agree to leading order.

The theorem (Lemma 18.1 of Levin–Peres–Wilmer) asserts that cutoff is equivalent to the distance profile converging to a step function on the tmixt_{\mathrm{mix}}tmix​ time scale: the family has a cutoff if and only if for every c>0c>0c>0

  1. c<1c<1c<1 implies dn(⌊c tmix(n)⌋)→1d_n\bigl(\lfloor c\,t^{(n)}_{\mathrm{mix}}\rfloor\bigr)\to1dn​(⌊ctmix(n)​⌋)→1 — just before the mixing time the family is asymptotically unmixed;
  2. c>1c>1c>1 implies dn(⌊c tmix(n)⌋)→0d_n\bigl(\lfloor c\,t^{(n)}_{\mathrm{mix}}\rfloor\bigr)\to0dn​(⌊ctmix(n)​⌋)→0 — just after it, asymptotically mixed.

This equivalence is the working definition of cutoff in practice: sharp upper and lower bounds on dnd_ndn​ at times c tmixc\,t_{\mathrm{mix}}ctmix​ (as produced for the hypercube in this mission) are exactly what the right-hand side asks for.

Preamble
import Definitions.Def_mm_cutoff
Formal statement
namespace MarkovMixing

/-- **Lemma 18.1** (LPW): a sequence of chains has a cutoff if and only if,
on the time scale of `t_mix`, the distance to stationarity approaches a step
function: `d_n(⌊c t_mix⌋) → 1` for `c < 1` and `→ 0` for `c > 1`.

Each chain in the sequence is hypothesized irreducible and aperiodic. LPW
speak of "the mixing time for the `n`-th chain", taking for granted that
`t_mix` is a genuine finite time, which is to say that `d_n(t) → 0`;
`mixingTime` is an infimum over the naturals, and for a chain that never comes
within `ε` of stationarity that infimum is over an empty set and reports the
junk value `0`. -/
theorem cutoff_iff_step {V : ℕ → Type*} [∀ n, Fintype (V n)]
    [∀ n, DecidableEq (V n)] [∀ n, Nonempty (V n)]
    (P : ∀ n, Matrix (V n) (V n) ℝ) (π : ∀ n, V n → ℝ)
    (hP : ∀ n, IsStochastic (P n)) (hirr : ∀ n, Irreducible (P n))
    (hap : ∀ n, Aperiodic (P n)) (hπ : ∀ n, IsStationary (P n) (π n)) :
    HasCutoff P π ↔
      ∀ c : ℝ, 0 < c →
        (c < 1 → Filter.Tendsto
          (fun n => distStationary (P n) (π n) ⌊c * tMix (P n) (π n)⌋₊)
          Filter.atTop (nhds 1)) ∧
        (1 < c → Filter.Tendsto
          (fun n => distStationary (P n) (π n) ⌊c * tMix (P n) (π n)⌋₊)
          Filter.atTop (nhds 0)) := by
  sorry

end MarkovMixing
Source
D. A. Levin, Y. Peres, E. L. Wilmer, Markov Chains and Mixing Times, AMS 2009, https://documents.epfl.ch/groups/i/ip/ipg/www/2013-2014/Random_Walks/markovmixing.pdf, Section 18.1, Lemma 18.1, p. 247

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paper
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me