クーポンコレクター問題

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

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

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

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

解法

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

ここで、 Hn は n 番目の調和数である。 調和数のを使用して、以下が得られる。

ここで、  はオイラーの定数である。

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

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

なぜならば、  であるからである（バーゼル問題を参照）。

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

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

したがって、についてはとなる。

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

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

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

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

 によると、不均一な確率分布の一般的なケースでは、以下のようになる。

関連項目 

 Watterson estimator
 誕生日問題
 コンプリートガチャ
 食玩

脚注

注釈

出典

出典 
.
.
.

.
.
.

外部リンク 
 "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.

証明を含む記事
確率問題
ギャンブルの数学
数学に関する記事