  We analyze a fairly standard idealization of Pollard's Rho algorithm for
finding the discrete logarithm in a cyclic group G. It is found that, with high
probability, a collision occurs in $O(\sqrt{|G|\log |G| \log \log |G|})$ steps,
not far from the widely conjectured value of $\Theta(\sqrt{|G|})$. This
improves upon a recent result of Miller--Venkatesan which showed an upper bound
of $O(\sqrt{|G|}\log^3 |G|)$. Our proof is based on analyzing an appropriate
nonreversible, non-lazy random walk on a discrete cycle of (odd) length |G|,
and showing that the mixing time of the corresponding walk is $O(\log |G| \log
\log |G|)$.
