Abstract: Motivated by the analysis of the Pollard Rho algorithm for the discrete logarithm problem, we develop a birthday theorem regarding self-intersections of Markov chains with uniform stationary distribution. As an application we show that a collision occurs in \Theta(\sqrt{|G|}) steps of the Rho algorithm for finding the discrete log in a cyclic group G. Time permitting, I will describe current work on extensions to the more practically relevant Kangaroo algorithm. This is based on joint papers with Jeong Han Kim, Ravi Montenegro, and Yuval Peres.