Cutoff is a step-function profile
ProvedMarkovMixing.cutoff_iff_stepConsider a family of chains: for each , an irreducible and aperiodic chain on a finite state space with stationary distribution — irreducible and aperiodic so that it does converge to and its mixing times are genuine finite times. Write for the worst-case total variation distance to stationarity (), , and . The family has a cutoff when for every : 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 time scale: the family has a cutoff if and only if for every
- implies — just before the mixing time the family is asymptotically unmixed;
- implies — just after it, asymptotically mixed.
This equivalence is the working definition of cutoff in practice: sharp upper and lower bounds on at times (as produced for the hypercube in this mission) are exactly what the right-hand side asks for.
import Definitions.Def_mm_cutoff
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