Total variation and separation cutoffs are not equivalent and neither one implies the other. (English) Zbl 1345.60077

Summary: The cutoff phenomenon describes the case when an abrupt transition occurs in the convergence of a Markov chain to its equilibrium measure. There are various metrics which can be used to measure the distance to equilibrium, each of which corresponding to a different notion of cutoff. The most commonly used are the total variation and the separation distances. In this note, we prove that the cutoffs for these two distances are not equivalent by constructing several counterexamples which display cutoff in the total variation but not in the separation distance and with the opposite behavior, including a lazy simple random walk on a sequence of uniformly bounded degree expander graphs. These examples give a negative answer to a question of Ding, Lubetzky and Peres.


60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
60G50 Sums of independent random variables; random walks
Full Text: DOI arXiv Euclid