Hostname: page-component-7b7567c8c-2n9c9 Total loading time: 0 Render date: 2026-11-19T04:01:31.975Z Has data issue: false hasContentIssue false

Non-Backtracking Random Walks and Cogrowth of Graphs

Published online by Cambridge University Press:  20 November 2018

Ronald Ortner
Affiliation:
Department Mathematik und Informationstechnolgie, Montanuniversität Leoben, Franz-Josef-Strasse 18, A-8700 Leoben, Austria email: ronald.ortner@unileoben.ac.at
Wolfgang Woess
Affiliation:
Institut für Mathematische Strukturtheorie, Technische Universität Graz, Steyrergasse 30, A-8010 Graz, Austria email: woess@TUGraz.at
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Let $X$ be 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 of $X$ . Thus we obtain for infinite $X$ that the $n$ -step non-backtracking transition probabilities tend to zero, and we can also compute their limit when $X$ is 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 when $X$ is non-regular, but small cycles are dense in $X$ , we show that the graph $X$ is non-amenable if and only if the non-backtracking $n$ -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.

Information

Type
Research Article
Copyright
Copyright © Canadian Mathematical Society 2007