A technical report on hitting times, mixing and cutoff

Jonathan Hermon

Published 2015-01-08Version 1

In this work we give a characterization of mixing and cutoff for reversible Markov chains with finite state spaces starting from an arbitrary starting distribution in terms of hitting times of sets which are "worst" in some sense. We show that for a fixed initial distribution the "worst" sets can be taken to be sets which are "worst in expectation". We also give a surprising counter-example which demonstrates that in general cutoff cannot be characterized in terms of the hitting time distribution of sets which are worst in expectation (as opposed to cutoff from a fixed initial distribution). In addition, we prove a decomposition theorem which asserts that for reversible Markov chains on a finite state space, mixing with respect to some relaxations of $L^{\infty}$-mixing and separation-mixing are in fact equivalent to total variation-mixing. We also prove some inequalities between the expected hitting times of sets of different sizes which are "worst in expectation".