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

DOI10.1214/16-EJP4687zbMATH Open1345.60077arXiv1508.03913MaRDI QIDQ303559FDOQ303559

Authors: Jonathan Hermon, Hubert Lacoin, Yuval Peres 

Publication date: 22 August 2016

Published in: Electronic Journal of Probability (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1508.03913

Recommendations

• Total variation cutoff in birth-and-death chains
• Cutoff for Markov chains: some examples and applications
• Characterization of cutoff for reversible Markov chains
• On sensitivity of mixing times and cutoff
• Characterization of cutoff for reversible Markov chains

zbMATH Keywords

cutoffMarkov chainsmixing timetotal variation distancelazy simple random walkseparation distance

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Sums of independent random variables; random walks (60G50)

Cited In (12)

• Total variation cutoff in a tree
• Characterization of cutoff for reversible Markov chains
• On sensitivity of mixing times and cutoff
• Antiduality and Möbius monotonicity: generalized coupon collector problem
• A product chain without cutoff
• Cutoff profile of ASEP on a segment
• Cut-off phenomenon for converging processes in the sense of \(\alpha\)-divergence measures
• Sensitivity of mixing times of Cayley graphs
• On the separation cut-off phenomenon for Brownian motions on high dimensional spheres
• A spectral characterization for concentration of the cover time
• Universality of cutoff for graphs with an added random matching
• Mixing time of the adjacent walk on the simplex

This page was built for publication: Total variation and separation cutoffs are not equivalent and neither one implies the other

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q303559)