Characterization of cutoff for reversible Markov chains

Abstract

A sequence of Markov chains is said to exhibit (total variation) cutoff if the convergence to stationarity in total variation distance is abrupt. We consider reversible lazy chains. We prove a necessary and sufficient condition for the occurrence of the cutoff phenomena in terms of concentration of hitting time of "worst" (in some sense) sets of stationary measure at least $\alpha$, for some $\alpha \in (0,1)$. We also give general bounds on the total variation distance of a reversible chain at time $t$ in terms of the probability that some "worst" set of stationary measure at least $\alpha$ was not hit by time $t$. As an application of our techniques we show that a sequence of lazy Markov chains on finite trees exhibits a cutoff iff the ratio of their relaxation-times and their (lazy) mixing-times tends to 0.

Improved Theorem 3. Extended abstract appeared in SODA 2015

References in corpus (4)

• Separation cut-offs for birth and death chains
• Mixing and hitting times for finite Markov chains
• Tight inequalities among set hitting times in Markov chains
• The power of averaging at two consecutive time steps: Proof of a mixing conjecture by Aldous and Fill

Cited by in corpus (13)

• On sensitivity of uniform mixing times
• Frogs on trees?
• On sensitivity of mixing times and cutoff
• Cutoff at the entropic time for random walks on covered expander graphs
• The cutoff phenomenon in total variation for nonlinear Langevin systems with small layered stable noise
• The power of averaging at two consecutive time steps: Proof of a mixing conjecture by Aldous and Fill
• Sensitivity of mixing times of Cayley graphs
• A spectral characterization for concentration of the cover time
• Ergodicity bounds for stable Ornstein-Uhlenbeck systems in Wasserstein distance with applications to cutoff stability
• Limit Profile for Projections of Random Walks on Groups
• Cutoff thermalization for Ornstein-Uhlenbeck systems with small Lévy noise in the Wasserstein distance
• Cutoff for random walk on random graphs with a community structure
• Cutoff ergodicity bounds in Wasserstein distance for a viscous energy shell model with Lévy noise