2016/10/15 by Kempton, Mark
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1610.04672
Pólya's random walk theorem states that a random walk on a d-dimensional grid is recurrent for d=1,2 and transient for d≥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≥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.