Non-backtracking random walks mix faster

Noga Alon, Itai Benjamini, Eyal Lubetzky, Sasha Sodin

Research output: Contribution to journalArticle

76 Scopus citations

Abstract

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))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 Ω(log n) times.

Original languageEnglish (US)
Pages (from-to)585-603
Number of pages19
JournalCommunications in Contemporary Mathematics
Volume9
Issue number4
DOIs
StatePublished - Aug 1 2007
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Mathematics(all)
  • Applied Mathematics

Keywords

  • Balls and bins
  • Expanders
  • Girth
  • Mixing rate
  • Non-backtracking random walks

Fingerprint Dive into the research topics of 'Non-backtracking random walks mix faster'. Together they form a unique fingerprint.

  • Cite this