Total variation and separation cutoffs are not equivalent and neither one implies the other


Type
Article
Change log
Authors
Lacoin, Hubert 
Peres, Yuval 
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