Cutoff on all Ramanujan graphs

Eyal Lubetzky, Yuval Peres

Published 2015-07-16Version 1

The cutoff phenomenon for simple random walk, a sharp transition in its $L^1$-convergence to equilibrium, was conjectured by the second author in 2004 to hold on every family of transitive expanders, yet this was not verified nor refuted on any single example to date. We show that on every Ramanujan graph $G$, simple random walk exhibits cutoff: when $G$ has $n$ vertices and degree $d$, the total-variation distance of the walk from the uniform distribution at time $t=\frac{d}{d-2}\log_{d-1} n + s\sqrt{\log n}$ is asymptotically $\mathbb{P}(Z > c\, s)$ where $Z$ is a standard normal variable and $c=c(d)$ is an explicit constant. Consequently, for every vertex $x$ in $G$, its distance from $n-o(n)$ of the vertices is asymptotically $\log_{d-1} n$.