Algorithms & Randomness Center (ARC)

Jonathan Hermon (Cambridge)

Monday, November 27, 2017

Klaus 1116 East - 11:00 am

Title:  A characterization of $L_p$ mixing, cutoff and hypercontractivity via maximal inequalities and hitting times.

Abstract:  (joint work with Yuval Peres): 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 uniform ($L_{\infty}$) mixing time (UMT), (there is neither a sharp bound nor one possessing a probabilistic interpretation). We show that the UMT 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_{LS}$, as a weighted version of the spectral gap. This characterization yields a probabilistic interpretation of $c_{LS}$ in terms of a hitting time version of hypercontractivity. As applications, we (1) resolve a conjecture of Kozma by showing that the UMT is not robust under rough isometries (even in the bounded degree, unweighted setup), (2) show that for weighted nearest neighbor random walks on trees, the UMT is robust under bounded perturbations of the edge weights, and (3) Establish a general robustness result under addition of weighted self-loops.

--------------------------------------

Speaker's Webpage

Videos of recent talks are available at: https://smartech.gatech.edu/handle/1853/46836

Click here to subscribe to the seminar email list: arc-colloq@cc.gatech.edu