Non-Backtracking Walks Reach Collisions Near the Square-Root Scale

A non-backtracking random walk cannot immediately reverse the edge it has just traversed. This constraint makes the walk a natural model for exploration on sparse graphs, while also changing how quickly it can revisit a previously visited vertex.

Core Contribution

The paper studies the expected self-intersection time of non-backtracking random walks on connected undirected graphs. For every fixed $\Delta \geq 3$, the authors show an $O(\sqrt{n}\log n)$ upper bound on $n$-vertex graphs whose minimum degree is at least 3 and whose maximum degree is at most $\Delta$.

For regular graphs with a uniform spectral gap, they improve this bound to $O(\sqrt{n})$. The result places the collision time at the familiar square-root scale associated with birthday-paradox effects, provided the graph has sufficient global expansion.

The paper also proves an $\Omega(\sqrt{n})$ lower bound for a class of regular expanders. Together with the spectral-gap upper bound, this shows that the square-root scale is attained on that class up to constant factors.

Why the Assumptions Matter

The two upper bounds have different scopes. The $O(\sqrt{n}\log n)$ guarantee requires bounded degrees and a minimum degree of 3, while removing the logarithmic factor additionally requires regularity and a uniform spectral gap. The paper therefore does not establish an $O(\sqrt{n})$ bound for every bounded-degree graph.

The distinction highlights the role of expansion: local degree conditions control the walk broadly, whereas spectral information enables a sharper collision-time estimate.

Connection to Ising Mixing

The self-intersection bound has an application to Glauber dynamics for the Ising model on $\Delta$-regular graphs at the tree-uniqueness threshold. The paper shows that its upper bound on expected self-intersection time yields an improved mixing-time bound in this setting.

This connection links a geometric property of non-backtracking exploration to the analysis of single-site sampling dynamics. The result is an upper bound rather than an exact description of the mixing time, and its stated scope is specific to regular graphs at the threshold.

Scope

The work is theoretical and focuses on connected undirected graphs. Its main conclusions concern expected self-intersection times under degree and expansion assumptions, with a sampling application for critical Ising models on regular graphs.

Open directions include understanding whether the logarithmic factor can be removed under weaker assumptions and how broadly the resulting critical Ising mixing guarantees extend beyond the regular-graph setting.