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


Type
Article
Change log
Authors
Peres, Y 
Abstract

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.

Description
Keywords
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
0178-8051
1432-2064
Volume Title
170
Publisher
Springer Science and Business Media LLC