Journal of Combinatorics

Volume 9 (2018)

Number 2

A non-backtracking Pólya’s theorem

Pages: 327 – 343



Mark Kempton (Center of Mathematical Sciences and Applications, Harvard University, Cambridge, Massachusetts, U.S.A.)


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