Journal of Combinatorics
Volume 9 (2018)
A non-backtracking Pólya’s theorem
Pages: 327 – 343
Pólya’s random walk theorem (or recurrence theorem) states that a random walk on a d-dimensional grid is recurrent for $d = 1,2$ and transient for $d \geq 3$.We prove a version of Pólya’s random walk theorem for non-backtracking random walks. Namely, we prove that a non-backtracking random walk on a d-dimensional grid is recurrent for $d = 2$ and transient for $d = 1, d \geq 3$. Along the way, we prove several useful general facts about non-backtracking random walks on graphs. In addition, our proof includes an exact enumeration of the number of closed non-backtracking random walks on an infinite $2$-dimensional grid. This enumeration suggests an interesting combinatorial link between non-backtracking random walks on grids, and trinomial coefficients.
Research supported by the Center of Mathematical Sciences and Applications at Harvard University.
Received 28 October 2016
Published 22 January 2018