誕生日のパラドックス エクスプローラー

誕生日が同じ人がいる確率が重ならない確率を上回るには、部屋に何人いる必要があるか？これを導出し、なぜ 23 人という数字が直感より遥かに小さく感じられるのかを説明せよ。

1. 余事象を計算する。「少なくとも1組が同じ」を直接求めるのは、重複の仕方が一度に多様に生じ得るため扱いづらい。「全員が異なる」であれば、単一の明確な選択の積として表せる。

   $$P(\text{all different})=\prod _{k=0}^{n-1}\frac{365-k}{365}$$

2. 新しい人物が増えるたび、すでに占有された誕生日をすべて避けなければならないため、選択可能な日数は毎回1日ずつ減っていく。これらの分数を掛け合わせる。

   $$n=23:\frac{365}{365}\cdot \frac{364}{365}\cdots \frac{343}{365}=0.4927$$

3. 1 から引く。上の探索ツールはまさにこれを表示しており、計算結果が半分を超える最初の n が 23 である。

   $$P(\text{shared})=1-0.4927=0.5073=50.7\%$$

4. 比べるのは、自分とほかの22人だけではありません。どの二人の組も数えるため、組の数は集団の人数のおよそ二乗に応じて増えていきます。

   $$\left(\genfrac{}{}{0ex}{}{n}{2}\right)=\frac{23\times 22}{2}=253\text{pairs}$$

5. その2乗の成長は近似式にも明確に現れている。確率は 730 に対する n² の比に依存するため、境界点は 365 の一定割合ではなく平方根としてスケールする。

   $$P\approx 1-e^{-n^2/730}:n=\sqrt{730\ln 2}=22.5$$

23 人で 50.7%。誰もが覚えている数は 23 ですが、それは結果のうち最も役に立たない部分です。365 日の 1 年にだけ属する数だからです。その下にある規則——カレンダーがハッシュ関数に変わっても生き残る規則——を見つけましょう。

1. 厳密な答えは積です。2 人目が 1 人目と外れ、3 人目が 2 人とも外れ、と部屋を進んでいく。パネルが評価しているのはこの積です。

   $$Q(n)=\prod _{k=0}^{n-1}\frac{365-k}{365},P=1-Q(23)=0.507$$

2. 積のままでは考えにくいので対数を取ります。k が 365 に対して小さいうちは、各対数はほぼ引数そのものです。残るのは最初の n−1 個の整数の和です。

   $$\ln Q=\sum _{k=0}^{n-1}\ln \left(1-\frac{k}{365}\right)\approx -\sum _{k=0}^{n-1}\frac{k}{365}=-\frac{n(n-1)}{730}$$

3. 確率を 1/2 とおいて解きます。n² の項が n を圧倒するので答えは平方根になり、パネルの 23 から半人以内に着地します。

   $$P=\frac{1}{2}⟹\frac{n(n-1)}{730}=\ln 2⟹n^2\approx 730\ln 2=506.0⟹n\approx 22.5$$

4. では 365 を 1 つも含まない形で書きましょう。1 年は特別ではありませんでした。等確率の枠が N 個なら、折り返し点はおよそ 1.1774√N です。

   $$n\approx \sqrt{2N\ln 2}=1.1774\sqrt{N}:N=365⟹22.49$$

5. これを本当に効く場所に当てはめます。32 ビットのハッシュには 2³² 個の枠があり、途方もなく聞こえます——しかし途方もない数の平方根は途方もなくありません。

   $$N=2^{32}:n\approx 1.1774\sqrt{2^{32}}=1.1774\times 65536=77162$$

6. それを、引いてくる空間の大きさと比べてみてください。

   $$\frac{77162}{2^{32}}=1.8\times 10^{-5}=0.0018\%$$