クーポンの種類数
n と全種類を集めるのに必要な試行回数の期待値
E(
T) のグラフ
具体的には次のような問題である。
- 壺の中に n 種類の異なるクーポンが入っている。1回の試行で壺の中から1枚クーポンを引き、引いたものと同じ種類のクーポンを壺の中に戻すものとする。n 種類(全種類)のクーポンを集めようとしたとき、 t 回以上の試行回数が必要となる確率はいくつだろうか?
別の言い方をすると次のようになる。
- n 種類の異なるクーポンがあるとき、各種類のクーポンを1回以上引くまでに、何回クーポンを引けば良いか?
数学的分析によれば、必要とされる試行回数の期待値は である[注釈 1]。例えば n = 50の場合、全50種類のクーポンを収集するには、平均で約225回の試行が必要となる[注釈 2]。
解法
期待値の計算
T を全 n 種のクーポンを収集する時間とし、 ti を i - 1種のクーポンを収集した後に i 種類目のクーポンを収集する時間とする。T と ti を確率変数と考える。新しいクーポンを集める確率は pi = (n − (i − 1))/n である。従って、 ti は期待値を1/pi とする幾何分布となる。期待値の線形性により、以下が得られる。
ここで、 Hn は n 番目の調和数である。 調和数の漸近解析(英語版)を使用して、以下が得られる。
ここで、 はオイラーの定数である。
マルコフの不等式を使用して、所望の確率の上限を与えることができる。
分散の計算
確率変数 ti の独立性を用いて、分散が以下のように計算できる。
なぜならば、 であるからである(バーゼル問題を参照)。
チェビシェフの不等式を使用して、所望の確率を決めることができる。
テールの推定
異なる上限は、以下の計算から導き出すことができる。 を最初の 回の試行で 番目のクーポンが引けない事象を表すとする。
したがって、についてはとなる。
拡張と一般化
- ドナルド・J・ニューマン(英語版)とローレンス・シェップ(英語版)は、全クーポンを m 枚ずつ収集する必要がある場合として、クーポンコレクター問題を一般化した。各クーポンを m 枚収集するのにかかる時間を Tm とする。彼らは、この場合の期待値が以下を満たしていることを示した。
- ここで、 m は固定されている。 m = 1のとき、上述の式が得られる。
- 同じ一般化のもとでエルデシュとレーニは以下を導いた。
- フィリップ・フラジョレ(英語版)[2]によると、不均一な確率分布の一般的なケースでは、以下のようになる。