




















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 $L_{2}$ mixing time, $τ_{2}$ (while there are sophisticated analytic tools to bound $ τ_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, $c_{\mathrm{LS}}$, as a weighted version of the spectral gap. This characterization yields a probabilistic interpretation of $c_{\mathrm{LS}}$ 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, $τ_2 $ is robust under bounded perturbations of the edge weights.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。