誕生日の問題

確率論では、誕生日の問題は、ランダムに選ばれたn 人の集団の中で、少なくとも 2 人が同じ誕生日である確率を求めるものです。誕生日のパラドックスとは、その確率が 50% を超えるには 23 人だけ必要であるという直感に反する事実を指します。

誕生日のパラドックスは真実のパラドックスです。一見間違っているように見えますが、実際には真実です。誕生日が同じである確率が 50% に達するのに必要なのは 23 人だけというのは意外に思えるかもしれませんが、誕生日の比較はすべての可能性のある個人のペア間で行われると考えると、この結果はより直感的になります。23 人の個人の場合、⁠23 × 22/2⁠  = 考慮すべきペアは 253 組あり、これは暦年の 365 / 366 日の半分以上です。

誕生日問題の現実世界での応用としては、誕生日攻撃と呼ばれる暗号攻撃があります。誕生日攻撃では、この確率モデルを使用して、ハッシュ関数の衝突を見つける複雑さを軽減するとともに、特定の集団サイズのハッシュ内に存在するハッシュ衝突のおおよそのリスクを計算します。

この問題は、 1927年頃にハロルド・ダベンポートが発見したと一般に考えられているが、当時は公表されていなかった。ダベンポートは「この問題が以前に発表されていないとは信じられなかった」ため、自分が発見者だとは主張しなかった。^{[1] [2]}誕生日問題の最初のバージョンは、1939年にリチャード・フォン・ミーゼスによって公表された。 ^[3]

順列の観点から、イベントA を、誕生日が重複しない 23 人のグループを見つける確率とします。イベントB は、少なくとも 2 人の誕生日が同じ 23 人のグループを見つける確率で、P ( B ) = 1 − P ( A )です。P ( A )は、繰り返しがなく順序が重要でない誕生日の総数（例: 2 人のグループで、mm/dd の誕生日形式の場合、考えられる 1 つの結果は）を、繰り返しがあり順序が重要になる誕生日の総数（例: 2 人のグループの場合、考えられる 1 つの結果は）で割った比です。したがって、 と は順列です。 ${\displaystyle V_{nr}}$${\displaystyle \left\{\left\{01/02,05/20\right\},\left\{05/20,01/02\right\},\left\{10/02,08/04\right\},...\right\}}$${\displaystyle V_{t}}$${\displaystyle \left\{\left\{01/02,01/02\right\},\left\{10/02,08/04\right\},...\right\}}$${\displaystyle V_{nr}}$${\displaystyle V_{t}}$

${\displaystyle {\begin{aligned}V_{nr}&={\frac {n!}{(nk)!}}={\frac {365!}{(365-23)!}}\\[8pt]V_{t}&=n^{k}=365^{23}\\[8pt]P(A)&={\frac {V_{nr}}{V_{t}}}\approx 0.492703\\[8pt]P(B)&=1-P(A)\approx 1-0.492703\approx 0.507297\quad (50.7297\%)\end{aligned}}}$

誕生日問題を解決する別の方法は、n人のグループで少なくとも2人が同じ誕生日である確率を概算で求めることです。簡単にするために、うるう年、双子、選択バイアス、出生率の季節的および週ごとの変動^[4]は一般に無視され、代わりに365の誕生日の可能性があり、各人の誕生日がグループ内の他の人とは無関係にこれらのいずれかの日になる可能性が等しいと仮定します。

誕生日が独立している場合、誕生日が均一に分布していると、グループ内の2人が同じ誕生日になる確率が最小限に抑えられます。不均一であればあるほど、2人が同じ誕生日になる可能性が高くなります。^{[5] [6]}しかし、現実世界の誕生日はそれほど不均一ではなく、大きな変化はありません。理論上の均一分布と同様に、同じ誕生日になる確率が50%を超えるために必要な現実世界のグループサイズは23です。^[7]

目標は、部屋にいる少なくとも 2 人の誕生日が同じである確率P ( B )を計算することです。ただし、部屋にいる 2 人の誕生日が同じではない確率P ( A ′)を計算する方が簡単です。この場合、 BとA ′ が唯一の 2 つの可能性であり、相互に排他的であるため、P ( B ) = 1 − P ( A ′) となります。

