更新:2024/11/21

クーポン・コレクターの問題の意味と期待値・分散について

はるか
はるか
クーポン・コレクターの問題って知ってる?
ふゅか
ふゅか
うん!例えば、アイスクリームの蓋に付いているステッカーをランダムに集める場合、全種類を揃えるのに平均でどのくらいのかを計算する問題よね!

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} \]

PR