クーポンコレクター問題のソースを表示

[[File:Coupon collector problem.svg|thumb|400px|クーポンの種類数 ''n'' と全種類を集めるのに必要な試行回数の期待値 ''E''(''T'') のグラフ]]
'''クーポンコレクター問題'''（クーポンコレクターもんだい、{{lang-en|Coupon collector's problem}}）とは、[[確率論]]における「全ての[[クーポン]]を集めると何らかの特典が得られる」場合に、何回クーポンを引けばよいかという問題である。「クーポンコレクター」と表現しているが、[[ソーシャルゲーム]]で問題視された[[コンプリートガチャ]]をはじめ、[[トレーディングカード]]、[[カプセルトイ]]、[[ブラインドパッケージ]]の[[食玩]]などで全種類を集める（コンプリートする）場合にも適用できる問題である。そのため、[[日本]]においては「'''食玩問題 '''」<ref>{{cite web|url=http://aquarius10.cse.kyutech.ac.jp/~otabe/shokugan/|title=食玩問題|accessdate=2017-09-11}}</ref>とも呼ばれる。

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

別の言い方をすると次のようになる。
:''n'' 種類の異なるクーポンがあるとき、各種類のクーポンを1回以上引くまでに、何回クーポンを引けば良いか?

数学的分析によれば、必要とされる試行回数の[[期待値]]は <math>\Theta(n\log(n))</math> である<ref group="注釈">この項目全体において、log は[[自然対数]]を指す。Θについては[[ランダウの記号]]を参照。</ref>。例えば ''n''&nbsp;=&nbsp;50の場合、全50種類のクーポンを収集するには、平均で約225回の試行が必要となる<ref group="注釈">全50種類のクーポンを収集するための試行回数の期待値は E(50) = 50(1 + 1/2 + 1/3 + ... + 1/50) = 224.9603 である。期待値の概算は <math>n\log n+\gamma n+1/2</math> で行え、この場合は <math>50\log 50+50\gamma+1/2 \approx 195.6011+28.8608+0.5\approx 224.9619</math> となる。</ref>。

==解法==
=== 期待値の計算 ===
''T'' を全 ''n'' 種のクーポンを収集する時間とし、 ''t<sub>i</sub>'' を ''i - 1''種のクーポンを収集した後に ''i'' 種類目のクーポンを収集する時間とする。''T'' と ''t<sub>i</sub>'' を[[確率変数]]と考える。新しいクーポンを集める確率は ''p<sub>i</sub>'' = (''n''&nbsp;−&nbsp;(''i''&nbsp;−&nbsp;1))/''n'' である。従って、 ''t<sub>i</sub>'' は期待値を1/''p<sub>i</sub>'' とする[[幾何分布]]となる。[[期待値#性質|期待値の線形性]]により、以下が得られる。
:<math>
\begin{align}
\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{align}
</math>

ここで、 ''H<sub>n</sub>'' は ''n'' 番目の[[調和数 (発散列)|調和数]]である。 調和数の{{仮リンク|漸近解析|en|Asymptotic analysis}}を使用して、以下が得られる。
:<math>
\operatorname{E}(T)  = n \cdot H_n = n \log n + \gamma n + \frac{1}{2} + O(1/n)
</math>
ここで、 <math>\gamma \approx 0.5772156649</math> は[[オイラーの定数]]である。

[[マルコフの不等式]]を使用して、所望の確率の上限を与えることができる。
:<math>\operatorname{P}(T \geq cn H_n) \le \frac{1}{c}</math>

=== 分散の計算 ===
[[確率変数]] ''t<sub>i</sub>'' の独立性を用いて、[[分散 (確率論)|分散]]が以下のように計算できる。
:<math>
\begin{align}
\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{align}
</math>

なぜならば、 <math>\frac{\pi^2}6=\frac{1}{1^2}+\frac{1}{2^2}+\cdots+\frac{1}{n^2}+\cdots</math> であるからである（[[バーゼル問題]]を参照）。

[[チェビシェフの不等式]]を使用して、所望の確率を決めることができる。
:<math>\operatorname{P}\left(|T- n H_n| \geq cn\right) \le \frac{\pi^2}{6c^2}</math>

=== テールの推定 ===
異なる上限は、以下の計算から導き出すことができる。<math>{Z}_i^r</math> を最初の <math>r</math> 回の試行で <math>i</math> 番目のクーポンが引けない事象を表すとする。
:<math>
\begin{align}
P\left [ {Z}_i^r \right ] = \left(1-\frac{1}{n}\right)^r \le e^{-r / n}
\end{align}
</math>

したがって、<math>r = \beta n \log n</math>については<math>P\left [ {Z}_i^r \right ] \le e^{(-\beta n \log n ) / n} = n^{-\beta}</math>となる。
:<math>
\begin{align}
P\left [ T > \beta n \log n \right ] = P \left [ 	\bigcup_i {Z}_i^{\beta n \log n} \right ] \le n \cdot P [ {Z}_1^{\beta n \log n} ] \le n^{-\beta + 1}
\end{align}
</math>

== 拡張と一般化 ==
* [[ポール・エルデシュ]]と[[レーニ・アルフレード]]は、 ''T'' の分布の極限定理を証明した。この結果は、ここまでに述べた境界のさらなる拡張である。
::<math>
\operatorname{P}(T < n\log n + cn) \to e^{-e^{-c}} \quad (n\to\infty)
</math>

* {{仮リンク|ドナルド・J・ニューマン|en|Donald J. Newman}}と{{仮リンク|ローレンス・シェップ|en|Lawrence Shepp}}は、全クーポンを ''m'' 枚ずつ収集する必要がある場合として、クーポンコレクター問題を[[一般化]]した。各クーポンを ''m'' 枚収集するのにかかる時間を ''T<sub>m</sub>'' とする。彼らは、この場合の期待値が以下を満たしていることを示した。
::<math>
\operatorname{E}(T_m) =  n \log n + (m-1) n \log\log n + O(n) \quad (n\to\infty)
</math>
:ここで、 ''m'' は固定されている。 ''m'' = 1のとき、上述の式が得られる。

* 同じ一般化のもとでエルデシュとレーニは以下を導いた。
::<math>
\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)</math>

* {{仮リンク|フィリップ・フラジョレ|en|Philippe Flajolet}}<ref name="Flajolet">{{citation |first=Philippe |last=Flajolet |first2=Danièle |last2=Gardy |first3=Loÿs |last3=Thimonier |url=http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.217.5965&rep=rep1&type=pdf |title=Birthday paradox, coupon collectors, caching algorithms and self-organizing search |journal=Discrete Applied Mathematics |volume=39 |issue=3 |year=1992 |pages=207–229 |doi=10.1016/0166-218x(92)90177-c}}</ref>によると、不均一な確率分布の一般的なケースでは、以下のようになる。
::<math>
E(T)=\int_0^\infty \big(1-\prod_{i=1}^n(1-e^{-p_it})\big)dt
</math>

== 関連項目 ==
* [[コンプリートガチャ]]
* [[食玩]] / [[カプセルトイ]] / [[ブラインドパッケージ]]
* [[誕生日のパラドックス]]（誕生日問題）
* [[:en:Watterson estimator|Watterson estimator]]

== 脚注 ==
===注釈===
{{Notelist}}
===出典===
{{Reflist}}

== 出典 ==
*{{citation
 | last1 = Blom | first1 = Gunnar
 | last2 = Holst | first2 = Lars
 | last3 = Sandell | first3 = Dennis
 | contribution = 7.5 Coupon collecting I, 7.6 Coupon collecting II, and 15.4 Coupon collecting III
 | isbn = 0-387-94161-4
 | location = New York
 | mr = 1265713
 | pages = 85–87, 191
 | publisher = Springer-Verlag
 | title = Problems and Snapshots from the World of Probability
 | url = https://books.google.com/books?id=KCsSWFMq2u0C&pg=PA85
 | year = 1994}}.
*{{citation
 | last = Dawkins | first = Brian
 | issue = 1
 | journal = The American Statistician
 | jstor = 2685247
 | pages = 76–82
 | title = Siobhan's problem: the coupon collector revisited
 | volume = 45
 | year = 1991
 | doi=10.2307/2685247}}.
*{{citation
 | last1 = Erdős | first1 = Paul | author1-link = Paul Erdős
 | last2 = Rényi | first2 = Alfréd | author2-link = Alfréd Rényi
 | journal = Magyar Tudományos Akadémia Matematikai Kutató Intézetének Közleményei
 | mr = 0150807
 | pages = 215–220
 | title = On a classical problem of probability theory
 | url = http://www.renyi.hu/~p_erdos/1961-09.pdf
 | volume = 6
 | year = 1961}}.
*{{citation
 | last1 = Newman | first1 = Donald J. | author1-link = Donald J. Newman
 | last2 = Shepp | first2 = Lawrence | author2-link = Lawrence Shepp
 | doi = 10.2307/2308930
 | journal = [[American Mathematical Monthly]]
 | mr = 0120672
 | pages = 58–61
 | title = The double dixie cup problem
 | volume = 67
 | year = 1960}}
*{{citation
 | last1 = Flajolet | first1 = Philippe | author1-link = Philippe Flajolet
 | last2 = Gardy | first2 = Danièle
 | last3 = Thimonier | first3 = Loÿs
 | doi = 10.1016/0166-218X(92)90177-C
 | issue = 3
 | journal = Discrete Applied Mathematics
 | mr = 1189469
 | pages = 207–229
 | title = Birthday paradox, coupon collectors, caching algorithms and self-organizing search
 | url = http://algo.inria.fr/flajolet/Publications/alloc2.ps.gz
 | volume = 39
 | year = 1992}}.
*{{citation
 | last = Isaac | first = Richard
 | contribution = 8.4 The coupon collector's problem solved
 | isbn = 0-387-94415-X
 | location = New York
 | mr = 1329545
 | pages = 80–82
 | publisher = Springer-Verlag
 | series = [[Undergraduate Texts in Mathematics]]
 | title = The Pleasures of Probability
 | url = https://books.google.com/books?id=a_2vsIx4FQMC&pg=PA80
 | year = 1995}}.
*{{citation
 | last1 = Motwani | first1 = Rajeev | author1-link = Rajeev Motwani
 | last2 = Raghavan | first2 = Prabhakar
 | contribution = 3.6. The Coupon Collector's Problem
 | location = Cambridge
 | mr = 1344451
 | pages = 57–63
 | publisher = Cambridge University Press
 | title = Randomized algorithms
 | url = https://books.google.com/books?id=QKVY4mDivBEC&pg=PA57
 | year = 1995}}.

== 外部リンク ==
* "[http://demonstrations.wolfram.com/CouponCollectorProblem/ Coupon Collector Problem]" by [[Ed Pegg, Jr.]], the [[Wolfram Demonstrations Project]]. Mathematica package.
* ''[http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/coupon.html How Many Singles, Doubles, Triples, Etc., Should The Coupon Collector Expect?]'', a short note by [[Doron Zeilberger]].

{{確率論}}
{{デフォルトソート:くうほんこれくたあもんたい}}
[[Category:証明を含む記事]]
[[Category:確率問題]]
[[Category:ギャンブルの数学]]
[[Category:数学に関する記事]]