23 人の場合のP ( B )の計算は次のようになります。23 人を 1 から 23 まで番号付けします。23 人全員の誕生日が異なるというイベントは、人 2 が人 1 と同じ誕生日ではない、人 3 が人 1 とも人 2 とも誕生日ではない、などとなり、最後に人 23 が人 1 から人 22 の誰とも誕生日が同じではないというイベントと同じです。これらのイベントをイベント 2、イベント 3 などと呼びます。イベント 1 は人 1 が誕生日であるというイベントで、確率 1 で発生します。このイベントの結合は条件付き確率を使用して計算できます。イベント 2 の確率は⁠364/365⁠、人物2の誕生日は人物1の誕生日以外である可能性がある。同様に、イベント2が発生した場合のイベント3の確率は⁠363/365⁠、人物3は人物1と人物2が取得していない誕生日のいずれかである可能性がある。これは最終的に、すべての先行イベントが発生したと仮定した場合のイベント23の確率が⁠になるまで続く。343/365最後に、条件付き確率の原理によれば、P ( A ′)はこれらの個々の確率の積に等しいことになります。

式（ １ ）の項をまとめると次のようになる。

式（２ ）を評価するとP（A ′）≈0.492703となる。

したがって、P ( B ) ≈ 1 − 0.492703 = 0.507297  (50.7297%) となります。

このプロセスは、 n人のグループに一般化できます。ここで、 p ( n ) は、 n人のうち少なくとも 2 人が同じ誕生日である確率です。まず、 n 人の誕生日がすべて異なる確率p ( n )を計算する方が簡単です。鳩の巣原理によ​​れば、n > 365の場合、 p ( n )はゼロです。n  ≤ 365の場合:

${\displaystyle {\begin{aligned}{\bar {p}}(n)&=1\times \left(1-{\frac {1}{365}}\right)\times \left(1-{\frac {2}{365}}\right)\times \cdots \times \left(1-{\frac {n-1}{365}}\right)\\[6pt]&={\frac {365\times 364\times \cdots \times (365-n+1)}{365^{n}}}\\[6pt]&={\frac {365!}{365^{n}(365-n)!}}={\frac {n!\cdot {\binom {365}{n}}}{365^{n}}}={\frac {_{365}P_{n}}{365^{n}}}\end{aligned}}}$

ここで、!は階乗演算子、(³⁶⁵
_位)は二項係数、 _k P _{r は}順列を表します。

この式は、最初の人には誕生日を共有する人がいないこと、2番目の人は最初の人と同じ誕生日を持つことができないことを表しています（⁠364/365⁠）、3人目の誕生日は最初の2人と同じにすることはできません（⁠363/365⁠）、そして一般にn番目の誕生日は、それ以前のn − 1 個のいずれとも同じになることはできません。

n人のうち少なくとも2人が同じ誕生日であるということは、 n人の誕生日がすべて異なるということと相補的である。したがって、その確率p ( n )は

${\displaystyle p(n)=1-{\bar {p}}(n).}$

次の表は、 nの他の値に対する確率を示しています(この表では、うるう年の存在は無視され、各誕生日の確率は等しいと想定されています)。

指数関数のテイラー級数展開（定数e≈2.718 281 828 )

${\displaystyle e^{x}=1+x+{\frac {x^{2}}{2!}}+\cdots }$

は、e ^xの一次近似値を提供します。 ${\displaystyle |x|\ll 1}$

${\displaystyle e^{x}\approx 1+x.}$

この近似をp ( n )について導出された最初の式に適用するには、x = − ⁠と設定します。1つの/365⁠ . したがって、

${\displaystyle e^{-a/365}\approx 1-{\frac {a}{365}}.}$

次に、p ( n )の各項をaを非負の整数に置き換え、 a = n − 1となるまで続ける。例えば、a = 1のとき、

${\displaystyle e^{-1/365}\approx 1-{\frac {1}{365}}.}$

p ( n )について導出された最初の式は次のように近似できる。

${\displaystyle {\begin{aligned}{\bar {p}}(n)&\approx 1\cdot e^{-1/365}\cdot e^{-2/365}\cdots e^{-(n-1)/365}\\[6pt]&=e^{-{\big (}1+2+\,\cdots \,+(n-1){\big )}/365}\\[6pt]&=e^{-{\frac {n(n-1)/2}{365}}}=e^{-{\frac {n(n-1)}{730}}}.\end{aligned}}}$

したがって、

${\displaystyle p(n)=1-{\bar {p}}(n)\approx 1-e^{-{\frac {n(n-1)}{730}}}.}$

さらに粗い近似は次のように表される。

${\displaystyle p(n)\approx 1-e^{-{\frac {n^{2}}{730}}},}$

グラフが示すように、これは依然としてかなり正確です。

近似値によれば、同じアプローチを任意の数の「人」と「日」に適用できます。365 日ではなくd 日、 n人の場合、n ≪ dの場合、上記と同じアプローチを使用して、利用可能なd日間のうちn人のうち少なくとも 2 人が同じ誕生日になる確率をp ( n , d )とすると、次の結果が得られます。

