A birthday paradox for Markov chains with an optimal bound for collision in the Pollard rho algorithm for discrete logarithm (Q968774)

The authors propose to show a Birthday Paradox for self-intersection of Markov chains with uniform stationary distribution. The Birthday Paradox states that if \(C\sqrt{N}\) items are sampled uniformly at random with replacement from a set of \(N\) items, for large \(C\) with high probability, some items will be chosen twice. This can be interpreted as a statement that with high probability, a Markov chain on the complete graph \(K_N\) with transitions \(P(i, j)= 1/N\) will intersect its past in \(C\sqrt{N}\) steps. The authors refer to such a self-intersection as a collision and say the collision time is \(O(\sqrt{N})\). After an Introduction (Section 1), in Section 2 some preliminaries are given: an introduction to the Pollard Rho algorithm and a simple multiplicative bound on the collision time in terms of the mixing time. Then in Section 3 (collision time) the more general Birthday Paradox for Markov chains with uniform stationary distribution is discussed. The main result of this section is given in Theorem 3.2 (``Birthday Paradox for Markov chains''). Finally an example related to this theorem is discussed. The main result of the paper (Theorem 4.2) is presented in Section 4 entitled Convergence of the Rho walk. Some auxiliary results, used to prove this theorem, are given too. The authors finish in the last section (Distinguished point methods) by proving similar results for the distinguished points method of parallelizing the algorithm. The paper contains also an ``Appendix'' in which the theorem 4.7 given in Section 4 is proved. It is a good and instructive paper.