CUTOFF AT THE ENTROPIC TIME FOR RANDOM WALKS ON COVERED EXPANDER GRAPHS
- 9 February 2021
- journal article
- research article
- Published by Cambridge University Press (CUP) in Journal of the Institute of Mathematics of Jussieu
- Vol. 21 (5) , 1571-1616
Abstract
It is a fact simple to establish that the mixing time of the simple random walk on a d-regular graph $G_n$ with n vertices is asymptotically bounded from below by $\frac {d }{d-2 } \frac {\log n}{\log (d-1)}$ . Such a bound is obtained by comparing the walk on $G_n$ to the walk on d-regular tree $\mathcal{T}_d$ . If one can map another transitive graph $\mathcal{G} $ onto $G_n$ , then we can improve the strategy by using a comparison with the random walk on $\mathcal{G} $ (instead of that of $\mathcal{T} _d$ ), and we obtain a lower bound of the form $\frac {1}{\mathfrak{h} }\log n$ , where $\mathfrak{h} $ is the entropy rate associated with $\mathcal{G} $ . We call this the entropic lower bound.It was recently proved that in the case $\mathcal{G} =\mathcal{T} _d$ , this entropic lower bound (in that case $\frac {d }{d-2 } \frac {\log n}{\log (d-1)}$ ) is sharp when graphs have minimal spectral radius and thus that in that case the random walk exhibits cutoff at the entropic time. In this article, we provide a generalisation of the result by providing a sufficient condition on the spectra of the random walks on $G_n$ under which the random walk exhibits cutoff at the entropic time. It applies notably to anisotropic random walks on random d-regular graphs and to random walks on random n-lifts of a base graph (including nonreversible walks).
Keywords
All Related Versions
This publication has 38 references indexed in Scilit:
- A strengthening and a multipartite generalization of the Alon-Boppana-Serre theoremProceedings of the American Mathematical Society, 2010
- Asymptotic entropy and Green speed for random walks on countable groupsThe Annals of Probability, 2008
- Weighted expanders and the anisotropic Alon–Boppana theoremEuropean Journal of Combinatorics, 2004
- Relative expanders or weakly relatively Ramanujan graphsDuke Mathematical Journal, 2003
- Random Graph Coverings I: General Theory and Graph ConnectivityCombinatorica, 2002
- Harmonic analysis for anisotropic random walks on homogeneous treesMemoirs of the American Mathematical Society, 1994
- Random Walks on Discrete Groups: Boundary and EntropyThe Annals of Probability, 1983
- Random walks on finite groups and rapidly mixing markov chains1983
- Computing Norms in Group C ∗ -AlgebrasAmerican Journal of Mathematics, 1976
- On a Set of PolynomialsAnnals of Mathematics, 1930