背景
「性質のよいハッシュ関数が $n$ 個の値を出力しえる場合、同じハッシュ値を取る $2$ つの値の組を発見する（衝突する）までの出力試行回数の期待値を求めよ」という問題を考えます。
IT用語辞典 e-Words には、以下のように記載されていますが、$1.25$ ってどこから来たねんという疑問があります。
あるハッシュ関数がH個の値を出力し得る場合、
平均で約1.25√Hの試行回数で同じハッシュ値を取る
2つの値の組を発見できることが知られている。
証明（ラマヌジャン降臨）
良いハッシュ関数が $n$ 種類の値を出力するとします。衝突が発生するまでの試行回数を表す確率変数 $X$ を考え、その期待値 $E[X]$ は、
\begin{align*}
E[X] &= \sum_{j=0}^{\infty} j \cdot P(X=j) \\
&= \sum_{k=0}^{\infty} P(X > k) \\
&= \sum_{k=0}^{n} \left( \frac{n}{n} \times \frac{n-1}{n} \times \frac{n-2}{n} \times \cdots \times \frac{n-k+1}{n} \right) \\
&= \sum_{k=0}^{n} \frac{n!}{ (n-k)! n^k } \\
&= 1 + \sum_{k=1}^{n} \frac{n!}{ (n-k)! n^k } \\
&= 1+Q(n) \\
&\sim 1 + \left( \sqrt{\frac{\pi n}{2}} - \frac{1}{3} + \frac{1}{12} \sqrt{\frac{\pi}{2n}} - \frac{4}{135 n} + \dots \right) \\
&= \sqrt{\frac{\pi n}{2}} + \frac{2}{3} + \frac{1}{12} \sqrt{\frac{\pi}{2n}} - \frac{4}{135 n} + \dots
\end{align*}
ここで $Q(n)$ はラマヌジャンのQ関数です。$n$ が大きい場合、期待値 $E[X]$ は $\displaystyle \sqrt{\frac{\pi n}{2}} \approx 1.253 \sqrt{n}$ に近い値をとります。
補遺
ラマヌジャンのQ関数
$$Q(n) = \sum_{k=1}^{n} \frac{n!}{ (n-k)! n^k }$$$n$ が大きいとき、次の漸近展開を持つことが知られています。$$Q(n) \sim \sqrt{\frac{\pi n}{2}} - \frac{1}{3} + \frac{1}{12} \sqrt{\frac{\pi}{2n}} - \frac{4}{135 n} + \dots$$
上記の漸近展開は、On Ramanujan's Q-function に高等な証明が乗っています。
本問題の証明について
-
この証明方法は、Wikipedia によると、Knuth, D. E. (1973). The Art of Computer Programming. Vol. 3, Sorting and Searching. に記載されていると言及されています。Vol. 3 を僕は持っておらず、第何版の何ページにどれくらいの厳密さで証明が乗っているのか、持っている人がいたら教えてほしいです。
-
Stack Exchange に高度な初等的な証明が載っています。
類似問題
「何人集まれば、同じ誕生日のペアがいる確率が $p$ を超えるか？」という問題の答えは、誕生日の種類数 $n$ が大きいとき約 $\sqrt{2 \ln (1/(1-p))} \sqrt{n}$ 人と近似されます。例えば $p=0.5$ の場合は約 $1.1774 \sqrt{n}$ となります。日本語での説明はこちら。