CHARACTERIZATION OF CUTOFF FOR REVERSIBLE MARKOV CHAINS

Authors
Basu, Riddhipratim 
Peres, Yuval 

Loading...
Thumbnail Image
Type
Article
Change log
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 α, for some α∈(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 α 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.

Publication Date
2017
Online Publication Date
2017-05-01
Acceptance Date
Keywords
Cutoff, mixing-time, finite reversible Markov chains, hitting times, trees, maximal inequality
Journal Title
ANNALS OF PROBABILITY
Journal ISSN
0091-1798
Volume Title
45
Publisher
Institute of Mathematical Statistics