誕生日が重なる確率

確率の例題で「同じクラスに，同じ誕生日の人が高確率で存在すること」（誕生日のパラドックス - Wikipedia）を題材とした問題がよく取り上げられます．

誕生日ならちょっとびっくりする例で済むのですが，生体認証やDNA鑑定で同じことが起きるため，問題となるそうです（参考文献[1]）．
➡他人受入率（FAR）とは - IT用語辞典 e-Words

一般論

$k$人が$n$個の分類のいずれかに等確率で属するとする．
例えば，誕生日を考えるときには$n=365$である．

$k$人がすべて異なる分類に属する確率は

\begin{aligned}
P(n, k)
&= 1 \cdot \frac{n-1}{n} \cdot \frac{n-2}{n} \cdots \frac{n-k+1}{n} \\
&= \prod_{m=0}^{k-1} \frac{n-m}{n}
= \prod_{m=0}^{k-1} \biggl(1 - \frac{m}{n}\biggr)
\end{aligned}

したがって，同じ分類に属する人がいる確率は

\begin{aligned}
1 - P(n, k)
\end{aligned}

となる．

概算の方法

$k/n \ll 1$の場合

\begin{aligned}
P(n, k)
&\simeq \prod_{m=0}^{k-1} e^{-m/n}
= \exp\biggl(-\frac{1}{n} \sum_{m=0}^{k-1}m \biggr)
= e^{-(k-1)k/2n } \\
&\simeq e^{-k^{2}/2n }
\end{aligned}

したがって，同じ分類に属する人がいる確率は

\begin{aligned}
1 - P(n, k)
&\simeq 1 - e^{-k^{2}/2n }
\end{aligned}

となる．

この確率が$1/2$を超えるための人数$k$は

\begin{aligned}
& e^{-k^{2}/2n } < 1/2 \\
\Leftrightarrow & k > \sqrt{2 \ln 2} \sqrt{n} \simeq 1.18 \sqrt{n}
\end{aligned}

と，$\sqrt{n}$に比例する（参考：正規分布の半値幅（FWHM） - Notes_JP）．

例：

誕生日が重なる確率は，$n=365$として$k > 22$となる．
月だけが重なる確率は，$n=12$として$k > 4$となる．
日だけが重なる確率は，$n=30$として$k > 6$となる．