Non-Backtracking Random Walks and Cogrowth of Graphs

DOI10.4153/CJM-2007-035-1zbMATH Open1123.05081arXivmath/0403414OpenAlexW1986796100MaRDI QIDQ3590760FDOQ3590760

Authors: Ronald Ortner, Wolfgang Woess 

Publication date: 3 September 2007

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

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.

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

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

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)

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
• Title not available (Why is that?)
• Amenability, critical exponents of subgroups and growth of closed geodesics
• Critical exponents for groups of isometries.
• Group-extended Markov systems, amenability, and the Perron-Frobenius operator
• Unbounded Hermitian operators and relative reproducing kernel Hilbert space
• 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
• The non-backtracking spectrum of the universal cover of a graph
• Weighted cogrowth formula for free groups
• 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)