誕生日が被る確率の話 - Essaytial Machine Learning

　結論：分からないものは分からない。

概要

　特定人数からなる集団内で同じ誕生日の人がいる確率はどれぐらいか、という問題がある。普通は誕生日が独立同分布な一様分布に従うと仮定して23人の集団で50%を超えるとされるが、実際はおそらく一様分布ではないし独立同分布でもない。実際の分布と従属性は分からないので分かる範囲で論じる。

誕生日が従う分布

　誕生日が従う分布は一般に一様分布とは限らず、日本ではこんな感じらしい。これは順位付けの結果なので実際の確率がどうなっているのかは分からないが、7月～9月に偏りがあることは見て取れる。他にも4月2日や12月25日等は確率が高まる理由付けもできるし、正月や盆の連休に確率が下がるのもまあ納得できる。2月29日が特に低いことも容易に想像できるだろう*1。

　では誕生日が一様分布に従わない場合に誕生日が被る確率について考えてみよう。といっても具体的な分布が分からければ限度はあるので、とりあえず独立同分布と仮定して取り得る範囲を調べよう。最大値は全員が1月1日に産みたい人から産まれた謎の集団でも想定すれば確率1で誕生日が被ることが分かる。

　最小値は以下の通り定式化できる。違う星で論じることも考えて1年は $D$ 日あるとし、元日のような起算日を決めて日付を $1, \dots, D$ で番号付ける。さらに集団の構成員も $1, \dots, N$ で番号付けて、 $X_i$ を $i$ 番目の人の誕生日を表す独立同分布な確率変数とする。 $i$ 番目の人の誕生日が $d$ である確率を $P(X_i=d) = a_d$ とすると、全員の誕生日が異なる確率は、対称性から

$\displaystyle \begin{align} P(\forall i, j \ X_i \neq X_j) & = N! P(X_1 \lt \dots X_N) \\ & = N! \sum_{i_N=N}^D a_{i_N} \sum_{i_{N-1}=N-1}^{i_N-1} a_{i_{N-1}} \dots \sum_{i_1=1}^{i_2-1} a_{i_1}, \end{align}$

なので、最大化問題としては

$\displaystyle \begin{align} \text{maximize}: & & f_N(a) & = \sum_{i_N=N}^D a_{i_N} \sum_{i_{N-1}=N-1}^{i_N-1} a_{i_{N-1}} \dots \sum_{i_1=1}^{i_2-1} a_{i_1}, \\ \text{subject to}: & & g(a) & = \sum_{i=1}^D a_i-1 = 0, \quad a_i \geq 0, \end{align}$

と書かれる。これに対して Lagrange 未定乗数法を利用すると

$\displaystyle \begin{align} \text{stationarize}: & & & L(a, \lambda) = f_N(a) + \lambda g(a), \\ \text{subject to}: & & & a_i \geq 0, \end{align}$

という停留化問題となり、停留点（の候補）は以下の連立方程式の解で与えられる：

$\displaystyle \begin{align} \frac{\partial}{\partial a_i} L(a, \lambda) & = \sum_{\begin{gathered} N-1 \leq i_{N-1} \leq D, \\ i_{N-1} \neq i \end{gathered}} a_{i_{N-1}} \sum_{\begin{gathered} N-2 \leq i_{N-2} \lt i_{N-1}, \\ i_{N-2} \neq i \end{gathered}} a_{i_{N-2}} \dots \sum_{\begin{gathered} 1 \leq i_1 \lt i_2, \\ i_1 \neq i \end{gathered}} a_{i_1} + \lambda = 0, \\ \frac{\partial}{\partial \lambda} L(a, \lambda) & = g(a) = 0, \end{align}$

ここで、 $a^{[i]} = (a_1, \dots, a _ {i-1}, 0, a _ {i+1}, \dots, a_D)$ と書くと

