Birthday paradox for non-backtracking walks
A non-backtracking walk chooses a random neighboring vertex without immediately retracing its last edge. How many steps does it take before it is likely to visit a vertex twice?
Why it matters and what counts as progress
Why it matters: The ordinary birthday paradox gives a square-root collision scale for independent draws. In a walk, the graph constrains each step, so a comparable scale requires controlling those dependencies.
What counts as progress: Prove a collision bound from every starting edge, with explicit assumptions about degrees or expansion. State whether the constant depends on degree and whether the result concerns open walks or closed loops.
How the problem developed
- 2024 · Closed loops on random regular graphs [1]
Benjamin Dozier and Jenya Sapir Benjamin Dozier and Jenya Sapir analyze self-intersections of closed non-backtracking loops on random regular graphs.
- August 2026 · Related bounds under different graph assumptions [2]
Ferenc Bencs and collaborators Ferenc Bencs and collaborators prove a logarithmically weaker bound in a more general class and a square-root bound for fixed-degree expanders.
- 26 Aug 2026 · Fixed-degree regular graphs [3]
Benjamin Dozier with AI assistance Dozier extends an AI proof for degree three to every fixed degree at least three. The argument starts from any directed edge.
AI contribution
The Birthday Paradox for non-backtracking walks on regular graphs
For every fixed and every , there is such that on any simple d-regular graph with n vertices, a uniform non-backtracking walk of length greater than from any starting edge is simple with probability less than .
Sources
Publication history
The Birthday Paradox for non-backtracking walks on regular graphs
Daily emails by default, only when there’s an update.