Return to Colloquia & Seminar listing
A characterization of cut-off in terms of smoothness and concentration of the hitting times of huge and tiny sets
Probability| Speaker: | Jonathan Hermon, University of California, Berkeley |
| Location: | 1147 MSB |
| Start time: | Wed, Jan 8 2014, 2:10PM |
A sequence of Markov chains is said to exhibit (total variation) cutoff if the convergence to stationarity in total variation distance is abrupt.
We show that a sequence of reversible Markov chains with finite state spaces exhibits cutoff if and only if for any alpha which does not tend to 0 or 1 too quickly, the hitting time of any "worst" set of stationary measure at least alpha is concentrated (around the mixing time). By worst we mean that this set has the maximal expected hitting time out of all the sets whose stationary measure are greater or equal to alpha. The expectation and concentration of the hitting time of any set are considered w.r.t. a starting state which is "worst" in some sense.
We also show that for a sequence of finite reversible transitive chains it suffices to have concentration of the hitting time of just one such "worst" set for each chain in the sequence in order for the sequence to exhibit cutoff and that the same holds in general under some additional assumptions. Our results are extended also to the case of pre-cutoff.
The talk is based on joint work with Riddhipratim Basu and Yuval Peres.