A technical report on hitting times, mixing and cutoff

Original · EN

Consider a sequence of continuous-time irreducible reversible Markov chains and a sequence of initial distributions, μₙ. The sequence is said to exhibit μₙ-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 μₙ-cutoff for an arbitrary sequence of initial distributions μₙ (in the above setup). Our characterization is expressed in terms of hitting times of sets which are "worst" w.r.t. μₙ. Consider a Markov chain on Ω whose stationary distribution in π. Let tₕ(α):=ₓ ∈ Ω,ₐ ⊂ Ω:π₍ₐ₎ ≥ αEₓ[Tₐ] be the expected hitting time of the worst set of size at least α. It was recently proved by Peres and Sousi and independently by Oliveira that tₕ(1/4) captures the order of the mixing time. In this work we further refine this connection and show that μₙ-cutoff can be characterized in terms of concentration of hitting times (starting from μₙ) of sets which are worst in expectation w.r.t. μₙ. 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 C such that for every Markov chain ε(tₕ(ε)-tₕ(1-ε)) ≤ Ctrel | ε|, for all 0< ε< 1/2, where trel is the inverse of the spectral gap of the chain.