コンテンツにスキップ

クーポンコレクター問題

出典: フリー百科事典『ウィキペディア(Wikipedia)』
クーポンの種類数 n と全種類を集めるのに必要な試行回数の期待値 E(T) のグラフ

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

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

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

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

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

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

解法

[編集]

期待値の計算

[編集]

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

ここで、 Hnn 番目の調和数である。 調和数の漸近解析英語版を使用して、以下が得られる。

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

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

分散の計算

[編集]

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

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

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

テールの推定

[編集]

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

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

拡張と一般化

[編集]
ここで、 m は固定されている。 m = 1のとき、上述の式が得られる。
  • 同じ一般化のもとでエルデシュとレーニは以下を導いた。

関連項目

[編集]

脚注

[編集]

注釈

[編集]
  1. ^ この項目全体において、log は自然対数を指す。Θについてはランダウの記号を参照。
  2. ^ 全50種類のクーポンを収集するための試行回数の期待値は E(50) = 50(1 + 1/2 + 1/3 + ... + 1/50) = 224.9603 である。期待値の概算は で行え、この場合は となる。

出典

[編集]
  1. ^ 食玩問題”. 2017年9月11日閲覧。
  2. ^ Flajolet, Philippe; Gardy, Danièle; Thimonier, Loÿs (1992), “Birthday paradox, coupon collectors, caching algorithms and self-organizing search”, Discrete Applied Mathematics 39 (3): 207–229, doi:10.1016/0166-218x(92)90177-c, http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.217.5965&rep=rep1&type=pdf 

出典

[編集]

外部リンク

[編集]