Non-backtracking random walks and cogrowth of graphs

Details Non-backtracking random walks and cogrowth of graphs Non-backtracking random walks and cogrowth of graphs

2004-03-24

arxiv.org/abs/math/0403414v1

Mathematics

Probability

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Non-backtracking random walks and cogrowth of graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Non-backtracking random walks and cogrowth of graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Non-backtracking random walks and cogrowth of graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-89706