A non-backtracking Pólya’s theorem

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.

Full Text (PDF format)

Research supported by the Center of Mathematical Sciences and Applications at Harvard University.

Received 28 October 2016

Published 22 January 2018