Repository logo
 

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

Accepted version
Peer-reviewed

Loading...
Thumbnail Image

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