Non-backtracking random walks mix faster

Abstract

We compute the mixing rate of a non-backtracking random walk on a regular expander. Using some properties of Chebyshev polynomials of the second kind, we show that this rate may be up to twice as fast as the mixing rate of the simple random walk. The closer the expander is to a Ramanujan graph, the higher the ratio between the above two mixing rates is. As an application, we show that if $G$ is a high-girth regular expander on $n$ vertices, then a typical non-backtracking random walk of length $n$ on $G$ does not visit a vertex more than $(1+o(1))\frac{\log n}{\log \log n}$ times, and this result is tight. In this sense, the multi-set of visited vertices is analogous to the result of throwing $n$ balls to $n$ bins uniformly, in contrast to the simple random walk on $G$, which almost surely visits some vertex $\Omega (\log n)$ times.

18 pages; 2 figures

Cited by in corpus (34)

• Random walks and diffusion on networks
• Spectral redemption: clustering sparse networks
• Statistical physics of inference: Thresholds and algorithms
• Percolation on sparse networks
• Cutoff phenomena for random walks on random regular graphs
• Mapping flows on hypergraphs
• Eigenvectors of the discrete Laplacian on regular graphs - a statistical approach
• Non-backtracking random walk
• Functional limit theorems for random regular graphs
• Ramanujan graphings and correlation decay in local algorithms
• Fast computation of matrix function-based centrality measures for layer-coupled multiplex networks
• Analysis of node2vec random walks on networks
• Spectral measures of factor of i.i.d. processes on vertex-transitive graphs
• Spectra of random regular hypergraphs
• Analytical results for the distribution of cover times of random walks on random regular graphs
• Cutoff at the entropic time for random walks on covered expander graphs
• Spectral theory of the non-backtracking Laplacian for graphs
• Analytical results for the distribution of first hitting times of random walks on random regular graphs
• An estimate for the average spectral measure of random band matrices
• Greedy Random Walk
• The distribution of first hitting times of non-backtracking random walks on Erdős-Rényi networks
• Markov chains on finite fields with deterministic jumps
• Efficient network exploration by means of resetting self-avoiding random walkers
• Cycle density in infinite Ramanujan graphs
• Factorized Graph Representations for Semi-Supervised Learning from Sparse Data
• Analysis of the susceptible-infected-susceptible epidemic dynamics in networks via the non-backtracking matrix
• Graph sampling by lagged random walk
• Exponential speedups for quantum walks in random hierarchical graphs
• Metapopulation models imply non-Poissonian statistics of interevent times
• Free flags over local rings and powering of high dimensional expanders
• Reversibility of the non-backtracking random walk
• Effects of concurrency on epidemic spreading in Markovian temporal networks
• The limit theorem with respect to the matrices on non-backtracking paths of a graph
• Analytical results for the distribution of first return times of non-backtracking random walks on configuration model networks