${\displaystyle {\begin{aligned}p(n,d)&\approx 1-e^{-{\frac {n(n-1)}{2d}}}\\[6pt]&\approx 1-e^{-{\frac {n^{2}}{2d}}}.\end{aligned}}}$

2人の誕生日が同じでない確率は⁠364/365⁠ . n人の人がいる部屋には、(₂^位
) = ⁠ｎ（ｎ −１）/2⁠ペア、すなわち（₂^位
)イベント。同じ誕生日の人が 2 人いない確率は、これらのイベントが独立していると仮定し、それらの確率を掛け合わせることで近似できます。独立しているということは、部屋だけでなく世界中のあらゆる 2 人のペアを置き換えて選ぶことに相当します。つまり、364/365⁠ は自身に掛け合わせることができる（₂^位
）倍となり、

${\displaystyle {\bar {p}}(n)\approx \left({\frac {364}{365}}\right)^{\binom {n}{2}}.}$

これは誰も同じ誕生日を持たない確率なので、誰かが同じ誕生日を持つ確率は

${\displaystyle p(n)\approx 1-\left({\frac {364}{365}}\right)^{\binom {n}{2}}.}$

そして23人のグループの場合、共有の確率は

${\displaystyle p(23)\approx 1-\left({\frac {364}{365}}\right)^{\binom {23}{2}}=1-\left({\frac {364}{365}}\right)^{253}\approx 0.500477.}$

23人のグループに二項分布の ポアソン近似を適用すると、

${\displaystyle \operatorname {Poi} \left({\frac {\binom {23}{2}}{365}}\right)=\operatorname {Poi} \left({\frac {253}{365}}\right)\approx \operatorname {Poi} (0.6932)}$

それで

${\displaystyle \Pr(X>0)=1-\Pr(X=0)\approx 1-e^{-0.6932}\approx 1-0.499998=0.500002.}$

結果は、これまでの説明と同様に 50% を超えています。この近似は、 e ^x ≈ 1 + x を使用するテイラー展開に基づく上記の近似と同じです。

暗算に使える良い経験則は、次の関係である。

${\displaystyle p(n,d)\approx {\frac {n^{2}}{2d}}}$

これは次のようにも書ける。

${\displaystyle n\approx {\sqrt {2d\times p(n)}}}$

これは、確率が以下の場合に有効です。1/2これらの式では、d は1 年間の日数です。

例えば、 ⁠に必要な人数を見積もるには、1/2⁠誕生日が同じ場合、

${\displaystyle n\approx {\sqrt {2\times 365\times {\tfrac {1}{2}}}}={\sqrt {365}}\approx 19}$

これは正解の 23 からそれほど離れていません。

これは、少なくとも⁠ の人数を必要とする人数について、次の式を使用して概算することもできます。1/2⁠一致する可能性:

${\displaystyle n\geq {\tfrac {1}{2}}+{\sqrt {{\tfrac {1}{4}}+2\times \ln(2)\times 365}}=22.999943.}$

これは、 ⁠のイベントが良好な近似値を示している結果です。1/け⁠確率は⁠1/2⁠ k ln 2回繰り返された場合、少なくとも1回発生する確率。^[8]

この表の明るいフィールドは、ハッシュ スペースの特定のサイズ (行) をビット単位で指定して、指定された衝突確率 (列) を達成するために必要なハッシュの数を示しています。誕生日の例えを使用すると、「ハッシュ スペースのサイズ」は「利用可能な日数」に似ており、「衝突確率」は「誕生日が重なる確率」に似ており、「必要なハッシュ要素の数」は「必要なグループ人数」に似ています。この表を使用して、必要な最小ハッシュ サイズ (ハッシュの上限とエラー確率を指定) や衝突確率 (ハッシュの数とエラー確率が固定されている場合) を決定することもできます。

比較すると、10 ⁻¹⁸から10 ⁻¹⁵は典型的なハードディスクの訂正不可能なビットエラー率である。^{[9]理論的には、} MD5などの128ビットハッシュ関数は、約8.2 × 10 ^{11 個}のドキュメントですが、出力可能な数はこれより多くなります。

以下の議論はポール・ハルモスの議論を引用したものである。^{[注 1]}

上で述べたように、2つの誕生日が重ならない確率は

${\displaystyle 1-p(n)={\bar {p}}(n)=\prod _{k=1}^{n-1}\left(1-{\frac {k}{365}}\right).}$

