知っているとゲームや日常生活で役立つ確率の問題をまとめよう。よく知られた関係式は関係するページのリンクを載せ、本ページではwebで見つけられなかった関係式の証明のみ記述する。

問題１:低確率事象の繰り返し
非常に低確率で成功する事象を成功するまで何度も繰り返す、という状況はしばしば現れる問題である。


$M$回繰り返したときに、一度でも成功する確率$p_N(M)$は、 と見積もれる。等号は$M/N=\text{const.}$かつ$N \rightarrow \infty$で成立する。Table. 1に$p_N(M)$の具体的な値を示す。 特に、$p_N(M=N)$はせいぜい6割強で直観よりも小さい。


また、一度でも成功するまでの回数の期待値は$N$、標準偏差は$\sqrt{N(N-1)} \simeq N$と求まる。すなわち、標準偏差は期待値とほぼ同一で、事象を必ず成功させるために必要な試行回数のバラツキは直観よりも大きい。これは低確率の事象を必ず成功させたい時、留意すべき事実である。


問題2: 誕生日のパラドックス
次は、$N$種類のグッズを等確率でランダムに入手していくと、入手回数が何回のときに同一のグッズが重複してしまうか、という疑問に応える問題である。


これは誕生日のパラドックスと呼ばれる問題である。以前、解説したように（リンク：一般化された誕生日のパラドックス）、$N$が十分大きいとき（$N \geq 100$で誤差1%以内で正しい）に、$M$回目までに重複が現れる確率は と近似できる。
これから$M \simeq \sqrt{N}$で重複が起こる事が推測できる。実際、この期待値$\langle M(N) \rangle$の厳密値は初等関数で表せないが、近似式として が成立する事を示せる（下記「補足1」参照のこと）。実際、Fig.1から分かるように、この近似式は非常によい精度で成立する。つまり、$N$種のグッズを集めていくと、およそ$M = 1.25 \sqrt{N}$の回数（例えば$N=10000$であれば$M=125$回）で重複が起こるという事だ。この回数は直観に反して非常に小さい。 


問題3: 席替え問題（完全順列）
次は、クラスで全員の席をランダムに席替えしたときに、全員が以前と異なる席に割り当てられるか？という問題を考える。プレゼントを皆で持ち寄って交換する際に、全員が自分以外のプレゼントをもらえるか、も同じ問題である。


この問題は完全順列（攪乱順列）として知られ、その性質は古くからよく研究されている。この確率$p_N$は、 \begin{equation} p_N= \sum_{k=0}^N\frac{(-1)^k}{k!}, \lim_{N \rightarrow \infty} p(N)= \frac{1}{e} \end{equation} となる。Table.2は$N$の具体的な値の数値結果であるが、$N=5$にて極限値$1/e$とほぼ等しい。


また、この確率事象で面白いのは、同一の席に座る人数の期待値$E$も標準偏差$\sigma$も$N$に依存せず、 \begin{equation} E= \sigma=1 \end{equation} が成立する事である（この証明は、下記「補足2」参照のこと）。 つまり、$N$がいくら大きくなっても同じ席に座っている人は1人ぐらい居るということである。

---

補足1: 誕生日問題の期待値の近似式
$M$回目で初めて重複が生じる確率は$q_N(M)= p_N(M)- p_N(M-1)$と書ける。また、$p_N(1)=0$かつ$p_N(N+1)=1$であることに注意しよう。 この時、期待値$\langle M(N) \rangle$は と計算される。 ここで、$\langle M(N) \rangle$を$N=1$と $N \gg 1$の２つの場合に対して評価しよう。

1. $N=1$のとき
   このとき、$M=2$で$100\%$の確率で重複が起こるから。 \begin{equation} \langle M(1) \rangle =2 \end{equation} となる。
2. $N \gg 1$のとき
   $p_N(M) = 1- \exp[-M^2/(2N)]$と近似出来るから、
   \begin{equation} \langle M(N) \rangle\simeq 2 + \sum_{M=1}^{N} \exp \left[-\frac{M^2}{2N} \right] \end{equation}
   この和を積分で近似し (厳密にはEuler-Maclaurin公式で正当化する)、Gauss積分の公式を使うと、
   \begin{equation} \begin{split} \langle M(N) \rangle &\simeq 2 + \int_{1}^{N} \exp \left[-\frac{M^2}{2N} \right] dM \\ &= 2 + \sqrt{2N}\int_{\frac{1}{\sqrt{2N}}}^{\sqrt{\frac{N}{2}}} \exp \left[-x^2 \right] dx \\ &\simeq 2 + \sqrt{2N} \int_{0}^{\infty} \exp \left[-x^2 \right] dx \\ &= \sqrt{\frac{\pi}{2}} \cdot \sqrt{N} +O(1) \end{split} \end{equation}

これら$N=1$と$N \gg 1$の2つの結果を補間すると、近似式として、 を得る。

補足2: 席替え問題の期待値と標準偏差
$N$人の席替えで、$k$人だけが同じ席のままになる確率$q(k)$を考える。$N$人から$k$人を選ぶ組み合わせの数は$N!/(k!(N-k)!) $通りあり、$N-k$人の席が全て異なる場合の数は$(N-k)! p_{N-k}$通りあるから、 となる。当然$\sum_{k=0}^N q(k)=1$が成立するから \begin{equation} \sum_{k=0}^N \frac{p_{N-k}}{k!} =1 \end{equation} が成立する。 この式から期待値$\langle k \rangle $は、 と計算される。また、$\langle k^2 \rangle $は、 と計算される。 よって、標準偏差$\sigma$は、$ \sigma=\sqrt{\langle k^2 \rangle - \langle k \rangle^2}=1$ となる。