CMS/SMC
Canadian Mathematical Society
www.cms.math.ca
Canadian Mathematical Society
  location:  PublicationsjournalsCJM
Abstract view

Non-Backtracking Random Walks and Cogrowth of Graphs

  Published:2007-08-01
 Printed: Aug 2007
  • Ronald Ortner
  • Wolfgang Woess
Features coming soon:
Citations   (via CrossRef) Tools: Search Google Scholar:
Format:   HTML   LaTeX   MathJax   PDF   PostScript  

Abstract

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, \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 non-backtracking 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 non-regular, but \emph{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.
Keywords: graph, oriented line grap, covering tree, random walk, cogrowth, amenability graph, oriented line grap, covering tree, random walk, cogrowth, amenability
MSC Classifications: 05C75, 60G50, 20F69 show english descriptions Structural characterization of families of graphs
Sums of independent random variables; random walks
Asymptotic properties of groups
05C75 - Structural characterization of families of graphs
60G50 - Sums of independent random variables; random walks
20F69 - Asymptotic properties of groups
 

© Canadian Mathematical Society, 2014 : http://www.cms.math.ca/