前の段落と同様に、 p ( n ) > ⁠となる最小のnが重要です。1/2⁠ ; または同等に、 p ( n ) < ⁠となる最小のn1/2⁠ .

上記の式で不等式1 − x < e ^{− x}を用いて、 1 − ⁠け/365⁠ e ^{− k ⁄ 365}となる。

${\displaystyle {\bar {p}}(n)=\prod _{k=1}^{n-1}\left(1-{\frac {k}{365}}\right)<\prod _{k=1}^{n-1}\left(e^{-{\frac {k}{365}}}\right)=e^{-{\frac {n(n-1)}{730}}}.}$

したがって、上記の式は近似値であるだけでなく、p ( n )の上限値でもあります。不等式

${\displaystyle e^{-{\frac {n(n-1)}{730}}}<{\frac {1}{2}}}$

p ( n ) < ⁠ を意味する1/2⁠ . nについて解くと

${\displaystyle n^{2}-n>730\ln 2.}$

ここで、730 ln 2 はおよそ 505.997 であり、 n = 23 のときのn ² − nの値 506 をわずかに下回っています。したがって、23 人で十分です。ちなみに、n ² − n = 730 ln 2 をnについて解くと、上で引用した Frank H. Mathis の近似式が得られます。

この導出は、誕生日が一致する可能性が少なくとも均等であることを保証するために最大23 人が必要であることを示しているだけであり、 nが 22 以下になる可能性も残されています。

一般化された誕生日問題は、1年がd日あるとすると、ランダムに選ばれたn人の集合において、誕生日が一致する確率が少なくとも50%となるような 最小の数n ( d )を求める問題である。言い換えれば、n ( d )は、

${\displaystyle 1-\left(1-{\frac {1}{d}}\right)\left(1-{\frac {2}{d}}\right)\cdots \left(1-{\frac {n-1}{d}}\right)\geq {\frac {1}{2}}.}$

古典的な誕生日問題は、n (365)を決定することに相当する。n ( d )の最初の99個の値はここに示されている（OEISのシーケンスA033810）。

同様の計算により、dが341～372の範囲にある 場合、 n ( d ) =23であることがわかります。

n ( d )に関する多くの境界値と公式が発表されている。^{[10]任意の}d ≥ 1 に対して、数n ( d )は次式を満たす。^[11]

${\displaystyle {\frac {3-2\ln 2}{6}}<n(d)-{\sqrt {2d\ln 2}}\leq 9-{\sqrt {86\ln 2}}.}$

これらの境界は、n ( d ) − √ 2 d ln 2の数 が、

${\displaystyle {\frac {3-2\ln 2}{6}}\approx 0.27,}$

それは

${\displaystyle 9-{\sqrt {86\ln 2}}\approx 1.28}$

最大値はd = 43のときです。

境界は十分に厳密なので、ほとんどの場合、n ( d )の正確な値が得られます。たとえば、 d = 365 の場合、これらの境界は22.7633 < n (365) < 23.7736を意味し、23 はその範囲内の唯一の整数です。一般に、これらの境界から、 n ( d )は常に次のいずれかに等しいこと がわかります。

${\displaystyle \left\lceil {\sqrt {2d\ln 2}}\,\right\rceil \quad {\text{or}}\quad \left\lceil {\sqrt {2d\ln 2}}\,\right\rceil +1}$

ここで⌈·⌉は天井関数を表す。式

${\displaystyle n(d)=\left\lceil {\sqrt {2d\ln 2}}\,\right\rceil }$

は整数dの73%に当てはまる。^[12]式

${\displaystyle n(d)=\left\lceil {\sqrt {2d\ln 2}}+{\frac {3-2\ln 2}{6}}\right\rceil }$

ほぼすべての dに対して成り立ち、つまり漸近密度1の整数dの集合に対して成り立つ。 ^[12]

式

${\displaystyle n(d)=\left\lceil {\sqrt {2d\ln 2}}+{\frac {3-2\ln 2}{6}}+{\frac {9-4(\ln 2)^{2}}{72{\sqrt {2d\ln 2}}}}\right\rceil }$

全てのd ≤に対して成り立つ10 ¹⁸だが、この公式には反例が無限に存在すると推測される。 ^[13]

式

${\displaystyle n(d)=\left\lceil {\sqrt {2d\ln 2}}+{\frac {3-2\ln 2}{6}}+{\frac {9-4(\ln 2)^{2}}{72{\sqrt {2d\ln 2}}}}-{\frac {2(\ln 2)^{2}}{135d}}\right\rceil }$

