クーポン・コレクターの問題の意味と期待値・分散について
1. クーポン・コレクターの問題
クーポン・コレクターの問題（Coupon Collector’s Problem）は、確率論における古典的な問題の一つです。この問題は、例えば、ある種類のクーポンがランダムに配布されるとして、すべての種類のクーポンを集めるために必要なクーポンの時間の期待値を求めるというものです。食玩問題とも呼ばれます。
2. 期待値と分散の計算
2.1. 幾何分布との関係
幾何分布は、「特定の事象が初めて発生するまでの試行回数」を表す確率分布です。この分布がクーポン・コレクター問題に現れる理由は、「まだ集めていない新しいクーポンを取得するまでの試行回数」を表しているためです。具体的には、全$ N $種類のクーポンを集める時間を$ T$、すでに $i−1$種類集めた後に 次の新しいクーポンを集める時間を $t_i $とします。この $T$ と $t_i $を確率変数として考えると、新しいクーポンを集める確率は
$$p_i= \frac{N - (i-1)}{N}$$
また k回目に初めて成功する確率$P_i$は
$$P_i= (1-p_i)^{k-1}p_i$$
2.2. 期待値
幾何分布の期待値は $\frac{1}{p_i}$で表され、期待値の線形性により、全体の期待値$ E[T]$は次のように求められます。
\[E[T]= \sum_{i=1}^{N} E[t_i] = N \left( 1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{N} \right) \]
2.3. 分散の計算
\( t_i \) は幾何分布に従う確率変数であり、その分散は次のように表されます。
\[ \mathrm{V}[t_i] = \frac{1-p_i}{p_i^2} \]
また、全体の分散は次のように表されます。
\[ \mathrm{V}[T] = \sum_{i=1}^{N} \mathrm{V}[t_i] \]
各 \( \mathrm{V}[t_i] \) を計算すると、
\[ \mathrm{V}[t_i]= \frac{1 - p_i}{p_i^2} = \frac{1 - \frac{N-i+1}{N}}{\left(\frac{N-i+1}{N}\right)^2} = \frac{\frac{i-1}{N}}{\left(\frac{N-i+1}{N}\right)^2} = \frac{N(i-1)}{(N-i+1)^2} \]
これを全体の分散に代入します。
\[ \mathrm{Var}(T) = \sum_{i=1}^{N} \frac{N(i-1)}{(N-i+1)^2} \]
