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

  1. 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.

  2. 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.

  3. 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

Benjamin Dozier

For every fixed d≥3d\ge 3 and every ε>0\varepsilon >0, there is C(d,ε)C(d,\varepsilon ) such that on any simple d-regular graph with n vertices, a uniform non-backtracking walk of length greater than C(d,ε)nC(d,\varepsilon )\sqrt{n} from any starting edge is simple with probability less than ε\varepsilon .

AI involvementAI-centered
ImportanceNotable
Technical verificationFormal (Lean)
Human understandingExplained
Paper date:

Sources

  1. Dozier and Sapir’s earlier closed-loop analysis
  2. Bencs and collaborators’ contemporaneous bounds
  3. The Birthday Paradox for non-backtracking walks on regular graphs
  4. Pinned theorem, provenance and checking record
Publication history