全てのd ≤に対して成り立つ10 ¹⁸であり、この式はすべてのdに対して成り立つと推測される。 ^[13]

この問題を拡張して、グループ内の少なくとも 3 人、4 人、5 人などが同じ誕生日を共有する確率が 50% を超えるには、グループに何人必要かを問うこともできます。

最初の数個の値は次のとおりです。3人が同じ誕生日になる確率が50%を超える人 - 88人。4人が同じ誕生日になる確率が50%を超える人 - 187人（OEISのシーケンスA014088）。^[14]

誕生日の問題は次のように一般化できます。

離散一様分布から範囲[1, d ]で抽出されたn個のランダムな整数が与えられたとき、少なくとも2つの数字が同じである確率p ( n ; d )はいくらでしょうか？（ d = 365の場合は通常の誕生日問題になります。）^[15]

一般的な結果は、上記と同じ議論を使用して導き出すことができます。

${\displaystyle {\begin{aligned}p(n;d)&={\begin{cases}1-\displaystyle \prod _{k=1}^{n-1}\left(1-{\frac {k}{d}}\right)&n\leq d\\1&n>d\end{cases}}\\[8px]&\approx 1-e^{-{\frac {n(n-1)}{2d}}}\\&\approx 1-\left({\frac {d-1}{d}}\right)^{\frac {n(n-1)}{2}}\end{aligned}}}$

逆に、少なくとも2つの数が同じである 確率pを得るために[1, d ]から抽出されるランダムな整数の数をn ( p ; d )とすると、

${\displaystyle n(p;d)\approx {\sqrt {2d\cdot \ln \left({\frac {1}{1-p}}\right)}}.}$

このより一般的な意味での誕生日問題はハッシュ関数に適用されます。衝突が発生する前に生成できるNビットハッシュの予想数は2 ^Nではなく、 2 ^{N ⁄ 2}のみです。これは暗号ハッシュ関数に対する誕生日攻撃によって悪用され、ハッシュテーブルでの少数の衝突が実用上避けられない 理由です。

誕生日問題の理論は、ゾーイ・シュナーベル^{[16]によって}捕獲再捕獲統計という名前で湖の魚の個体数を推定するために使われました。誕生日問題とその一般化は、偶然の一致をモデル化するための有用なツールでもあります。^[17]

古典的な誕生日問題では、2人以上の人が特定の誕生日を共有したり、複数の日に一致する場合が想定される。n人の中で、 d日間の可能性がある誕生日が一致するペアが1組だけ存在する確率は^{[17]である。}

${\displaystyle p_{2}(n;d)={\frac {n \choose 2}{d-n+1}}p(n;d)}$

標準的な誕生日問題とは異なり、nが増加すると、確率は減少する前に最大値に達します。たとえば、d = 365の場合、一意の一致の確率は、 n = 28のときに最大値 0.3864 になります。

基本的な問題では、すべての試行が 1 つの「タイプ」であるとみなします。誕生日の問題は、任意の数のタイプを考慮するように一般化されています。^[18]最も単純な拡張では、2 種類の人々、たとえばm 人の男性とn人の女性がいて、問題は少なくとも 1 人の男性と 1 人の女性が誕生日を共有する確率を特徴付けることになります。(2 人の男性または 2 人の女性が誕生日を共有することはカウントされません。) ここで誕生日が共有されない確率は、

${\displaystyle p_{0}={\frac {1}{d^{m+n}}}\sum _{i=1}^{m}\sum _{j=1}^{n}S_{2}(m,i)S_{2}(n,j)\prod _{k=0}^{i+j-1}d-k}$

ここで、d = 365、S _{2 は}第2種のスターリング数です。したがって、望ましい確率は1 − p ₀です。

この誕生日問題のバリエーションは、総人数m + nに対して一意の解が存在しない点で興味深いものです。たとえば、通常の 50% の確率値は、男性 16 人と女性 16 人の 32 人のグループと、女性 43 人と男性 6 人の 49 人のグループの両方で実現されます。

関連する質問は、人々が一人ずつ部屋に入ってくると、その部屋にすでにいる人と同じ誕生日になる可能性が最も高いのは誰でしょうか? つまり、どのnに対してp ( n ) − p ( n  − 1)が最大になるのでしょうか? 答えは 20 です。最初の一致に対して賞品がある場合、列の最適な位置は 20 番目です。^{[引用が必要]}

誕生日問題では、2人のうちのどちらも事前に選ばれていません。対照的に、n人の人がいる部屋で少なくとも1人の他の人が特定の人（たとえばあなた）と同じ誕生日である確率q ( n )は次のように与えられます。

