# 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 – SEJPM May 18 '17 at 12:26
• boss, thanks. Is it that trivial? why the downvote – Antonis Paragas May 18 '17 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 – gusto2 May 18 '17 at 13:36
• Dropped an upvote... for whatever that's worth. – e-sushi May 18 '17 at 14:14
• haha cheers, i was just wondering if it was out of line or something – Antonis Paragas May 18 '17 at 14:44

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.