クーポンコレクター問題

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

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

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

数学的分析によれば、必要とされる試行回数の期待値は  であるこの項目全体において、log は自然対数を指す。Θについてはランダウの記号を参照。。例えば n = 50の場合、全50種類のクーポンを収集するには、平均で約225回の試行が必要となる全50種類のクーポンを収集するための試行回数の期待値は E(50) = 50(1 + 1/2 + 1/3 + ... + 1/50) = 224.9603 である。期待値の概算は  で行え、この場合は  となる。。

解法
 期待値の計算 
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.

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