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

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

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

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

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

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

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

${\displaystyle {\begin{aligned}\operatorname {E} (T)&=\operatorname {E} (t_{1})+\operatorname {E} (t_{2})+\cdots +\operatorname {E} (t_{n})={\frac {1}{p_{1))}+{\frac {1}{p_{2))}+\cdots +{\frac {1}{p_{n))}\\&={\frac {n}{n))+{\frac {n}{n-1))+\cdots +{\frac {n}{1))\\&=n\cdot \left({\frac {1}{1))+{\frac {1}{2))+\cdots +{\frac {1}{n))\right)\\&=n\cdot H_{n}\end{aligned))}$

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

${\displaystyle \operatorname {E} (T)=n\cdot H_{n}=n\log n+\gamma n+{\frac {1}{2))+O(1/n)}$

ここで、 ${\displaystyle \gamma \approx 0.5772156649}$ はオイラーの定数である。

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

${\displaystyle \operatorname {P} (T\geq cnH_{n})\leq {\frac {1}{c))}$

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

${\displaystyle {\begin{aligned}\operatorname {Var} (T)&=\operatorname {Var} (t_{1})+\operatorname {Var} (t_{2})+\cdots +\operatorname {Var} (t_{n})\\&={\frac {1-p_{1)){p_{1}^{2))}+{\frac {1-p_{2)){p_{2}^{2))}+\cdots +{\frac {1-p_{n)){p_{n}^{2))}\\&<\left({\frac {n^{2)){n^{2))}+{\frac {n^{2)){(n-1)^{2))}+\cdots +{\frac {n^{2)){1^{2))}\right)\\&=n^{2}\cdot \left({\frac {1}{1^{2))}+{\frac {1}{2^{2))}+\cdots +{\frac {1}{n^{2))}\right)\\&<{\frac {\pi ^{2)){6))n^{2}\end{aligned))}$

なぜならば、 ${\displaystyle {\frac {\pi ^{2)){6))={\frac {1}{1^{2))}+{\frac {1}{2^{2))}+\cdots +{\frac {1}{n^{2))}+\cdots }$ であるからである（バーゼル問題を参照）。

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

${\displaystyle \operatorname {P} \left(|T-nH_{n}|\geq cn\right)\leq {\frac {\pi ^{2)){6c^{2))))$

異なる上限は、以下の計算から導き出すことができる。${\displaystyle {Z}_{i}^{r))$ を最初の ${\displaystyle r}$ 回の試行で ${\displaystyle i}$ 番目のクーポンが引けない事象を表すとする。

${\displaystyle {\begin{aligned}P\left[{Z}_{i}^{r}\right]=\left(1-{\frac {1}{n))\right)^{r}\leq e^{-r/n}\end{aligned))}$

したがって、${\displaystyle r=\beta n\log n}$については${\displaystyle P\left[{Z}_{i}^{r}\right]\leq e^{(-\beta n\log n)/n}=n^{-\beta ))$となる。

${\displaystyle {\begin{aligned}P\left[T>\beta n\log n\right]=P\left[\bigcup _{i}{Z}_{i}^{\beta n\log n}\right]\leq n\cdot P[{Z}_{1}^{\beta n\log n}]\leq n^{-\beta +1}\end{aligned))}$

• ポール・エルデシュとレーニ・アルフレードは、 T の分布の極限定理を証明した。この結果は、ここまでに述べた境界のさらなる拡張である。

${\displaystyle \operatorname {P} (T<n\log n+cn)\to e^{-e^{-c))\quad (n\to \infty )}$

• ドナルド・J・ニューマン（英語版）とローレンス・シェップ（英語版）は、全クーポンを m 枚ずつ収集する必要がある場合として、クーポンコレクター問題を一般化した。各クーポンを m 枚収集するのにかかる時間を T_m とする。彼らは、この場合の期待値が以下を満たしていることを示した。

${\displaystyle \operatorname {E} (T_{m})=n\log n+(m-1)n\log \log n+O(n)\quad (n\to \infty )}$

ここで、 m は固定されている。 m = 1のとき、上述の式が得られる。

• 同じ一般化のもとでエルデシュとレーニは以下を導いた。

${\displaystyle \operatorname {P} {\bigl (}T_{m}<n\log n+(m-1)n\log \log n+cn{\bigr )}\to e^{-e^{-c}/(m-1)!}\quad (n\to \infty )}$

• フィリップ・フラジョレ（英語版）^[2]によると、不均一な確率分布の一般的なケースでは、以下のようになる。

