Characterization of cutoff for reversible Markov chains

  • Jonathan Hermon | MSR

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

Speaker Details

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.

    • Portrait of Jeff Running

      Jeff Running

Series: Microsoft Research Talks