Journal of Combinatorics

Volume 11 (2020)

Number 3

Remarks on the recurrence and transience of non-backtracking random walks

Pages: 549 – 555

DOI: https://dx.doi.org/10.4310/JOC.2020.v11.n3.a7

Authors

Paul Jung (Korea Advanced Institute of Science and Technology (KAIST), Daejeon, South Korea)

Greg Markowsky (Monash University, Melbourne, Victoria, Australia)

Abstract

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.

Keywords

non-backtracking random walk, Pólya’s theorem

Full Text (PDF format)

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