Non-backtracking random walks mix faster

Details Non-backtracking random walks mix faster Non-backtracking random walks mix faster

2006-10-18

arxiv.org/abs/math/0610550v1

Commun. Contemp. Math. 9 (2007), no. 4, 585-603

Mathematics

Probability

18 pages; 2 figures

Scientific paper

10.1142/S0219199707002551

We compute the mixing rate of a non-backtracking random walk on a regular expander. Using some properties of Chebyshev polynomials of the second kind, we show that this rate may be up to twice as fast as the mixing rate of the simple random walk. The closer the expander is to a Ramanujan graph, the higher the ratio between the above two mixing rates is. As an application, we show that if $G$ is a high-girth regular expander on $n$ vertices, then a typical non-backtracking random walk of length $n$ on $G$ does not visit a vertex more than $(1+o(1))\frac{\log n}{\log\log n}$ times, and this result is tight. In this sense, the multi-set of visited vertices is analogous to the result of throwing $n$ balls to $n$ bins uniformly, in contrast to the simple random walk on $G$, which almost surely visits some vertex $\Omega(\log n)$ times.

Affiliated with

Also associated with

No associations

Rating

Non-backtracking random walks mix faster 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 mix faster, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Non-backtracking random walks mix faster will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-99826