Campuses:

Characterization of cutoff for reversible Markov chains

Wednesday, April 15, 2015 - 2:00pm - 2:50pm
Keller 3-180
Yuval Peres (Microsoft)
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, Oliviera, Sousi and the speaker established a less precise connection between hitting times and mixing). We deduce 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 Jonathan Hermon.)