Random walks on random n-lifts of any irreducible weighted base graph with two oriented cycles mix at time h^{-1} log n with cutoff, h the universal-cover entropy.
Cutoff on all Ramanujan graphs
1 Pith paper cite this work. Polarity classification is still indexing.
abstract
We show that on every Ramanujan graph $G$, the 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. Furthermore, for all $1 \leq p \leq \infty$, $d$-regular Ramanujan graphs minimize the asymptotic $L^p$-mixing time for SRW among all $d$-regular graphs. Our proof also shows that, for every vertex $x$ in $G$ as above, its distance from $n-o(n)$ of the vertices is asymptotically $\log_{d-1} n$.
fields
math.PR 1years
2019 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
Cutoff for random lifts of weighted graphs
Random walks on random n-lifts of any irreducible weighted base graph with two oriented cycles mix at time h^{-1} log n with cutoff, h the universal-cover entropy.