クーポンコレクター問題

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

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

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

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

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

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

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

解法

期待値の計算

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

$\begin{array}{cc}\mathrm{E}(T)& =\mathrm{E}(t_1)+\mathrm{E}(t_2)+\cdots +\mathrm{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 (\frac{1}{1}+\frac{1}{2}+\cdots +\frac{1}{n})\\ & =n\cdot H_n\end{array}$

ここで、 H_n は n 番目の調和数である。 調和数のテンプレート:仮リンクを使用して、以下が得られる。

$\mathrm{E}(T)=n\cdot H_n=n\log n+\gamma n+\frac{1}{2}+O(1/n)$

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

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

$\mathrm{P}(T\ge cn{H}_n)\le \frac{1}{c}$

分散の計算

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

$\begin{array}{cc}\mathrm{Var}(T)& =\mathrm{Var}(t_1)+\mathrm{Var}(t_2)+\cdots +\mathrm{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{n^2}{n^2}+\frac{n^2}{(n-1{)}^2}+\cdots +\frac{n^2}{1^2})\\ & =n^2\cdot (\frac{1}{1^2}+\frac{1}{2^2}+\cdots +\frac{1}{n^2})\\ & <\frac{{\pi }^2}{6}{n}^2\end{array}$

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

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

$\mathrm{P}(|T-n{H}_n|\ge cn)\le \frac{{\pi }^2}{6c^2}$

テールの推定

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

$\begin{array}{c}P\left[Z_i^r\right]={(1-\frac{1}{n})}^r\le e^{-r/n}\end{array}$

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

$\begin{array}{c}P[T>\beta n\log n]=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{array}$

拡張と一般化

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

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

• テンプレート:仮リンクとテンプレート:仮リンクは、全クーポンを m 枚ずつ収集する必要がある場合として、クーポンコレクター問題を一般化した。各クーポンを m 枚収集するのにかかる時間を T_m とする。彼らは、この場合の期待値が以下を満たしていることを示した。

$\mathrm{E}(T_m)=n\log n+(m-1)n\log \log n+O(n)(n\to \mathrm{\infty })$

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

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

$\mathrm{P}(T_m<n\log n+(m-1)n\log \log n+cn)\to e^{-e^{-c}/(m-1)!}(n\to \mathrm{\infty })$

• テンプレート:仮リンクによると、不均一な確率分布の一般的なケースでは、以下のようになる。

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

関連項目

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

出典

• テンプレート:Citation.
• テンプレート:Citation.
• テンプレート:Citation.
• テンプレート:Citation
• テンプレート:Citation.
• テンプレート:Citation.
• テンプレート:Citation.

外部リンク

• "Coupon Collector Problem" by Ed Pegg, Jr., the Wolfram Demonstrations Project. Mathematica package.
• How Many Singles, Doubles, Triples, Etc., Should The Coupon Collector Expect?, a short note by Doron Zeilberger.