Kempton, Mark Condie2017-12-042016Kempton, Mark. 2016. “Non-Backtracking Random Walks and a Weighted Ihara’s Theorem.” Open Journal of Discrete Mathematics 06 (04): 207–226. doi:10.4236/ojdm.2016.64018.2161-7643http://nrs.harvard.edu/urn-3:HUL.InstRepos:34406559We study the mixing rate of non-backtracking random walks on graphs by looking at non-backtracking walks as walks on the directed edges of a graph. A result known as Ihara’s Theorem relates the adjacency matrix of a graph to a matrix related to non-backtracking walks on the directed edges. We prove a weighted version of Ihara’s Theorem which relates the transition probability matrix of a non-backtracking walk to the transition matrix for the usual random walk. This allows us to determine the spectrum of the transition probability matrix of a non-backtracking random walk in the case of regular graphs and biregular graphs. As a corollary, we obtain a result of Alon et. al. in [1] that in most cases, a nonbacktracking random walk on a regular graph has a faster mixing rate than the usual random walk. In addition, we obtain an analogous result for biregular graphs.en-USJournal Article2016-05-1120162017-12-0410.4236/ojdm.2016.64018