23 人目の給仕
アメリカの数学者ウォーレン・ウィーバーは、1963 年の本『レディ・ラック』に、第 2 次世界大戦中のある夕食会の話を書いている。
軍の将校たちが集まった席で、話が誕生日の問題になった。部屋に 23 人いれば、誕生日が同じ 2 人がいる確率は 2 分の 1 を超える。ウィーバーがそう言うと、ほとんどの人は信じなかった。1 年は 365 日もある。23 人では、とても足りないように思える。
そこで、テーブルを回って、順に誕生日を言っていくことになった。最後の 1 人まで、同じ日は出なかった。そのとき、給仕をしていた女性が口を開いた。自分が部屋の 23 人目で、誕生日は席の 1 人と同じです、と。
これはウィーバーの回想で、細部を確かめる記録は無い。ただ、話の筋は数学とよく合っている。23 人の部屋で一致が起きるかどうかは、ほぼ五分五分の賭けである。席の 22 人では 47.6 %、給仕を入れた 23 人で 50.7 % になる。23 人の部屋を 2 つ用意すれば、少なくとも一方で一致が起きる確率は 75 % を超える。
「パラドックス」と呼ばれるが、論理の矛盾があるわけではない。直感と答えが大きく食い違う、という意味である。人は「自分と同じ誕生日の人がいるか」を思い浮かべてしまう。だが問われているのは、23 人の中の、誰と誰でもよい 1 組である。23 人からできる 2 人の組は 組もある。
起源
この問題を最初に考えたのは、イギリスの数学者ハロルド・ダベンポートだとよく言われる。1927 年ごろに人に話していたが、発表はしなかった。自分が最初に考えたとも言わなかった。これほど簡単な問題が、まだ誰にも書かれていないとは信じられなかったから、と伝えられている。
活字になった最初の記録は、1939 年にオーストリア出身の数学者リヒャルト・フォン・ミーゼスが書いた論文である。フォン・ミーゼスは、確率を「試行を限りなく続けたときに現れる割合の極限」として定める立場(頻度説)を唱えた人でもある。1933 年にナチスの政権を逃れてドイツを去り、イスタンブール大学で教えていた。この論文は、玉をいくつかの箱にでたらめに入れたとき、同じ箱に入る玉の数がどうなるかを扱う「占有問題」を論じ、誕生日の一致をその例の 1 つとした。
その後、確率論の教科書に必ず載る例題になった。答えが直感とあまりに違うので、確率の考え方の入門として好まれた。
20 世紀の後半には、暗号の分野で新しい意味を持った。デジタルの指紋とも言える「ハッシュ値」は、どんなデータも決まった長さの値にまとめる。2 つの違うデータが同じ値になる組を探す攻撃は、この問題と同じ数学に従うので、「誕生日攻撃」と呼ばれる。
証明
誕生日は 365 日のどれにも同じ確からしさで、人ごとに独立に決まるとする(2 月 29 日は考えない)。「誰か 2 人が一致する」より、反対の「全員がばらばら」の方が数えやすい。
-
1 人目は何日でもよい。2 人目は 1 人目と違う 364 日、3 人目は残りの 363 日…と続く。 人がばらばらになる確率は次の積である。
-
一致する 2 人がいる確率は、その残りである。
-
を計算すると となり、ここで初めて 2 分の 1 を超える。
-
小さな では である。積が指数の和になり、和は になる。
-
確率が 2 分の 1 になる を求めると、 となる。 である。
-
日の数を一般に とすると、半分になる人数は に比例する。
うるう年の 2 月 29 日を入れても、答えはほとんど変わらない。実際の誕生日は、月や曜日によって少し偏っている。偏りがあると一致はかえって起きやすくなることが知られていて、本当の確率は上の値より少し高い。
応用
人数ごとの確率。 23 人で 50.7 %、30 人で 70.6 %、40 人で 89.1 %、50 人で 97.0 %、57 人で 99 % を超える。小学校の 1 クラスで同じ誕生日の 2 人がいるのは、珍しいことではない。一方、「自分と同じ誕生日の人」がいる確率が 50 % を超えるには、自分以外に 253 人が要る。
一致する組の数の平均。 1 組の 2 人が同じ誕生日である確率は で、23 人の中には 253 組ある。だから、一致する組の数の平均は 組になる。「少なくとも 1 組」の確率 は、この平均より小さい。一致が起きる部屋では、2 組、3 組と重なって起きることがあるからである。
誕生日攻撃。 ビットのハッシュ値は 通りある。手順 6 から、違うデータで同じ値になる組は、およそ 個のデータを試せば、半分の確率で見つかる。64 ビットなら約 51 億個で、いまの計算機ならすぐに届く。そのため、安全のためのハッシュ関数は 256 ビットのように長くし、 回の計算でも届かないようにする。2017 年に破られた SHA-1(160 ビット)は、この方法なら約 回の計算が要るところを、関数の弱点を突いて約 回で衝突を作られた。
ばらばらの ID。 データベースで使う UUID(第 4 版)は、122 ビットの乱数でできている。2 つが重なる確率が 50 % になるのは、約 個を作ったときである。毎秒 10 億個作っても、80 年以上かかる。
図示
曲線が急に立ち上がるのは 10 人から 40 人の間である。10 人で 11.7 %、20 人で 41.1 %、40 人で 89.1 % になる。人数が 2 倍になると、組の数はおよそ 4 倍になるからである。
実線と破線の差は、組の数の差である。 人の中の組は で 2 乗のように増えるが、自分を含む組は しかない。
シミュレーション
円は 1 年の 365 日で、いちばん上が 1 月 1 日である。部屋に人が 1 人ずつ入り、誕生日の位置に点が置かれる。同じ日に 2 人目が来ると、その日に線が引かれる。部屋がいっぱいになると少し止まり、次の部屋に移る。たくさんの部屋を試した結果の割合が、右のグラフの理論の曲線に近づいていく。人数のつまみを 23 の前後で動かしてみるとよい。
広がる学問
- 情報科学 ハッシュ表で値が重なる頻度の見積もり、暗号の鍵や署名の長さの決め方、乱数で作る ID の長さの決め方に使う。
- 心理学 人は偶然の一致を、実際より珍しいと感じやすい。統計学者のディアコニスとモステラーは 1989 年、偶然の一致を調べる方法を論じ、「十分に大きな数を集めれば、どんなに珍しいことも起きる」と指摘した。宝くじの高額の当選が同じ人に 2 度起きた、という話も、アメリカじゅうの宝くじの買い手の数を考えれば驚くほどのことではない、というのが 2 人の見方である。
- 法学 犯罪捜査の DNA 型のデータベースが大きくなると、別人どうしが一部の型で一致する組が見つかるようになる。組の数は登録した人数の 2 乗で増えるので、データベース全体を探して見つけた一致を、1 人と照合したときの確率だけで評価すると、証拠としての重みを見誤る。
- 数学 箱の数と玉の数を変えた占有問題として一般化される。3 人の誕生日が一致する確率が 50 % を超えるのは 88 人である。宝くじの当選番号が以前の回と同じになる確率も、同じ計算で見積もれる。
参考文献
- R. von Mises, "Über Aufteilungs- und Besetzungs-Wahrscheinlichkeiten", Revue de la Faculté des Sciences de l'Université d'Istanbul 4 (1939), 145-163.
- Warren Weaver, Lady Luck: The Theory of Probability (Anchor Books, 1963; Dover, 1982).
- William Feller, An Introduction to Probability Theory and Its Applications, vol. 1 (Wiley, 1950).
- Persi Diaconis and Frederick Mosteller, "Methods for Studying Coincidences", Journal of the American Statistical Association 84 (1989), 853-861.
- Marc Stevens et al., "The First Collision for Full SHA-1", CRYPTO 2017, Lecture Notes in Computer Science 10401 (2017), 570-596.