${\displaystyle q(n)=1-\left({\frac {365-1}{365}}\right)^{n}}$

そして一般的なdは

${\displaystyle q(n;d)=1-\left({\frac {d-1}{d}}\right)^{n}.}$

標準的なケースであるd = 365では、n = 23 を代入すると約 6.1% となり、これは 16 分の 1 未満の確率です。n 人の人がいる部屋の中で、少なくとも 1 人の他の人があなたと同じ誕生日である確率が 50% を超えるには、 nは少なくとも253である必要があります。この数は⁠よりも大幅に大きいです。365/2⁠ = 182.5 : その理由は、部屋にいる他の人の中に誕生日が一致する人がいる可能性が高いからです。

上で説明したように、 n人のグループ内の任意の 1 人の誕生日が他の人と同じである確率は です。同じ (一意ではない) 誕生日を持つ人の予想数は、その確率に人数 ( n ) を掛けることで簡単に計算できます。つまり、次のようになります。 ${\displaystyle q(n-1;d)}$

${\displaystyle n\left(1-\left({\frac {d-1}{d}}\right)^{n-1}\right)}$

(この乗算は、指標変数の期待値が線形であるため、このように行うことができます)。これは、誕生日が共通でない (固有の) 人の期待数は次のようになることを意味します。

${\displaystyle n\left({\frac {d-1}{d}}\right)^{n-1}}$

3 人、4 人など他の人と共有する人の予想人数についても、同様の式を導き出すことができます。

それぞれの誕生日を迎えるまでに何人必要になるかという予想数は、クーポン収集者の問題と呼ばれます。これはnH _nで計算できます。ここで、H _nはn番目の調和数です。365 通りの日付 (誕生日問題) の場合、答えは 2365 です。

もう一つの一般化は、等確率で誕生日がd人いる場合に、 k暦日以内に誕生日を迎えるn人のグループの中に少なくとも1組のペアが見つかる確率を求めることである。^[19]

${\displaystyle {\begin{aligned}p(n,k,d)&=1-{\frac {(d-nk-1)!}{d^{n-1}{\bigl (}d-n(k+1){\bigr )}!}}\end{aligned}}}$

あるペアの誕生日の差がk日以内である確率が 50% を超える ために必要な人数は、次の表に示されています。

したがって、ランダムに選ばれた7人のグループでは、そのうち2人が1週間以内に誕生日を迎える可能性が高くなります。^[19]

異なる誕生日の予想数、つまり少なくとも 1 人の誕生日である日数は次のとおりです。

${\displaystyle d-d\left({\frac {d-1}{d}}\right)^{n}}$

これは、誰の誕生日でもない日の予想数から導かれます。

${\displaystyle d\left({\frac {d-1}{d}}\right)^{n}}$

これは、特定の日が誰の誕生日でもない確率から導かれる。（⁠d − 1/d⁠ )^ん
 期待値が直線的であるため、簡単に合計できます。

たとえば、d = 365の場合、22 人の場合は約 21 種類の誕生日があり、50 人の場合は 46 種類の誕生日があると考えられます。1,000 人の場合は、約 341 種類の誕生日（未登録の誕生日 24 種類）があることになります。

上記は、特定の日に誕生日を迎える人の数の分布から一般化することができ、これは確率が2項分布である。1/d⁠ . 関連する確率にdを掛けると、期待される日数が得られます。たとえば、少なくとも 2 人の (つまり、0 でも 1 でもない) 人の誕生日が共有される日数の期待値は次のとおりです。

$${\displaystyle d-d\left({\frac {d-1}{d}}\right)^{n}-d\cdot {\binom {n}{1}}\left({\frac {1}{d}}\right)^{1}\left({\frac {d-1}{d}}\right)^{n-1}=d-d\left({\frac {d-1}{d}}\right)^{n}-n\left({\frac {d-1}{d}}\right)^{n-1}}$$

[1, d ]からランダムに選ばれたk番目の整数が少なくとも1つの前の選択を繰り返す確率は上記のq ( k − 1; d )に等しい。そのような整数がn個選ばれるときに、選択が前の選択を繰り返す期待総回数は^[20]に等しい。

${\displaystyle \sum _{k=1}^{n}q(k-1;d)=n-d+d\left({\frac {d-1}{d}}\right)^{n}}$

これは、人数から異なる誕生日の予想される数を引いた値に等しいと見ることができます。

