Repository logo
 

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

Published version
Peer-reviewed

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