Non-Backtracking Random Walks and Cogrowth of Graphs

DOI10.4153/CJM-2007-035-1MaRDI QIDQ3590760zbMATH OpenOpenAlexFDO

Authors Ronald Ortner, Wolfgang Woess

Publication date 3 September 2007

Published in Canadian Journal of Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0403414

zbMATH Keywords

Markov chaintransition probabilitiesfinitely generated groups

Mathematics Subject Classification ID

Sums of independent random variables; random walks (60G50) Structural characterization of families of graphs (05C75) Asymptotic properties of groups (20F69)

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, 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 "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.

Recommendations

• Reversibility of the non-backtracking random walk
• Remarks on the recurrence and transience of non-backtracking random walks
• Quasi-regular graphs, cogrowth, and amenability
• scientific article; zbMATH DE number 2128201
• Cycle density in infinite Ramanujan graphs

Cited in

(23)

• Vertex reinforced non-backtracking random walks: an example of path formation
• Cogrowth of Regular Graphs
• Algorithmically finite groups.
• Quasi-regular graphs, cogrowth, and amenability
• Fractal models for normal subgroups of Schottky groups
• The nonamenability of Schreier graphs for infinite index quasiconvex subgroups of hyperbolic groups.
• Remarks on the recurrence and transience of non-backtracking random walks
• scientific article; zbMATH DE number 2128201 (Why is no real title available?)
• Amenability, critical exponents of subgroups and growth of closed geodesics
• Critical exponents for groups of isometries.
• Unbounded Hermitian operators and relative reproducing kernel Hilbert space
• Group-extended Markov systems, amenability, and the Perron-Frobenius operator
• Absolutely continuous spectrum for quantum trees
• Recent results of quantum ergodicity on graphs and further investigation
• The measurable Kesten theorem
• Reversibility of the non-backtracking random walk
• Weighted cogrowth formula for free groups
• The non-backtracking spectrum of the universal cover of a graph
• Non-backtracking random walk
• Analysis of unbounded operators and random motion
• Return probabilities on nonunimodular transitive graphs
• Kesten's theorem for invariant random subgroups.
• L^p norms and support of eigenfunctions on graphs

This page was built for publication: Non-Backtracking Random Walks and Cogrowth of Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3590760)