Characterization of cutoff for reversible Markov chains

DOI10.1137/1.9781611973730.119MaRDI QIDQ5363065zbMATH OpenOpenAlexFDO

Authors Riddhipratim Basu, Jonathan Hermon, Yuval Peres

Publication date 5 October 2017

Published in Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Continuous-time Markov processes on discrete state spaces (60J27) Applications of branching processes (60J85)

Abstract: A sequence of Markov chains is said to exhibit (total variation) cutoff if the convergence to stationarity in total variation distance is abrupt. We consider reversible lazy chains. We prove a necessary and sufficient condition for the occurrence of the cutoff phenomena in terms of concentration of hitting time of "worst" (in some sense) sets of stationary measure at least $alpha$, for some $alphain(0,1)$. We also give general bounds on the total variation distance of a reversible chain at time $t$ in terms of the probability that some "worst" set of stationary measure at least $alpha$ was not hit by time $t$. As an application of our techniques we show that a sequence of lazy Markov chains on finite trees exhibits a cutoff iff the ratio of their relaxation-times and their (lazy) mixing-times tends to 0.

Recommendations

• Characterization of cutoff for reversible Markov chains
• The \(L^{2}\)-cutoffs for reversible Markov chains
• The \(L^{2}\)-cutoff for reversible Markov processes
• A characterization of reversible Markov chains by a rotational representation
• Estimations pour les chaînes de Markov réversibles
• Limit profiles for reversible Markov chains
• On the Convergence of Reversible Markov Chains
• Transition probability estimates for reversible Markov chains
• Comparison theorems for reversible Markov chains

Cited in

(25)

• No cut-off phenomenon for the ``Insect Markov chain
• Cutoffs for product chains
• The \(L^{2}\)-cutoffs for reversible Markov chains
• Cutoff at the ``entropic time for sparse Markov chains
• On sensitivity of mixing times and cutoff
• Segregating Markov chains
• Characterization of cutoff for reversible Markov chains
• No cutoff in spherically symmetric trees
• Cutoff for the square plaquette model on a critical length scale
• The \(L^{2}\)-cutoff for reversible Markov processes
• A characterization of \(L_{2}\) mixing and hypercontractivity via hitting times and maximal inequalities
• Decay rates and cutoff for convergence and hitting times of Markov chains with countably infinite state space
• Cutoff for Markov chains: some examples and applications
• Total variation and separation cutoffs are not equivalent and neither one implies the other
• Cutoff for samples of Markov chains
• A technical report on hitting times, mixing and cutoff
• Surprise probabilities in Markov chains
• Comparison of cutoffs between lazy walks and Markovian semigroups
• Total variation cutoff in a tree
• Cutoff on trees is rare
• The varentropy criterion is sharp on expanders
• Cutoff for the logistic SIS epidemic model with self-infection
• Game dynamics and equilibrium computation in the population protocol model
• Restart perturbations for reversible Markov chains: trichotomy and pre-cutoff equivalence
• Total variation cutoff in birth-and-death chains

This page was built for publication: Characterization of cutoff for reversible Markov chains

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