Journal of Combinatorics
Volume 11 (2020)
Remarks on the recurrence and transience of non-backtracking random walks
Pages: 549 – 555
A short proof of the equivalence of the recurrence of a non-backtracking random walk and that of a simple random walk on regular infinite graphs is given. It is then shown how this proof can be extended in certain cases where the graph in question is not regular.
non-backtracking random walk, Pólya’s theorem
The first-named author was supported in part by the (South Korean) National Research Foundation grant N01170220.
Received 20 May 2019
Accepted 17 June 2019
Published 11 May 2020