誕生日のパラドックス

$D$ は、$n$ 個の成分がすべて異なる並び $(\omega_1,\dots,\omega_n)$ の集合である。$n\leq N$ のとき、$\omega_1$ の選び方は $N$ 通り、$\omega_1$ を決めたとき $\omega_2$ の選び方は $\omega_1$ 以外の $N-1$ 通り、…、$\omega_1,\dots,\omega_{n-1}$ を決めたとき $\omega_n$ の選び方は $N-n+1$ 通りなので、積の法則により $|D|=N(N-1)\cdots(N-n+1)$ である。$|\Omega|=N^n$ で割ると最初の式を得る。$n>N$ のときは、$N$ 個の値しかとらない $n$ 個の成分のうち 2 つは一致するので（鳩の巣原理）$D=\emptyset$ であり、右辺の積も $k=N$ の因子 $1-N/N=0$ を含むので $0$ である。$C$ は $D$ の余事象なので $P(C)=1-P(D)$ である。

$f(x)=e^{-x}-1+x$ とおくと $f'(x)=1-e^{-x}$ は $x<0$ で負、$x>0$ で正なので、$f$ は $x=0$ で最小値 $f(0)=0$ をとり、$x\neq0$ では $f(x)>0$ である。

$0\leq x\leq\frac12$ で $g(x)=\log(1-x)+x+x^2$ とおく（$\log$ は自然対数関数）。$g(0)=0$ であり、
$$ g'(x)=-\frac1{1-x}+1+2x=\frac{x(1-2x)}{1-x}\geq0 $$
なので $g(x)\geq0$、すなわち $\log(1-x)\geq-x-x^2$ である。両辺の指数関数をとればよい。

$n>N$ なら $P(D)=0$ で上からの評価は明らかであり、このとき $n-1\geq N>N/2$ なので下からの評価は主張していない。$n\leq N$ なら thm-birthday-problem-formula の積の因子 $1-k/N$（$0\leq k\leq n-1$）はすべて正であり、lem-birthday-problem-exp-upper より $1-k/N\leq e^{-k/N}$ である。正の数の不等式は掛け合わせてよいので
$$ P(D)\leq\exp\Bigl(-\frac1N\sum_{k=0}^{n-1}k\Bigr)=\exp\Bigl(-\frac{n(n-1)}{2N}\Bigr) $$
である。$n-1\leq N/2$ なら $0\leq k/N\leq\frac12$ なので、lem-birthday-problem-exp-lower より $1-k/N\geq e^{-k/N-k^2/N^2}$ であり、$\sum_{k=0}^{n-1}k^2=\frac{(n-1)n(2n-1)}{6}$ を使って掛け合わせれば下からの評価を得る。

人数を明示して $P_n(D)$ と書く。thm-birthday-problem-formula より $P_{n+1}(D)=P_n(D)\cdot(1-n/N)$ で、$0\leq1-n/N\leq1$（$n\leq N$）または $P_n(D)=0$（$n>N$）なので、$P_n(D)$ は $n$ について単調非増加である。したがって $P_{22}(D)>1/2$ と $P_{23}(D)<1/2$ を示せばよい。以下 $\log2=0.6931471\ldots$ を使う。
$n=23$：thm-birthday-problem-bounds より $P_{23}(D)\leq\exp(-253/365)$ であり、$253/365=0.6931506\ldots>\log2$ なので $P_{23}(D)< e^{-\log2}=1/2$ である。
$n=22$：$n-1=21\leq365/2$ なので下からの評価が使え、$\frac{22\cdot21}{2\cdot365}+\frac{21\cdot22\cdot43}{6\cdot365^2}=\frac{231}{365}+\frac{3311}{133225}=0.6577\ldots<\log2$ だから、$P_{22}(D)>e^{-\log2}=1/2$ である。
よって $n\leq22$ では $P(D)\geq P_{22}(D)>1/2$、すなわち $P(C)<1/2$ であり、$n\geq23$ では $P(D)\leq P_{23}(D)<1/2$、すなわち $P(C)>1/2$ である。

$1\leq i< j\leq n$ について $E_{ij}:=\{\omega\in\Omega\mid\omega_i=\omega_j\}$ とおく。$E_{ij}$ の元は、$\omega_i=\omega_j$ の共通の値（$N$ 通り）と残りの $n-2$ 個の成分（$N^{n-2}$ 通り）で決まるので $|E_{ij}|=N^{n-1}$、$P(E_{ij})=1/N$ である。$C=\bigcup_{i< j}E_{ij}$ であり、和集合の元の個数は各集合の元の個数の和以下なので
$$ P(C)\leq\sum_{i< j}P(E_{ij})=\binom n2\frac1N=\frac{n(n-1)}{2N} $$
である（Sho08 Theorem 8.26、p. 246。和集合の確率を和で押さえるこの不等式は Boole の不等式と呼ばれる）。

前半は prop-birthday-problem-union-bound から直ちに従う。後半は thm-birthday-problem-bounds の上からの評価により $P(D)\leq\exp(-n(n-1)/(2N))\leq e^{-\log2}=\frac12$ となることから従う。

$\sum_{\omega}X(\omega)$ は、$\omega\in\Omega$ と $\omega_i=\omega_j$ を満たす組 $\{i,j\}$ の対の個数である。組 $\{i,j\}$ ごとに数え直すと、各組について $|E_{ij}|=N^{n-1}$ 個の $\omega$ があるので、合計は $\binom n2N^{n-1}$ である。$N^n$ で割ればよい。

独立性から、2 人とも $s$ 日目である確率は $p_s^2$ であり、一致の確率はそれを $s$ について足した $\sum_sp_s^2$ である。
$$ 0\leq\sum_{s=1}^{N}\Bigl(p_s-\frac1N\Bigr)^2=\sum_sp_s^2-\frac2N\sum_sp_s+\frac N{N^2}=\sum_sp_s^2-\frac1N $$
であり、等号はすべての $s$ で $p_s=1/N$ のときに限る。この計算は Sho08 演習 8.36・8.37（p. 249）の内容である。