${\displaystyle E(T)=\int _{0}^{\infty }{\big (}1-\prod _{i=1}^{n}(1-e^{-p_{i}t}){\big )}dt}$

• コンプリートガチャ
• 食玩 / カプセルトイ / ブラインドパッケージ
• 誕生日のパラドックス（誕生日問題）
• Watterson estimator

• Blom, Gunnar; Holst, Lars; Sandell, Dennis (1994), “7.5 Coupon collecting I, 7.6 Coupon collecting II, and 15.4 Coupon collecting III”, Problems and Snapshots from the World of Probability, New York: Springer-Verlag, pp. 85–87, 191, ISBN 0-387-94161-4, MR1265713, https://books.google.com/books?id=KCsSWFMq2u0C&pg=PA85 .
• Dawkins, Brian (1991), “Siobhan's problem: the coupon collector revisited”, The American Statistician 45 (1): 76–82, doi:10.2307/2685247, JSTOR 2685247, https://jstor.org/stable/2685247 .
• Erdős, Paul; Rényi, Alfréd (1961), “On a classical problem of probability theory”, Magyar Tudományos Akadémia Matematikai Kutató Intézetének Közleményei 6: 215–220, MR0150807, http://www.renyi.hu/~p_erdos/1961-09.pdf .
• Newman, Donald J.; Shepp, Lawrence (1960), “The double dixie cup problem”, American Mathematical Monthly 67: 58–61, doi:10.2307/2308930, MR0120672 
• 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, MR1189469, http://algo.inria.fr/flajolet/Publications/alloc2.ps.gz .
• Isaac, Richard (1995), “8.4 The coupon collector's problem solved”, The Pleasures of Probability, Undergraduate Texts in Mathematics, New York: Springer-Verlag, pp. 80–82, ISBN 0-387-94415-X, MR1329545, https://books.google.com/books?id=a_2vsIx4FQMC&pg=PA80 .
• Motwani, Rajeev; Raghavan, Prabhakar (1995), “3.6. The Coupon Collector's Problem”, Randomized algorithms, Cambridge: Cambridge University Press, pp. 57–63, MR1344451, https://books.google.com/books?id=QKVY4mDivBEC&pg=PA57 .

• "Coupon Collector Problem" by Ed Pegg, Jr., the Wolfram Demonstrations Project. Mathematica package.
• How Many Singles, Doubles, Triples, Etc., Should The Coupon Collector Expect?, a short note by Doron Zeilberger.

表 話 編 歴 確率論
確率の歴史	アンドレイ・コルモゴロフ トーマス・ベイズ アンドレイ・マルコフ ジョゼフ・L・ドゥーブ 伊藤清
確率の定義	客観確率 統計的確率 古典的確率 公理的確率 主観確率 ベイズ確率 確率の拡張 外確率 負の確率
基礎概念	モデル 試行 結果 事象 標本空間 確率測度 確率空間 確率変数 確率変数の収束 確率分布 離散確率分布 連続確率分布 同時分布 周辺分布 条件付き確率分布 独立同分布 関数 確率質量関数 確率密度関数 累積分布関数 特性関数 用語 独立 期待値 モーメント 条件付き確率 条件付き期待値
確率の解釈	ベルトランの逆説 3囚人問題 モンティ・ホール問題 サンクトペテルブルクのパラドックス 合接の誤謬 ギャンブラーの誤謬
問題	壺問題 クーポンコレクター問題
法則・定理	ベイズの定理 大数の法則 中心極限定理 コルモゴロフの0-1法則 デ・フィネッティの定理 ウィーナー＝ヒンチンの定理
測度論	確率測度の拡張 カラテオドリの拡張定理 E.ホップの拡張定理 コルモゴロフの拡張定理 ヴィタリの収束定理 ルベーグの優収束定理 ラプラス原理 スコロホッドの表現定理
確率微分方程式	伊藤の補題
確率過程	独立増分過程 定常過程 マルチンゲール マルコフ過程 マルコフ性 マルコフ連鎖 マルコフ決定過程 部分観測マルコフ決定過程 マルコフ再生過程 ウィーナー過程 ブラウン運動 幾何ブラウン運動 非整数ブラウン運動 ベルヌーイ過程 ガウス過程 自己相似過程 経験過程 中華料理店過程 オルンシュタイン＝ウーレンベック過程
情報量	最大エントロピー原理 交差エントロピー 結合エントロピー カルバック・ライブラー情報量 相互情報量
応用	数理ファイナンス ブラック–ショールズ方程式 確率的ボラティリティモデル 系統学 ベイズ法
カテゴリ