The product condition is necessary for cutoff
ProvedMarkovMixing.cutoff_necessaryConsider a family of chains on finite state spaces, each irreducible and aperiodic, each reversible with respect to its stationary distribution (detailed balance ). For each chain: is the worst-case total variation distance, with ; among the eigenvalues (real with , ), is the largest absolute value of an eigenvalue , and is the relaxation time (Mission VII). The family has a cutoff when for every .
The theorem (Proposition 18.4 of Levin–Peres–Wilmer) asserts: if the mixing times grow to infinity but stay comparable to the relaxation times — for a fixed constant — then the family has no cutoff.
The product condition is therefore necessary for cutoff. The reason: the relaxation-time lower bound of Mission VII gives , so if is proportional to , shrinking inflates beyond any bound — an eigenfunction decaying only like keeps the collapse from being abrupt. Whether the product condition is also sufficient for reversible families was a famous question of Peres; it fails in general, which makes this necessary direction the definitive elementary statement.
import Definitions.Def_mm_cutoff
namespace MarkovMixing
/-- **Proposition 18.4** (LPW): a necessary condition for (pre-)cutoff: for
a sequence of reversible irreducible aperiodic chains, if `t_mix/t_rel`
stays bounded, then even the weak cutoff ratio fails — the mixing-time
ratios `t_mix(ε)/t_mix(1−ε)` do not tend to `1` for small `ε`; in
particular the sequence has no cutoff. -/
theorem cutoff_necessary {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))
(hrev : ∀ n, DetailedBalance (P n) (π n))
(C : ℝ) (hC : 0 < C)
(hbound : ∀ n, (tMix (P n) (π n) : ℝ) ≤ C * relaxationTime (P n))
(hgrow : Filter.Tendsto (fun n => tMix (P n) (π n)) Filter.atTop Filter.atTop) :
¬HasCutoff P π := by
sorry
end MarkovMixing