Cutoff for Markov chains

A sequence of chains exhibits cutoff when its distance from stationarity drops from near one to near zero in a time window negligible compared with its mixing-time scale.

The ratio convention for cutoff for Markov chains requires $t_{\mathrm{mix}}^{(n)}(\epsilon )/t_{\mathrm{mix}}^{(n)}(1-\epsilon )\to 1$ for every fixed $0<\epsilon <1/2$, with positive denominators eventually. Equivalently, any two fixed levels have asymptotically equal mixing times. This convention permits a bounded-time jump; definitions which additionally require diverging mixing times exclude such a jump. For nonlazy simple random walk on the complete graph $K_n$, every fixed-level mixing time is eventually one.

For finite irreducible Markov chains that are aperiodic Markov chains and reversible Markov chains, the ratio definition of cutoff and $T_n=t_{\mathrm{mix}}^{(n)}(1/4)\to \infty$ imply the Peres product condition, with ${\gamma }_n=1-{\lambda }_{2,n}$. If ${\gamma }_n{T}_n\le B$ on a subsequence, then ${\gamma }_{\ast ,n}\le {\gamma }_n$ and the eigenvalue lower bound for total variation mixing giveFor sufficiently small fixed $\epsilon$, this contradicts the limit one forced by cutoff for Markov chains. The same argument proves the stronger conclusion ${\gamma }_{\ast ,n}{T}_n\to \infty$.

The random-to-top shuffle chooses one uniformly random card and moves it to the top of the deck. The time at which every card has been chosen is a strong stationary time, yielding cutoff at $n\log n$ with a window of order $n$.

The top-to-random shuffle removes the top card and inserts it in a uniformly random position. Under the uniform measure on permutations it is the time reversal of the random-to-top card shuffle, so the two shuffles have the same total-variation mixing profile.

A sequence of chains exhibits pre-cutoff if there are constants $0<A<B<\infty$ and times $t_n$ such that the worst-case distance tends to one at $A{t}_n$ and to zero at $B{t}_n$. For reversible chains, the product condition $t_{\mathrm{rel}}=o(t_{\mathrm{mix}})$ is necessary for pre-cutoff.

For $\tilde{P}=(1-a)P+a\Pi$, where every row of $\Pi$ equals the stationary distribution $\pi$,The perturbation superposes gradual exponential mixing on the original profile and can destroy pre-cutoff.

A shift-refresh chain cyclically moves a pointer through the coordinates of a bit vector and replaces the visited bit by an independent fair bit. Once the pointer walk has visited every residue, all coordinates have been refreshed, giving a strong stationary time.