クーポンコレクター問題

**クーポンコレクター問題**（クーポンコレクターもんだい、）とは、確率論における「全てのクーポンを集めると何らかの特典が得られる」場合に、何回クーポンを引けばよいかという問題である。「クーポンコレクター」と表現しているが、ソーシャルゲームで問題視されたコンプリートガチャをはじめ、トレーディングカード、カプセルトイ、ブラインドパッケージの食玩などで全種類を集める（コンプリートする）場合にも適用できる問題である。そのため、日本においては「**食玩問題 **」とも呼ばれる。

具体的には次のような問題である。
:壺の中に *n* 種類の異なるクーポンが入っている。1回の試行で壺の中から1枚クーポンを引き、引いたものと同じ種類のクーポンを壺の中に戻すものとする。*n* 種類（全種類）のクーポンを集めようとしたとき、 *t* 回以上の試行回数が必要となる確率はいくつだろうか? 

別の言い方をすると次のようになる。
:*n* 種類の異なるクーポンがあるとき、各種類のクーポンを1回以上引くまでに、何回クーポンを引けば良いか?

数学的分析によれば、必要とされる試行回数の期待値は \Theta(n\log(n)) である。例えば *n*&nbsp;=&nbsp;50の場合、全50種類のクーポンを収集するには、平均で約225回の試行が必要となる。

## 解法
### 期待値の計算
*T* を全 *n* 種のクーポンを収集する時間とし、 *t<sub>i</sub>* を *i - 1*種のクーポンを収集した後に *i* 種類目のクーポンを収集する時間とする。*T* と *t<sub>i</sub>* を確率変数と考える。新しいクーポンを集める確率は *p<sub>i</sub>* = (*n*&nbsp;−&nbsp;(*i*&nbsp;−&nbsp;1))/*n* である。従って、 *t<sub>i</sub>* は期待値を1/*p<sub>i</sub>* とする幾何分布となる。期待値の線形性により、以下が得られる。
:
\begin{align}
\operatorname{E}(T) &= \operatorname{E}(t_1) + \operatorname{E}(t_2) + \cdots + \operatorname{E}(t_n)
= \frac{1}{p_1} + \frac{1}{p_2} +  \cdots + \frac{1}{p_n} \\
&= \frac{n}{n} + \frac{n}{n-1} +  \cdots + \frac{n}{1} \\
&= n \cdot \left(\frac{1}{1} + \frac{1}{2} + \cdots + \frac{1}{n}\right) \\
&= n \cdot H_n
\end{align}


ここで、 *H<sub>n</sub>* は *n* 番目の調和数である。 調和数のを使用して、以下が得られる。
:
\operatorname{E}(T)  = n \cdot H_n = n \log n + \gamma n + \frac{1}{2} + O(1/n)

ここで、 \gamma \approx 0.5772156649 はオイラーの定数である。

マルコフの不等式を使用して、所望の確率の上限を与えることができる。
:\operatorname{P}(T \geq cn H_n) \le \frac{1}{c}

### 分散の計算
確率変数 *t<sub>i</sub>* の独立性を用いて、分散が以下のように計算できる。
:
\begin{align}
\operatorname{Var}(T)& = \operatorname{Var}(t_1) + \operatorname{Var}(t_2) + \cdots + \operatorname{Var}(t_n) \\
&= \frac{1-p_1}{p_1^2} + \frac{1-p_2}{p_2^2} +  \cdots + \frac{1-p_n}{p_n^2} \\
&

なぜならば、 \frac{\pi^2}6=\frac{1}{1^2}+\frac{1}{2^2}+\cdots+\frac{1}{n^2}+\cdots であるからである（バーゼル問題を参照）。

チェビシェフの不等式を使用して、所望の確率を決めることができる。
:\operatorname{P}\left(|T- n H_n| \geq cn\right) \le \frac{\pi^2}{6c^2}

### テールの推定
異なる上限は、以下の計算から導き出すことができる。{Z}_i^r を最初の r 回の試行で i 番目のクーポンが引けない事象を表すとする。
:
\begin{align}
P\left [ {Z}_i^r \right ] = \left(1-\frac{1}{n}\right)^r \le e^{-r / n}
\end{align}


したがって、r = \beta n \log nについてはP\left [ {Z}_i^r \right ] \le e^{(-\beta n \log n ) / n} = n^{-\beta}となる。
:
\begin{align}
P\left [ T > \beta n \log n \right ] = P \left [ 	\bigcup_i {Z}_i^{\beta n \log n} \right ] \le n \cdot P [ {Z}_1^{\beta n \log n} ] \le n^{-\beta + 1}
\end{align}


## 拡張と一般化
* ポール・エルデシュとレーニ・アルフレードは、 *T* の分布の極限定理を証明した。この結果は、ここまでに述べた境界のさらなる拡張である。
::
\operatorname{P}(T 

* とは、全クーポンを *m* 枚ずつ収集する必要がある場合として、クーポンコレクター問題を一般化した。各クーポンを *m* 枚収集するのにかかる時間を *T<sub>m</sub>* とする。彼らは、この場合の期待値が以下を満たしていることを示した。
::
\operatorname{E}(T_m) =  n \log n + (m-1) n \log\log n + O(n) \quad (n\to\infty)

:ここで、 *m* は固定されている。 *m* = 1のとき、上述の式が得られる。

* 同じ一般化のもとでエルデシュとレーニは以下を導いた。
::
\operatorname{P}\bigl(T_m 

* によると、不均一な確率分布の一般的なケースでは、以下のようになる。
::
E(T)=\int_0^\infty \big(1-\prod_{i=1}^n(1-e^{-p_it})\big)dt


## 関連項目
* コンプリートガチャ
* 食玩 / カプセルトイ / ブラインドパッケージ
* 誕生日のパラドックス（誕生日問題）
* Watterson estimator

## 脚注
### 注釈

### 出典

## 出典
*.
*.
*.
*
*.
*.
*.

## 外部リンク
* "Coupon Collector Problem" by Ed Pegg, Jr., the Wolfram Demonstrations Project. Mathematica package.
* *[http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/coupon.html How Many Singles, Doubles, Triples, Etc., Should The Coupon Collector Expect?]*, a short note by Doron Zeilberger.