= Pre-cutoff for Markov chains
A sequence of finite <irreducible Markov chain>[irreducible] Markov chains exhibits <pre-cutoff for Markov chains>[pre-cutoff] if there are constants $0<A<B<\infty$ and times $t_n$ such that its worst-case <total variation distance> satisfies
$$
d_n(\lfloor At_n\rfloor)\longrightarrow1,\qquad
d_n(\lfloor Bt_n\rfloor)\longrightarrow0.
$$
This only bounds the transition between two fixed multiples of a scale; <cutoff for Markov chains>[cutoff] requires the transition window to be negligible relative to the mixing scale.
For reversible <aperiodic Markov chain>[aperiodic] chains with $t_n\to\infty$, <pre-cutoff for Markov chains>[pre-cutoff] implies the product condition $t_{\mathrm{rel},n}=o(t_{\mathrm{mix},n}(1/4))$. In fact the analogous <Absolute relaxation time> must be negligible too. To see the mechanism, the two distance limits make $t_{\mathrm{mix},n}(1/4)$ comparable to $t_n$. If $r_n$ is the largest nontrivial <eigenvalue> modulus, the <Eigenvalue lower bound for total variation mixing> gives $d_n(t)\geq r_n^t/2$. The limit at $Bt_n$ forces $r_n^{\lfloor Bt_n\rfloor}\to0$, which implies $(1-r_n)t_n\to\infty$ when $t_n\to\infty$. The ordinary <spectral gap> is at least $1-r_n$, giving the ordinary product condition.
The diverging-scale hypothesis matters. Nonlazy <simple random walk> on the complete <graph> has $d_n(0)\to1$ and $d_n(1)=1/n\to0$, so the displayed <pre-cutoff for Markov chains>[pre-cutoff] convention holds on the bounded scale $t_n=1$, but its <Relaxation time> is not negligible relative to its <mixing time of a Markov chain>[mixing time].
Back to article page
