Portal de Periódicos da CAPES

Artigo Acesso aberto Produção Nacional Revisado por pares

BIBTEX RIS

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

2016; Institute of Mathematical Statistics; Volume: 21; Issue: none Linguagem: Inglês

10.1214/16-ejp4687

1083-6489

Jonathan Hermon, Hubert Lacoin, Yuval Peres,

Algorithms and Data Compression

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.