Non-Backtracking Random Walks and Cogrowth of Graphs
Ronald Ortner, Wolfgang Woess · Canadian Journal of Mathematics · 2007
Abstract LetXbe a locally finite, connected graph without vertices of degree 1. Non-backtracking random walk moves at each step with equal probability to one of the “forward” neighbours of the actual state,i.e.,it does not go back along the preceding edge to the preceding state. This is not a Markov chain, but can be turned into a Markov chain whose state space is the set of oriented edges ofX. Thus we obtain for infiniteXthat then-step non-backtracking transition probabilities tend to zero, and we can also compute their limit whenXis finite. This provides a short proof of an old result concerning cogrowth of groups, and makes the extension of that result to arbitrary regular graphs rigorous. Even whenXis non-regular, butsmall cycles are dense in X, we show that the graphXis non-amenable if and only if the non-backtrackingn-step transition probabilities decay exponentially fast. This is a partial generalization of the cogrowth criterion for regular graphs which comprises the original cogrowth criterion for finitely generated groups of Grigorchuk and Cohen.