Abstract
Many randomized algorithms employ Markov chains, and the mixing time of the chain is often the main term in the running time. A sequence of Markov chains is said to exhibit cutoff if the total variation distance to stationarity decreases from near 1 to near zero within a short time window (negligible to the mixing time). E.g. lazy walk on the hypercube exhibits cutoff, but lazy walk on the cycle does not. A necessary condition for cutoff is that the product of the spectral gap and the mixing time tends to infinity along the sequence; we prove that this condition is also sufficient for a lazy reversible chain, provided that the hitting times of certain large sets are concentrated. The proof is based on a maximal inequality that also yields sharp bounds for surprise probabilities in reversible chains.
Talk based on joint works with Riddhi Basu and Jonathan Hermon http://arxiv.org/abs/1409.3250 and with James Norris and Alex Zhai http://arxiv.org/abs/1408.0822, both to appear in SODA 2015.