Abstract view
NonBacktracking Random Walks and Cogrowth of Graphs


Published:20070801
Printed: Aug 2007
Ronald Ortner
Wolfgang Woess
Abstract
Let $X$ be a locally finite, connected graph without vertices of
degree $1$. Nonbacktracking random walk moves at each step with equal
probability to one of the ``forward'' neighbours of the actual state,
\emph{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 nonbacktracking transition
probabilities tend to zero, and we can also compute their limit when
$X$ is finite. This provides a short proof of old results concerning
cogrowth of groups, and makes the extension of that result to
arbitrary regular graphs rigorous. Even when $X$ is nonregular, but
\emph{small cycles are dense in} $X$, we show that the graph $X$ is
nonamenable if and only if the nonbacktracking $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.
Keywords: 
graph, oriented line grap, covering tree, random walk, cogrowth, amenability
graph, oriented line grap, covering tree, random walk, cogrowth, amenability
