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)α∈(0,1). We also give general bounds on the total variation distance of a reversible chain at time tt in terms of the probability that some “worst” set of stationary measure at least αα was not hit by time tt. 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 ∞∞.
This work was greatly motivated by the aforementioned results. It is natural to ask whether ) could be further refined so that the cutoff phenomenon could be characterized in terms of concentration of the hitting times of a sequence of sets @math which attain the maximum in the definition of @math (starting from the worst initial states). Corollary 1.5 in @cite_8 asserts that this is indeed the case in the transitive setup. More generally, Theorem 2 in @cite_8 asserts that this is indeed the case for any fixed sequence of initial states @math if one replaces @math and @math by @math and @math (i.e. when the hitting times and the mixing times are defined only w.r.t. these starting states). Alas, Proposition 1.6 in @cite_8 asserts that in general cutoff could not be characterized in this manner.
@cite_8
1593631888
Consider a sequence of continuous-time irreducible reversible Markov chains and a sequence of initial distributions, @math . The sequence is said to exhibit @math -cutoff if the convergence to stationarity in total variation distance is abrupt, w.r.t. this sequence of initial distributions. In this work we give a characterization of @math -cutoff for an arbitrary sequence of initial distributions @math (in the above setup). Our characterization is expressed in terms of hitting times of sets which are "worst" w.r.t. @math . Consider a Markov chain on @math whose stationary distribution in @math . Let @math be the expected hitting time of the worst set of size at least @math . It was recently proved by Peres and Sousi and independently by Oliveira that @math captures the order of the mixing time. In this work we further refine this connection and show that @math -cutoff can be characterized in terms of concentration of hitting times (starting from @math ) of sets which are worst in expectation w.r.t. @math . Conversely, we construct a counter-example which demonstrates that in general cutoff (as opposed to cutoff w.r.t. a certain sequence of initial distributions) cannot be characterized in this manner. Finally, we also prove that there exists an absolute constant @math such that for every Markov chain @math , for all @math , where @math is the inverse of the spectral gap of the chain.