Reversibility of the non-backtracking random walk

Abstract

Let $G$ be a connected graph of uniformly bounded degree. A $k$ non-backtracking random walk ($k$-NBRW) $(X_n{)}_{n=0}^{\infty }$ on $G$ evolves according to the following rule: Given $(X_n{)}_{n=0}^s$, at time $s+1$ the walk picks at random some edge which is incident to $X_s$ that was not crossed in the last $k$ steps and moves to its other end-point. If no such edge exists then it makes a simple random walk step. Assume that for some $R>0$ every ball of radius $R$ in $G$ contains a simple cycle of length at least $k$. We show that under some "nice" random time change the $k$-NBRW becomes reversible. This is used to prove that it is recurrent iff the simple random walk is.

34 pages. Some proofs that were previously omitted were added

References in corpus (3)

• Non-backtracking random walks mix faster
• Markov chain comparison
• Non-backtracking random walk