誕生日問題の別の定式化では、同じ誕生日のペアを見つけるために必要な平均人数を尋ねます。確率関数 Pr[ n人の人が少なくとも 1 人の誕生日を共有している] を考えると、この平均は分布の平均を決定します。これは、中央値を求める通常の定式化とは対照的です。この問題は、ドナルド・クヌースが著書「The Art of Computer Programming」で分析したいくつかのハッシュアルゴリズムに関連しています。 ^{[21] [22]}に示すように、サイズMの母集団から均一に、復元抽出してサンプルを抽出した場合、ある個体の最初の繰り返しサンプル抽出に必要な試行回数の期待値はn = 1 + Q ( M )であり、ここで

${\displaystyle Q(M)=\sum _{k=1}^{M}{\frac {M!}{(M-k)!M^{k}}}.}$

機能

${\displaystyle Q(M)=1+{\frac {M-1}{M}}+{\frac {(M-1)(M-2)}{M^{2}}}+\cdots +{\frac {(M-1)(M-2)\cdots 1}{M^{M-1}}}}$

シュリニヴァーサ・ラマヌジャンによって研究されており、漸近展開を持つ。

${\displaystyle Q(M)\sim {\sqrt {\frac {\pi M}{2}}}-{\frac {1}{3}}+{\frac {1}{12}}{\sqrt {\frac {\pi }{2M}}}-{\frac {4}{135M}}+\cdots .}$

1年がM = 365日の場合、同じ誕生日のペアを見つけるために必要な平均人数はn = 1 + Q ( M ) ≈ 24.61659で、50%の確率に必要な人数である23人より少し多い。最良の場合、2人で十分である。最悪の場合、最大人数であるM + 1 = 366人が必要となるが、平均すると25人しか必要ではない。

指標ランダム変数を用いた解析は、この問題をより単純かつ近似的に解析することができる。^[23]部屋にいるk人の各ペア( i , j )に対して、指標ランダム変数X _{ij を}次のように 定義する。${\displaystyle 1\leq i\leq j\leq k}$

$${\displaystyle {\begin{alignedat}{2}X_{ij}&=I\{{\text{person }}i{\text{ and person }}j{\text{ have the same birthday}}\}\\[10pt]&={\begin{cases}1,&{\text{if person }}i{\text{ and person }}j{\text{ have the same birthday;}}\\0,&{\text{otherwise.}}\end{cases}}\end{alignedat}}}$$

$${\displaystyle {\begin{alignedat}{2}E[X_{ij}]&=\Pr\{{\text{person }}i{\text{ and person }}j{\text{ have the same birthday}}\}={\frac {1}{n}}.\end{alignedat}}}$$

X を、同じ誕生日の個人のペアを数えるランダム変数と します。

$${\displaystyle X=\sum _{i=1}^{k}\sum _{j=i+1}^{k}X_{ij}}$$

$${\displaystyle {\begin{alignedat}{3}E[X]&=\sum _{i=1}^{k}\sum _{j=i+1}^{k}E[X_{ij}]\\[8pt]&={\binom {k}{2}}{\frac {1}{n}}\\[8pt]&={\frac {k(k-1)}{2n}}\end{alignedat}}}$$

n = 365の場合、k = 28であれば、同じ誕生日のペアの期待数は⁠28 × 27/2 × 365⁠  ≈ 1.0356。したがって、少なくとも 28 人の一致するペアが少なくとも 1 つあると予想できます。

2014年FIFAワールドカップでは、32チームそれぞれに23人の選手が所属していた。公式メンバーリストを分析したところ、16チームに誕生日が同じペアの選手がおり、そのうち5チームには2ペアあった。アルゼンチン、フランス、イラン、韓国、スイスにはそれぞれ2ペア、オーストラリア、ボスニア・ヘルツェゴビナ、ブラジル、カメルーン、コロンビア、ホンジュラス、オランダ、ナイジェリア、ロシア、スペイン、アメリカにはそれぞれ1ペアあった。^[24]

Voracek、Tran、Formannは、大多数の人が、同じ誕生日の人々の確率を達成するために必要な人数を著しく過大評価し、特定のサンプルサイズが与えられた場合に、同じ誕生日の人々の確率を著しく過小評価することを示しました。 ^[25]さらに、心理学の学生と女性は、カジノの訪問者/従業員や男性よりもこの課題で良い成績を収めましたが、自分の推定値に対する自信は低いことがわかりました。

逆の問題は、一定の確率pに対して、確率p ( n ) が与えられたpより小さくなる最大のn 、または確率p ( n )が与えられたpより大きい最小のn を見つけることです。^[要出典]

上記の式をd  = 365とすると、

${\displaystyle n(p;365)\approx {\sqrt {730\ln \left({\frac {1}{1-p}}\right)}}.}$

