Reversibility of the non-backtracking random walk
View / Open Files
Authors
Journal Title
Annales de l’Institut Henri Poincaré
ISSN
0246-0203
Publisher
Elsevier Masson
Volume
55
Issue
4
Pages
2295-2319
Type
Article
This Version
AM
Metadata
Show full item recordCitation
Hermon, J. (2019). Reversibility of the non-backtracking random walk. Annales de l’Institut Henri Poincaré, 55 (4), 2295-2319. https://doi.org/10.1214/18-AIHP949
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.
Keywords
math.PR, math.PR, 60J10
Sponsorship
EPSRC grant EP/L018896/1.
Identifiers
External DOI: https://doi.org/10.1214/18-AIHP949
This record's URL: https://www.repository.cam.ac.uk/handle/1810/296999
Rights
All rights reserved