Total variation and separation cutoffs are not equivalent and neither one implies the other
Published version
Peer-reviewed
Repository URI
Repository DOI
Change log
Authors
Abstract
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 cutoff for these two distances are not equivalent by constructing several counterexamples which display cutoff in total-variation but not in separation and with the opposite behavior, including 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.
Description
Keywords
Markov chains, mixing time, cutoff, counter example
Journal Title
ELECTRONIC JOURNAL OF PROBABILITY
Conference Name
Journal ISSN
1083-6489
Volume Title
21
Publisher
Institute of Mathematical Statistics