クーポンコレクター問題

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

クーポンの種類数 n と全種類を集めるのに必要な試行回数の期待値 E(T) のグラフ

具体的には次のような問題である。

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

別の言い方をすると次のようになる。

n 種類の異なるクーポンがあるとき、各種類のクーポンを1回以上引くまでに、何回クーポンを引けば良いか?

数学的分析によれば、必要とされる試行回数の期待値は ${\displaystyle \Theta (n\log(n))}$ である^{[注釈 1]}。例えば n = 50の場合、全50種類のクーポンを収集するには、平均で約225回の試行が必要となる^{[注釈 2]}。

解法

期待値の計算

T を全 n 種のクーポンを収集する時間とし、 t_i を i - 1種のクーポンを収集した後に i 種類目のクーポンを収集する時間とする。T と t_i を確率変数と考える。新しいクーポンを集める確率は p_i = (n − (i − 1))/n である。従って、 t_i は期待値を1/p_i とする幾何分布となる。期待値の線形性により、以下が得られる。

${\displaystyle {\begin{aligned}\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{aligned}}}$

ここで、 H_n は n 番目の調和数である。 調和数の漸近解析（英語版）を使用して、以下が得られる。

${\displaystyle \operatorname {E} (T)=n\cdot H_{n}=n\log n+\gamma n+{\frac {1}{2}}+O(1/n)}$

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

マルコフの不等式を使用して、所望の確率の上限を与えることができる。

${\displaystyle \operatorname {P} (T\geq cnH_{n})\leq {\frac {1}{c}}}$

分散の計算

確率変数 t_i の独立性を用いて、分散が以下のように計算できる。

${\displaystyle {\begin{aligned}\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}}}\\&<\left({\frac {n^{2}}{n^{2}}}+{\frac {n^{2}}{(n-1)^{2}}}+\cdots +{\frac {n^{2}}{1^{2}}}\right)\\&=n^{2}\cdot \left({\frac {1}{1^{2}}}+{\frac {1}{2^{2}}}+\cdots +{\frac {1}{n^{2}}}\right)\\&<{\frac {\pi ^{2}}{6}}n^{2}\end{aligned}}}$

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

チェビシェフの不等式を使用して、所望の確率を決めることができる。

${\displaystyle \operatorname {P} \left(|T-nH_{n}|\geq cn\right)\leq {\frac {\pi ^{2}}{6c^{2}}}}$

テールの推定

異なる上限は、以下の計算から導き出すことができる。${\displaystyle {Z}_{i}^{r}}$ を最初の ${\displaystyle r}$ 回の試行で ${\displaystyle i}$ 番目のクーポンが引けない事象を表すとする。

${\displaystyle {\begin{aligned}P\left[{Z}_{i}^{r}\right]=\left(1-{\frac {1}{n}}\right)^{r}\leq e^{-r/n}\end{aligned}}}$

したがって、${\displaystyle r=\beta n\log n}$については${\displaystyle P\left[{Z}_{i}^{r}\right]\leq e^{(-\beta n\log n)/n}=n^{-\beta }}$となる。

${\displaystyle {\begin{aligned}P\left[T>\beta n\log n\right]=P\left[\bigcup _{i}{Z}_{i}^{\beta n\log n}\right]\leq n\cdot P[{Z}_{1}^{\beta n\log n}]\leq n^{-\beta +1}\end{aligned}}}$

拡張と一般化

• ポール・エルデシュとレーニ・アルフレードは、 T の分布の極限定理を証明した。この結果は、ここまでに述べた境界のさらなる拡張である。

${\displaystyle \operatorname {P} (T<n\log n+cn)\to e^{-e^{-c}}\quad (n\to \infty )}$

• ドナルド・J・ニューマン（英語版）とローレンス・シェップ（英語版）は、全クーポンを m 枚ずつ収集する必要がある場合として、クーポンコレクター問題を一般化した。各クーポンを m 枚収集するのにかかる時間を T_m とする。彼らは、この場合の期待値が以下を満たしていることを示した。

${\displaystyle \operatorname {E} (T_{m})=n\log n+(m-1)n\log \log n+O(n)\quad (n\to \infty )}$

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

• 同じ一般化のもとでエルデシュとレーニは以下を導いた。

${\displaystyle \operatorname {P} {\bigl (}T_{m}<n\log n+(m-1)n\log \log n+cn{\bigr )}\to e^{-e^{-c}/(m-1)!}\quad (n\to \infty )}$

• フィリップ・フラジョレ（英語版）^[2]によると、不均一な確率分布の一般的なケースでは、以下のようになる。

${\displaystyle E(T)=\int _{0}^{\infty }{\big (}1-\prod _{i=1}^{n}(1-e^{-p_{i}t}){\big )}dt}$

関連項目

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