次の表にいくつかの計算例を示します。

範囲外にある値の一部は、近似値が必ずしも正確ではないことを示すために 色分けされています。

関連する問題に、オペレーションズ・リサーチのナップザック問題の変形である分割問題があります。いくつかの重りが天秤に載せられます。各重りは、1グラムから100万グラム（1トン）の間でランダムに選ばれた整数グラムです。問題は、通常（つまり、1に近い確率で）重りを左腕と右腕の間で移動させて天秤のバランスをとることができるかどうかです。（すべての重りの合計が奇数グラム​​の場合、1グラムの差異は許容されます。）重りが2つまたは3つしかない場合、答えは明らかに「いいえ」です。機能する組み合わせもありますが、ランダムに選択された3つの重りの組み合わせの大部分は機能しません。重りが非常に多い場合、答えは明らかに「はい」です。問題は、ちょうど十分な数はどれくらいか、つまり、バランスをとることが不可能であるのと同じくらい可能であるような重りの数はどれくらいか、ということです。

多くの場合、人々の直感は答えが上にあるということだ100 000。ほとんどの人は、それが数千または数万であると直感しますが、少なくとも数百であるべきだと感じる人もいます。正解は 23 です。 ^{[引用が必要]}

その理由は、正しい比較は重みを左と右に分割する数と比較することである。N個の重みに対して2 N − 1個の異なる分割があり、左^の合計から右の合計を引いたものは、各分割に対する新しいランダムな量と考えることができる。重みの合計の分布はほぼガウス分布で、ピークは500 000 Nと幅1 000 000 √ Nなので、 2 ^{N − 1}がおよそ1 000 000√Nで遷移が発生します。2 ^{23 − 1}は約400万ですが、分布の幅はわずか500万です。 ^[26]

アーサー・C・クラークの 1961 年の小説「月塵の落下」には、地下に閉じ込められた主人公たちが誕生日を祝い、誕生日問題の妥当性について議論する場面があります。物理学者の乗客は、「24 人以上のグループの場合、そのうちの 2 人が同じ誕生日である確率は 50% 以上です」と述べています。最終的に、出席している 22 人のうち、2 人の登場人物が同じ誕生日 (5 月 23 日) であることが明らかになります。

• Abramson, M.; Moser, WOJ (1970). 「More Birthday Surprises」. American Mathematical Monthly . 77 (8): 856– 858. doi :10.2307/2317022. JSTOR  2317022.
• ブルーム、D . (1973)。「誕生日の問題」。アメリカ数学月刊誌。80 (10): 1141– 1142。doi :10.2307/2318556。JSTOR  2318556。
• Kemeny, John G.; Snell, J. Laurie; Thompson, Gerald (1957).有限数学入門(初版).
• マッキニー、EH (1966)。「一般化された誕生日問題」。アメリカ数学月刊誌。73 ( 5): 385– 387。doi : 10.2307/2315408。JSTOR  2315408。
• Mosteller, F. (1962). 「誕生日問題の理解」.数学教師. 55 (5): 322– 325. doi :10.5951/MT.55.5.0322. JSTOR  27956609.Mosteller, Frederick (2006)に再録 。「誕生日問題の理解」。Springer 統計シリーズ、Frederick Mosteller 選集。pp.  349– 353。doi : 10.1007 /978-0-387-44956-2_21。ISBN 978-0-387-20271-6。
• シュネップス、レイラ、コルメズ、コラリー(2013)。「数学の誤り 5 番。ダイアナ・シルベスターの事件: コールド ヒット分析」。数学の裁判。法廷で数字がどのように使用され、悪用されるか。ベーシック ブックス。ISBN 978-0-465-03292-1。
• Sy M. Blinder (2013)。 『基礎数学ガイド：物理、化学、工学の学生のためのレビュー』Elsevier。pp.  5– 6。ISBN 978-0-12-407163-6。

• 閏年の誕生日を説明する誕生日パラドックス
• ワイスタイン、エリック・W.「誕生日の問題」。マスワールド。
• パラドックスを説明するユーモラスな記事
• SOCR EduMaterialsアクティビティ誕生日実験
• 誕生日問題を理解する（よりわかりやすく説明）
• 2012 年ユーロ誕生日。誕生日の問題。誕生日のパラドックスの実際のサッカーの例。
• グライム、ジェームズ。「23: 誕生日の確率」。Numberphile。ブレイディ・ハラン。2017年2月25日時点のオリジナルよりアーカイブ。 2013年4月2日閲覧。
• WolframAlpha で誕生日問題の確率を計算する