Characterization of cutoff for reversible Markov chains


August 22, 2014


Jonathan Hermon




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.)


Jonathan Hermon

Jonathan is a graduate student in the Department of Statistics at UC Berkeley and currently an intern at MSR. His advisor is Allan Sly. His research is in discrete probability theory, and is mostly related to mixing times of markov chains, random graphs and percolation.