證明圓周率/2−−−√圓周率/2sqrt{pi/2}在生日悖論中？

我過去在加密會議上發現了一篇出版物（如果我沒記錯的話，是在 80 年代），我認為這是第一個證明為什麼例如隨機函式 $ f:X\rightarrow X $ 和 $ #X=2^n, $ 預計會發生碰撞 $ \sqrt{\frac{\pi}{2}\times 2^n} $ 迭代。沒找到，有大佬參考嗎？

您要查找的論文是：

Flajolet 和 Odlyzko 的“隨機映射統計”，首次發表於密碼學進展 — EUROCRYPT ‘89。EUROCRYPT 1989。電腦科學講義，第 434 卷。

它可通過SpringerLink和Archives-Ouvertes (PDF)免費獲得。

您正在尋找的相關統計數據可能是 rho-length，它指定指定循環的平均長度為 $ \sqrt{\pi n/2} $ 在哪裡 $ n=2^k $ 在你的情況下。

摘要內容如下：

從有限集到自身的隨機映射要麼是啟發式模型，要麼是精確模型，適用於隨機數生成、計算數論、密碼學和整體算法分析中的各種應用。本文介紹了一個總體框架，其中對大約 20 個隨機映射的特徵參數進行了分析：通過使用生成函式和奇異性分析，系統地研究了這些參數。特別是，解決了 Knuth 的一個開放問題，即找到隨機映射的預期直徑。同樣的方法適用於更大類別的離散組合模型，並且還簡要討論了使用符號操縱系統（“電腦代數”）進行自動分析的可能性。

引用自：https://crypto.stackexchange.com/questions/47516