クーポン・コレクター問題

ウィキペディア

クーポンコレクター問題

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/06/24 02:32 UTC 版)

クーポンの種類数 n と全種類を集めるのに必要な試行回数の期待値 E(T) のグラフ

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

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

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

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

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

数学的分析によれば、必要とされる試行回数の期待値は ${\displaystyle \Theta (n\log(n))}$ カテゴリ