Non-backtracking random walks mix faster

By Noga Alon, Itai Benjamini, Eyal Lubetzky, S. Sodin. 2006

192 citations recorded by the source corpus.

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 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 Ω(log n) times.

Subfields: Discrete Mathematics and Combinatorics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/91ef82dc8250e5770a8d4abb85715f1f15d81aa3

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Discrete Mathematics and Combinatorics

In Statistics and Probability

Citations in the corpus

Cutoff on all Ramanujan graphs (2015, background): “that appear implicitly in [20] (see also [5,7,8] as well as [26, Exercise 6.”
Spectral redemption in clustering sparse networks (2013, methodology): “It has been used to show fast mixing for the non-backtracking random walk [17], and arises in connection to belief propagation [18, 19], in particular to rigorously analyze the behavior of belief propagation for clustering problems on regular graphs [5].”
Statistical physics of inference: thresholds and algorithms (2015, background): “[7] Noga Alon, Itai Benjamini, Eyal Lubetzky, and Sasha Sodin.”
THE NON-BACKTRACKING SPECTRUM OF THE UNIVERSAL COVER OF A GRAPH (2007, background): “For example, the nonbacktracking random walk selects at each step a uniform neighbour of Xn different from Xn−1 [1, 28].”
Random walks and diffusion on networks (2016, background): “In such an RW, a walker performs an RW, except that it is not allowed to backtrack [257, 258], so p( #» ij → #» ji) = 0 and p( #» ij → #» j`) = 1/(s j − Aji) (with ` 6= i).”
Non-backtracking random walks and a weighted Ihara's theorem (2016, methodology): “in [1] that in most cases, a nonbacktracking random walk on a regular graph has a faster mixing rate than the usual random walk.”
Cutoff phenomena for random walks on random regular graphs (2008, unknown): “Therefore, ρt − (d−2)td is a martingale, and the Azuma-Hoeffding inequality (cf., e.g., [6]) ensures that P (∣∣∣∣ρ4K − ρ0 − 4K(d− 2)d ∣∣∣∣ > K3 ) ≤ exp ( −K 72 ( 1 + d−2d )2 ) = o(1) .”