誕生日のパラドックス

パラドックス

パーティーに何人の客がいれば、誕生日が同じ2人がいる可能性が高くなるかと尋ねると、ほとんどの人は365の半分の180人くらいと答えます。本当の答えは23人で、このとき確率は50.7%です。客が57人なら99%です。パラドックスと呼ばれるのは矛盾しているからではなく、私たちの直感にそれほど強く反するからです。

直感が外れる理由

部屋の中で、私たちは無意識に自分を基準に考えます。自分と同じ誕生日の人がいる確率はどれくらいだろう？365日もあれば、その確率は小さいものです。でもこのパラドックスは、特定の1人との一致ではなく、部屋の中で考えられるすべてのペアについての話です。AとB、BとC、AとC、という具合です。23人からは253組の異なるペアができ、どのペアも誕生日が同じになる可能性があります。

ペアは2乗で増える

n人からは n × (n − 1) / 2 組のペアができます。10人なら45組、23人なら253組、57人なら1,596組、100人なら4,950組です。それぞれのペアの誕生日が同じになる確率は1/365なので、253組あれば、誕生日が同じペアは平均で 253/365 ≈ 0.69 組になります。人数を2倍にするとペアはおよそ4倍になり、それが同じ誕生日の確率が急上昇する理由です。

一歩ずつの計算

いちばん簡単なのは、誰も誕生日が同じにならない確率を求めて、100%から引く方法です。1人目はどの日を取ってもかまいません。2人目が1人目と同じ誕生日にならない確率は364/365です。3人目が最初の2人と違う確率は363/365、と続きます。23人なら：

365/365 × 364/365 × 363/365 × … × 343/365 ≈ 49.3%

全員の誕生日が違う確率が49.3%なので、その余事象である「同じ誕生日が少なくとも1組ある」確率は 100% − 49.3% = 50.7% です。

あなたと同じ誕生日の人

あなたと同じ誕生日の人がいる確率は、別の問いです。ほかの n − 1 人はそれぞれ364/365の確率であなたの誕生日を外すので、誰かがあなたと同じ誕生日である確率は 1 − (364/365)ⁿ⁻¹ です。23人ではわずか5.9%で、50%を超えるにはほかに253人必要です。23人のグループの253組のペアのうち、あなたを含むのは22組だけです。

平方根の法則と誕生日攻撃

同じ確からしさの値がN通りあるとき、およそ 1.2 × √N 回取り出すと重複が起こりやすくなります。√365 ≈ 19 で、1.2 × 19 ≈ 23 です。これはコンピューターセキュリティでとても重要です。攻撃者は誕生日攻撃を使って、暗号学的ハッシュ値が同じになる2つの入力、つまり衝突を探します。たとえばデジタル署名を偽造するためです。誕生日のパラドックスのおかげで、必要な試行回数は直感よりはるかに少なく、128ビットのハッシュなら 2¹²⁸ 回ではなく約 2⁶⁴ 回です。だから SHA-256 のような現代のハッシュは出力が長いのです。

PictorX で試す

誕生日のパラドックスを開くと、23人のグループが1人ずつ円の上に集まってきます。新しく来た人はそこにいる全員と線で結ばれ、キャプションがペアの数を数えます。誕生日はカレンダーの上に落ち、2人以上の誕生日が重なった日が光ります。下には、その人数での計算結果と、テストしたグループのうち同じ誕生日があった割合が並び、グラフにはすべての人数について、誰か2人の誕生日が同じになる確率と、あなたと同じ誕生日の人がいる確率が表示されます。1人ずつ加えたり、2〜366人を選んだり、毎秒最大10,000グループの速さで最大100,000グループをテストしたり、すべての人数をテストして点が曲線を描いていく様子を見たりしてみてください。