Contents Online

# Journal of Combinatorics

## Volume 9 (2018)

### Number 2

### A non-backtracking Pólya’s theorem

Pages: 327 – 343

DOI: https://dx.doi.org/10.4310/JOC.2018.v9.n2.a6

#### Author

#### Abstract

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