# Proof of $\sqrt{\pi/2}$ in birthday paradox?

I had found in the past a publication in a crypto conference (in 80s if i am not mistaken) which I believe was the first proof why for example a random function $f:X\rightarrow X$ with $\#X=2^n,$ is expected to have collision in $\sqrt{\frac{\pi}{2}\times 2^n}$ iterations. I can't find it, anyone has the reference?

• hal.archives-ouvertes.fr/inria-00075445/document May 18, 2017 at 12:26
• boss, thanks. Is it that trivial? why the downvote May 18, 2017 at 12:58
• @AntonisParagas don't take the down-votes personally. Many people are too lazy to answer / comment to correct you. For me - what do you mean "expected to have collision"? Though - nice reading from SEJPM May 18, 2017 at 13:36
• Dropped an upvote... for whatever that's worth. May 18, 2017 at 14:14
• haha cheers, i was just wondering if it was out of line or something May 18, 2017 at 14:44

The paper you are looking for is:

"Random Mapping Statistics" by Flajolet and Odlyzko, first published in Advances in Cryptology — EUROCRYPT ’89. EUROCRYPT 1989. Lecture Notes in Computer Science, vol 434.

It is freely available via SpringerLink and via Archives-Ouvertes (PDF).

The relevant statistic you are looking for is probably the rho-length, which specifies the specifies the average length of a cycle to be $\sqrt{\pi n/2}$ where $n=2^k$ in your case.