Portal de Periódicos da CAPES

Characterization of cutoff for reversible Markov chains

2017; Institute of Mathematical Statistics; Volume: 45; Issue: 3 Linguagem: Inglês

10.1214/16-aop1090

2168-894X

Riddhipratim Basu, Jonathan Hermon, Yuval Peres,

Gene Regulatory Network Analysis

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 $\alpha\in(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 product of their spectral gaps and their (lazy) mixing-times tends to $\infty$.