Georgia Institute of Technology College of Sciences

The Birthday Paradox says that if there are N days in a year, and 1.2*sqrt(N) days are chose uniformly at random with replacement, then there is a 50% probability that some day was chosen twice. This can be interpreted as a statement about self-intersection of random paths of length 1.2*sqrt(N) on the complete graph K_N with loops. We prove an extension which shows that for many graphs random paths with length of order sqrt(N) will have the same self-intersection property. We finish by discussing an application to the Pollard Rho Algorithm for Discrete Logarithm. (joint work with Jeong-Han Kim, Yuval Peres and Prasad Tetali).