On the self-intersection time of non-backtracking random walks

2026-08-10 • Data Structures and Algorithms

Data Structures and Algorithms

AI summaryⓘ

The authors study how long it takes for a certain kind of random walk, called a non-backtracking random walk, to cross its own path on graphs with specific degree conditions. They show that for graphs with degrees between 3 and some fixed maximum, the expected time before this self-intersection happens is on the order of the square root of the number of nodes times a logarithmic factor. For regular graphs with a specific spectral property, this time can be improved to just the square root of the number of nodes. They also prove that in some cases, the time can't be much smaller than this. Their results help improve understanding of the mixing speed of certain statistical physics models on these graphs.

non-backtracking random walkself-intersection timegraph theoryspectral gapregular graphexpander graphmixing timeGlauber dynamicsIsing modeltree uniqueness threshold

Authors

Ferenc Bencs, Leslie Ann Goldberg, Matthew Jenssen, Mark Jerrum, Gabor Pete, Guus Regts, Yitong Yin

Abstract

We study the self-intersection time of the non-backtracking random walk on connected undirected graphs. For every fixed $Δ\geq 3$ we show that the expected self-intersection time is $O(\sqrt{n} \log n)$ on $n$-vertex graphs with minimum degree at least $3$ and maximum degree at most $Δ$. For regular graphs with a uniform spectral gap, we improve this to $O(\sqrt{n})$. We also show an $Ω(\sqrt{n})$ lower bound on a class of regular expanders. Our upper bound on the expected self-intersection time implies an improved mixing time bound on Glauber dynamics for the Ising model on $Δ$-regular graphs at the tree uniqueness threshold.

View PDFOpen arXiv