$\displaystyle \begin{align} f_m(a) & = \sum_{\begin{gathered} m \leq i_m \leq D, \\ i_m \neq i \end{gathered}} a_{i_m} \sum_{\begin{gathered} m-1 \leq i_{m-1} \lt i_m, \\ i_{m-1} \neq i \end{gathered}} a_{i_{m-1}} \dots \sum_{\begin{gathered} 1 \leq i_1 \lt i_2, \\ i_1 \neq i \end{gathered}}a_{i_1} \\ & + a_i \sum_{\begin{gathered} m-1 \leq i_{m-1} \leq D, \\ i_{m-1} \neq i \end{gathered}} a_{i_{m-1}} \sum_{\begin{gathered} m-2 \leq i_{m-2} \lt i_{m-1}, \\ i_{m-2} \neq i \end{gathered}} a_{i_{m-2}} \dots \sum_{\begin{gathered} 1 \leq i_1 \lt i_2, \\ i_1 \neq i \end{gathered}} a_{i_1} \\ & = f_m(a^{[i]})+a_i f_{m-1}(a^{[i]}) \end{align}$

より $\frac{\partial}{\partial a_i} L(a, \lambda) = f _ {N-1}(a^{[i]})+\lambda$ であり、連立方程式の解 $(a, \lambda) = (\alpha, \lambda^*)$ に対して $f _ {N-1}(\alpha^{[i]})$ が $i$ に依らない値を取ることが分かる。また、 $i \neq j$ に対して

$f_{N-1}(a^{[i]}) = f_{N-1}((a^{[i]})^{[j]}) + a_j f_{N-2}((a^{[i]})^{[j]})$

であり、 $(a^{[i]})^{[j]} = (a^{[j]})^{[i]}$ に注意すると $\alpha_j f _ {N-2}((\alpha^{[i]})^{[j]}) = \alpha_i f _ {N-2}((\alpha^{[i]})^{[j]})$ が得られる。まず $\forall \alpha_i \gt 0$ の場合を考えると、 $f _ {N-2}((\alpha^{[i]})^{[j]}) \gt 0$ より $\alpha_i = \alpha_j$ となり、停留値として

$\displaystyle L(\alpha, \lambda^*) = \frac{1}{D^N} \frac{D!}{(D-N)! N!}$

が得られる。 $\exists \alpha_i = 0$ の時は日付が $D-1$ 通りの場合に帰着され、停留値が帰納的に

$\displaystyle \frac{1}{(D-1)^N} \frac{(D-1)!}{(D-N-1)! N!} ,\dots, \frac{1}{(N+1)^N} \frac{(N+1)!}{N!} ,\frac{1}{N^N}, 0$

と得られる。ここで $k \geq N$ に対して

$\displaystyle \frac{1}{(k+1)^N} \frac{(k+1)!}{(k-N+1)! N!} = \frac{k^N}{(k+1)^{N-1}} \frac{1}{k-N+1} \frac{1}{k^N} \frac{k!}{(k-N)! N!},$ $\displaystyle (k+1)^{N-1}(k-N+1) \leq \left( \frac{(N-1)(k+1)+(k-N+1)}{N} \right)^N = k^N$

より、得られた停留値は $\alpha_i \neq 0$ となる個数について単調増加なので、最大のものは $\alpha_1 = \dots = \alpha_D = \frac{1}{D}$ の時の $\frac{1}{D ^ N} \frac{D!}{(D-N)! N!}$ だ。あとは $f_N(a)$ が連続なので閉集合 $\{ a \ | \ \sum a_i = 1, \ a_i \geq 0 \}$ で最大値を持つことから、求める確率は

$\displaystyle P(\forall i, j \ X_i \neq X_j) = N! \frac{1}{D ^ N} \frac{D!}{(D-N)! N!} = \frac{1}{D ^ N} \frac{D!}{(D-N)!}$

だと分かる。これは誕生日が $\alpha_1 = \dots = \alpha_D = \frac{1}{D}$ の一様分布に従う場合の被らない確率なので、一様にランダムより偏りがある方が被る確率が高い、という直感的理解が正しいことが示せた。

独立同分布でない場合

　確率論の立場で何か論じられることってあるんだろうか。被る確率の最大値は前節と同じく1だ。最小値に関しては $N \leq D$ である限り、絶対 $i$ 日目に産みたい人から産まれた人を集団の $i$ 番目に割り当てれば被る確率は0になる。 $N \gt D$ なら巣箱の原理から確率1になるのが分かる。

　社会学的には病院の受け入れ能力だったり役所の処理能力だったりを考えるなり、心理学的には知人の出産情報を聞いた時の心情だったりを考えるなりすればいいんじゃないかな。

*1:他の日の4分の1程度の確率にはならない気がする。