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