The classical birthday paradox says that in a group of about 23 people, there is already a better-than-even chance that two share a birthday. The underlying math is general: if you make around the square root of N random choices from a collection of N items, you have a good chance of picking the same item twice. This paper studies an analogous question for random walks on networks, specifically asking how long a walk must be before it is likely to revisit a location or cross its own path.
The twist here is that the walks studied are "non-backtracking," meaning the walker is not allowed to immediately reverse the last step taken. This constraint makes the walk behave more like a truly random exploration of the network, and it is also mathematically harder to analyze because successive steps are not fully independent. The authors focus on regular graphs, where every node has the same number of connections (at least three), and they ask when such a walk is likely to self-intersect, meaning visit a node or traverse an edge it has seen before.
The main result is that the birthday paradox threshold for these walks is essentially the square root of the number of vertices in the graph, just as intuition from the classical paradox would suggest. Walks shorter than this threshold tend not to self-intersect, while walks longer than it almost surely do. This confirms a conjecture made by two prominent mathematicians, Noga Alon and Yuval Peres, at least for graphs where the degree is fixed rather than growing. The result has implications for understanding how quickly random walks explore networks and for the design and analysis of algorithms that use random walks in graph problems.