クーポンコレクター問題
ウィキペディア フリーな encyclopedia
確率論において、クーポンコレクター問題(クーポンコレクターもんだい、英語: Coupon collector's problem)とは、 「全てのクーポンを集めると、何らかの特典が得られる」ような場合に、何回クーポンを引けば良いかという問題である。「クーポンコレクター」と表現しているが、ソーシャルゲームにおけるコンプリートガチャや、(全て集めることで特典があるわけではないが)カプセルトイ・食玩・トレーディングカード等で全種類を集める場合にも適用できる問題である。日本においては食玩問題 [1]とも呼ばれる。
具体的には次のような問題である。
- 壺の中に n 種類の異なるクーポンが入っている。1回の試行で壺の中から1枚クーポンを引き、引いたものと同じ種類のクーポンを壺の中に戻すものとする。n 種類(全種類)のクーポンを集めようとしたとき、 t 回以上の試行回数が必要となる確率はいくつだろうか?
別の言い方をすると次のようになる。
- n 種類の異なるクーポンがあるとき、各種類のクーポンを1回以上引くまでに、何回クーポンを引けば良いか?
数学的分析によれば、必要とされる試行回数の期待値は である[注釈 1]。例えば n = 50の場合、全50種類のクーポンを収集するには、平均で約225回の試行が必要となる[注釈 2]。