Characterization of cutoff for reversible Markov chains

Опубликовано 21 июня 2016, 19:16

A sequence of Markov chains is said to exhibit cutoff if the convergence to stationarity in total variation distance is abrupt. We prove a necessary and sufficient condition for cutoff in reversible lazy chains in terms of concentration of hitting time of certain sets of large stationary measure. (Previous works of Aldous, Peres, Sousi and Oliviera established a less precise connection between hitting times and mixing). As an application, we show that a sequence of lazy Markov chains on finite trees exhibits a cutoff iff the ratio of their relaxation-times and their mixing-times tends to 0. (Joint work with Riddhi Basu and Yuval Peres.)