クーポンコレクター問題

確率論において、クーポンコレクター問題（クーポンコレクターもんだい、）とは、
「全てのクーポンを集めると、何らかの特典が得られる」ような場合に、何回クーポンを引けば良いかという問題である。「クーポンコレクター」と表現しているが、ソーシャルゲームにおけるコンプリートガチャや、（全て集めることで特典があるわけではないが）カプセルトイ・食玩・トレーディングカード等で全種類を集める場合にも適用できる問題である。日本においては食玩問題 とも呼ばれる。
具体的には次のような問題である。
別の言い方をすると次のようになる。
数学的分析によれば、必要とされる試行回数の期待値は formula_1 である。例えば "n" = 50の場合、全50種類のクーポンを収集するには、平均で約225回の試行が必要となる。
解法.
期待値の計算.
"T" を全 "n" 種のクーポンを収集する時間とし、 "ti" を "i - 1"種のクーポンを収集した後に "i" 種類目のクーポンを収集する時間とする。"T" と "ti" を確率変数と考える。新しいクーポンを集める確率は "pi" = ("n" − ("i" − 1))/"n" である。従って、 "ti" は期待値を1/"pi" とする幾何分布となる。期待値の線形性により、以下が得られる。
ここで、 "Hn" は "n" 番目の調和数である。 調和数のを使用して、以下が得られる。
ここで、 formula_4 はオイラーの定数である。
マルコフの不等式を使用して、所望の確率の上限を与えることができる。
分散の計算.
確率変数 "ti" の独立性を用いて、分散が以下のように計算できる。
なぜならば、 formula_7 であるからである（バーゼル問題を参照）。
チェビシェフの不等式を使用して、所望の確率を決めることができる。
テールの推定.
異なる上限は、以下の計算から導き出すことができる。formula_9 を最初の formula_10 回の試行で formula_11 番目のクーポンが引けない事象を表すとする。
したがって、formula_13についてはformula_14となる。