誕生日のパラドックス：なぜ23人いれば誕生日が重なるのか

2014年のワールドカップで、記者たちが全32チームを調べたことがあります。どのチームもちょうど23人の選手を抱えており、32チーム中16チーム、つまり半分で、少なくとも2人の選手が誕生日を共有していました。誰かが仕組んだわけではありません。23という数字は、単にそういうことをするのです。

それが誕生日のパラドックスです：23人の部屋では、誕生日が重なる方が重ならないよりも起こりやすい。誕生日は365通りあり、人は23人しかいないのですから、この主張はばかげて聞こえますし、その反応はほぼ万人共通です。しかしこの結果はトリックでも、統計の錯覚でも、細かい注釈に左右されるものでもありません。短い数え上げの議論であり、正しい数え方の代わりに直感がどの数え方をしているかが見えれば、パラドックスはほとんど当たり前に近いものへと溶けていきます。

主張を正確に述べる

誕生日が互いに独立で、365日のどの日にも等しい確率で落ちるとし、2月29日はひとまず無視して、23人を考えます。主張は次の通りです。

そのうち少なくとも2人の誕生日が一致する確率は50.7%、コイン投げよりわずかに有利です。

2つの細部が重要です。第一に、主張は誰か2人が一致することについてであり、特定の誰かと一致することについてではありません。第二に、「誕生日を共有する」とは3月14日のように1年の中の同じ日を指すのであって、同じ年月日ではありません。どちらも些細に聞こえます。しかしそのうちの一方は、これから見るように、パラドックスそのものなのです。

証明はただの数え上げ

直接の問い、つまり誰かが誰かと一致する確率はいくらか、は正面から攻めるのが厄介です。一致は重なり合う多くの形で起こり得るからです。確率にはこのための定番の一手があります：何も起こらない確率を計算し、1から引く。この一手がなぜ許されるのかを土台から知りたい方は、確率を直感的に理解するをご覧ください。

これで証明のすべてです：ペアを数えて一致がもっともらしい理由を見て、23個の分数を掛けて、どれほどもっともらしいかを正確に知る。高度な道具立てはなく、信じるしかない箇所もありません。すべてのステップは電卓で確かめられます。

そして曲線は速く登り続けます。30人では一致の確率は70.6%。50人では97.0%。70人では99.9%：1年のうち295日がまだ手つかずのまま、誕生日の一致はほぼ保証されるのです。

直感はどこで間違うのか

誕生日のパラドックスは確実に人を欺きますが、その欺き方はひとつの具体的で、診断可能な形をしています：人は違う問いに答えてしまうのです。

パズルを聞くと、心は静かに、あなたが主役のバージョンにすり替えます。ここにいる誰かが私の誕生日と一致する確率は？この問いの答えは本当に小さいのです。23人の部屋には他に22人しかおらず、それぞれがあなたと一致する確率は1/365、誰かがあなたと一致する確率は合計しても約6%です。もしパズルがあなたの誕生日についての話なら、懐疑派が正しかったでしょう。

しかしパズルは任意の一致についての話です。あなた対他の全員：22組。さらに2人目対3人目、7人目対19人目、そしてあなたがまったく関わらない他のすべての組み合わせ：あと231組、合計253組です。直感は内側から思い描ける22回の比較だけを数え、自分が加わらない231組には構造的に盲目です。パラドックスは、確率が奇妙に振る舞うことではありません。23人の部屋には、ひとりの人間が体験する比較の11倍もの比較が含まれている、ということなのです。

その差の大きさを見る手際のよい方法があります。特にあなたと一致する誰かが50%の確率で現れるには、他に22人ではまるで足りません：あなたのほかに253人が必要です。ひとつの決まった誕生日に一致するために必要な他人の数は、23人の中のペアの数と同じです。これは偶然ではなく、2つの問いが同じ算数で解かれているということであり、「私の誕生日」という枠組みが状況をどれほど過小評価しているかを正確に測っています。

答えを誠実にする但し書き

計算では、365日が等しく起こりやすく、うるう日は存在しないと仮定しました。どちらの仮定も現実の世界では成り立たないので、50.7%が現実との接触を生き延びるのかと問うのは公平です。

