Repository logo
 

A technical report on hitting times, mixing and cutoff

Published version
Peer-reviewed

Type

Article

Change log

Authors

Abstract

Consider a sequence of continuous-time irreducible reversible Markov chains and a sequence of initial distributions, μn. Instead of performing a worst case analysis, one can study the rate of convergence to the stationary distribution starting from these initial distributions. The sequence is said to exhibit (total variation) μn-cutoff if the convergence to stationarity in total variation distance is abrupt, w.r.t.~this sequence of initial distributions.

In this work we give a characterization of μn-cutoff (and also of total-variation mixing) for an arbitrary sequence of initial distributions μn (in the above setup). Our characterization is expressed in terms of hitting times of sets which are ``worst" (in some sense) w.r.t.~μn.

Consider a Markov chain on Ω whose stationary distribution is π. Let tH(α):=maxxΩ,AΩ:π(A)≥αEx[TA] be the expected hitting time of the set of stationary probability at least α which is ``worst in expectation" (starting from the worst starting state). The connection between $t_{\mathrm{H}}(\cdot) $ and the mixing time of the chain was previously studied by Aldous and later by Lov'asz and Winkler, and was recently refined by Peres and Sousi and independently by Oliveira. In this work we further refine this connection and show that μn-cutoff can be characterized in terms of concentration of hitting times (starting from μn) of sets which are worst in expectation w.r.t.~μn. Conversely, we construct a counter-example which demonstrates that in general cutoff (as opposed to cutoff w.r.t.~a certain sequence of initial distributions) cannot be characterized in this manner.

Finally, we also prove that there exists an absolute constant C such that for any Markov chain ϵ(t\h(ϵ)−t\h(1−ϵ))≤C\rel|logϵ|, for all 0<ϵ<1/2, where \rel is the inverse of the spectral gap of the additive symmetrization \half(P+P∗).

Description

Keywords

Mixing-time, hitting times, cutoff, finite reversible Markov chains, maximal inequality, counter-example

Journal Title

ALEA : Latin American Journal of Probability and Mathematical Statistics

Conference Name

Journal ISSN

1980-0436
1980-0436

Volume Title

15

Publisher

Instituto Nacional de Matemática Pura e Aplicada
Sponsorship
Engineering and Physical Sciences Research Council (EP/L018896/1)