Cutoff at the entropic time for random walks on covered expander graphs

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 $d/((d-2)\log (d-1))\log n$. Such a bound is obtained by comparing the walk on $G_n$ to the walk on the infinite $d$-regular tree. If one can map another infinite transitive graph onto $G_n$, then we can improve the strategy by using a comparison with the random walk on this transitive graph (instead of that of the regular tree), and we obtain a lower bound of the form $1/h\log n$, where $h$ is the entropy rate associated with the walk on the transitive graph. We call this the entropic lower bound. It was recently proved that in the case of the tree, this entropic lower bound is sharp when graphs have minimal spectral radius and thus that in that case the random walk exhibit cutoff at the entropic time. In this paper, we provide a generalization of the result by providing a sufficient condition on the spectra the random walks on $G_n$ under which the random walk exhibit 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 non-reversible walks).

arXiv comment45 pages, non-reversible random walks added, accepted for publication in Journal of the Institute of Mathematics of Jussieu

References in corpus (9)

• Non-backtracking random walks mix faster
• Cutoff phenomena for random walks on random regular graphs
• Eigenvalues of random lifts and polynomials of random permutation matrices
• Asymptotic entropy and green speed for random walks on countable groups
• Characterization of cutoff for reversible Markov chains
• Random matrices, non-backtracking walks, and orthogonal polynomials
• A strengthening and a multipartite generalization of the Alon-Boppana-Serre Theorem
• On the computation of spectra in free probability
• Cutoff for Ramanujan graphs via degree inflation

Cited by in corpus (3)

• Cutoff on Graphs and the Sarnak-Xue Density of Eigenvalues
• Cutoff for random walk on random graphs with a community structure
• Mixing trichotomy for random walks on directed stochastic block models