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

DOI10.1214/16-EJP4687MaRDI QIDQ303559zbMATH OpenFDO

Authors Jonathan Hermon, Hubert Lacoin, Yuval Peres

Publication date 22 August 2016

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

Full work available at URL https://arxiv.org/abs/1508.03913, https://projecteuclid.org/euclid.ejp/1469557137

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)

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.

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

Cited in

(12)

• Mixing time of the adjacent walk on the simplex
• 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

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)