生き延びます。それどころか、現実は味方します。稀な366日目として2月29日を加えると確率はほんのわずかに下がりますが、しきい値を23から動かすにはまったく足りません。誕生日の偏りは逆向きに働きます：実際の出生データには季節のピークがあり、特定の月が決まって混み合います。そうした偏りはどれも衝突を起こりやすくします。人気の日に確率が固まることこそ、衝突の餌だからです。均一モデルはこのパラドックスにとって最も不利な設定であり、それでも50%を超えるのです。

この頑健さは立ち止まって味わう価値があります。パラドックス風味のパズルの普段の振る舞いとは正反対だからです。たとえばモンティホール問題は、細かい但し書きに敏感なことで有名です：司会者が何を知っているかを変えれば答えが変わります。誕生日のパラドックスは頑丈な兄弟分です。教科書的な仮定からの現実的な逸脱はすべて確率を押し上げるので、この驚きはどんな揚げ足取りも生き延びます。

パーティーの余興からハッシュ関数の攻撃へ

誕生日のパラドックスはパーティーの賭けだけでも十分に元が取れますが、まじめな仕事も持っています。暗号の世界では衝突を見つけるコストを決めており、ひとつの攻撃手法がそのまま、この名前を冠しているのです。

ハッシュ関数は任意の入力を固定サイズの指紋に圧縮し、セキュリティはしばしば、同じ指紋を持つ2つの異なる入力を誰にも見つけられないことに依存します。指紋が128ビット、つまり2の128乗通りあるとしましょう。天文学的な大きさです。特定のひとつの指紋に当たる入力を推測するのは、本当に2の128乗回のオーダーの試行を要し、永遠に絶望的です。しかし、何でもいいから衝突、つまり一致する2つの入力さえあればいい攻撃者は、誕生日のゲームをプレイしています：ランダムな入力を生成すれば、平方根の法則により、およそ2の64乗回の試行で衝突が期待できます。これがバースデー攻撃です。2の64乗は大きい数ですが、安全な数ではありません。本気の攻撃者はすでにそこを越えています。

言い換えれば、このパラドックスはハッシュの実効的な強さを、ビット換算で半分に切り詰めます。128ビットの衝突耐性が欲しい暗号研究者が256ビット出力のハッシュを使うのはこのためです：2の256乗の平方根は2の128乗であり、バースデーショートカットでさえ手の届かない場所に置かれます。パーティーに何人呼ぶかを決めるパターンが、あなたの銀行接続を守るビット数も決めており、どちらもまったく同じ計算なのです。

試してみてください、費用はかからないのですから

最良の確率の結果がそうであるように、これも検証が安上がりです。25人前後のグループなら何でも使えます：教室、オフィスのフロア、チームの名簿、結婚式の招待客リスト。全員の誕生日を聞いて、一致を待ちましょう。もちろん、1つのグループでは何も証明されません。主張は50.7%であって確実ではないので、この賭けは半分近くの回数で負けます。

説得力を生むのは繰り返しです。スポーツの名簿はこれに理想的で、ワールドカップが誕生日パラドックスの記事に登場し続けるのはそのためです：23人のチームは、ちょうどしきい値サイズの実験が、あらかじめ組まれて公開されている状態なのです。10チーム調べれば、およそ5チームで一致が見つかると期待できます。あるいはシミュレーションしましょう：1から365までの乱数を23個割り当てて重複を調べる数行のコードを1万回走らせれば、結果は0.507から1%の何分の1かの範囲に収まります。23個の分数を掛けるという議論は正確な予測を出し、世界はそれに同意し続けており、確率が現実になるのをこれほど速く感じられる方法はそう多くありません。

その禅的な本質

誕生日のパラドックスが生き続けているのは、一般的な失敗パターンの完璧なミニチュアだからです。直感は状況をひとつの視点、つまりあなたの視点から評価しますが、組み合わせが絡む状況では、その単一視点は人数とともに膨らむ倍率の分だけずれていきます。ランダム性が乱れているわけではありません。誤りは、どの問いが黙って答えられてしまうかに、まるごと宿っています。

そして処方箋は、確率でいつもそうであるように同じです：当て推量を拒み、数えること。ペアを数えればもっともらしさが現れます。分数を掛ければ正確な数字が転がり出ます。同じ数え上げが姿を変えずに暗号システムの設計に再登場するのが、この話題全体の静かな教訓です：確率の議論は、自分が酒場の賭けに使われているのか、インターネットを守るために使われているのかを知らないのです。

23人。253回のチャンス。部屋は、見かけほど空いてはいなかったのです。