A characterization of L2 mixing and hypercontractivity via hitting times and maximal inequalities

Change log
Peres, Y 

There are several works characterizing the total-variation mixing time of a reversible Markov chain in term of natural probabilistic concepts such as stopping times and hitting times. In contrast, there is no known analog for the L2 mixing time, τ2 (while there are sophisticated analytic tools to bound $ \tau_2$, in general they do not determine τ2 up to a constant factor and they lack a probabilistic interpretation). In this work we show that τ2 can be characterized up to a constant factor using hitting times distributions. We also derive a new extremal characterization of the Log-Sobolev constant, cLS, as a weighted version of the spectral gap. This characterization yields a probabilistic interpretation of cLS in terms of a hitting time version of hypercontractivity. As applications of our results, we show that (1) for every reversible Markov chain, τ2 is robust under addition of self-loops with bounded weights, and (2) for weighted nearest neighbor random walks on trees, $\tau_2 $ is robust under bounded perturbations of the edge weights.

Mixing-time, Finite reversible Markov chains, Maximal inequalities, Hitting times, Hypercontractivity, Log-Sobolov inequalities, Relative entropy, Robustness of mixing times
Journal Title
Probability Theory and Related Fields
Conference Name
Journal ISSN
Volume Title
Springer Science and Business Media LLC