クーポンの種類数 n と全種類を集めるのに必要な試行回数の期待値 E (T ) のグラフ
確率論 において、クーポンコレクター問題 (クーポンコレクターもんだい、英語 : Coupon collector's problem )とは、
「全てのクーポン を集めると、何らかの特典が得られる」ような場合に、何回クーポンを引けば良いかという問題である。「クーポンコレクター」と表現しているが、ソーシャルゲーム におけるコンプリートガチャ や、(全て集めることで特典があるわけではないが)カプセルトイ ・食玩 ・トレーディングカード 等で全種類を集める場合にも適用できる問題である。日本においては食玩問題 [1] とも呼ばれる。
具体的には次のような問題である。
壺 の中に n 種類の異なるクーポンが入っている。1回の試行で壺の中から1枚クーポンを引き、引いたものと同じ種類のクーポンを壺の中に戻すものとする。n 種類(全種類)のクーポンを集めようとしたとき、 t 回以上の試行回数が必要となる確率はいくつだろうか?
別の言い方をすると次のようになる。
n 種類の異なるクーポンがあるとき、各種類のクーポンを1回以上引くまでに、何回クーポンを引けば良いか?
数学的分析によれば、必要とされる試行回数の期待値 は
Θ
(
n
log
(
n
)
)
{\displaystyle \Theta (n\log(n))}
である[注釈 1] 。例えば n = 50の場合、全50種類のクーポンを収集するには、平均で約225回の試行が必要となる[注釈 2] 。
解法
期待値の計算
T を全 n 種のクーポンを収集する時間とし、 ti を i - 1 種のクーポンを収集した後に i 種類目のクーポンを収集する時間とする。T と ti を確率変数 と考える。新しいクーポンを集める確率は pi = (n − (i − 1))/n である。従って、 ti は期待値を1/pi とする幾何分布 となる。期待値の線形性 により、以下が得られる。
E
(
T
)
=
E
(
t
1
)
+
E
(
t
2
)
+
⋯
+
E
(
t
n
)
=
1
p
1
+
1
p
2
+
⋯
+
1
p
n
=
n
n
+
n
n
−
1
+
⋯
+
n
1
=
n
⋅
(
1
1
+
1
2
+
⋯
+
1
n
)
=
n
⋅
H
n
{\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}
ここで、 Hn は n 番目の調和数 である。 調和数の漸近解析(英語版 ) を使用して、以下が得られる。
E
(
T
)
=
n
⋅
H
n
=
n
log
n
+
γ
n
+
1
2
+
O
(
1
/
n
)
{\displaystyle \operatorname {E} (T)=n\cdot H_{n}=n\log n+\gamma n+{\frac {1}{2}+O(1/n)}
ここで、
γ
≈
0.5772156649
{\displaystyle \gamma \approx 0.5772156649}
はオイラーの定数 である。
マルコフの不等式 を使用して、所望の確率の上限を与えることができる。
P
(
T
≥
c
n
H
n
)
≤
1
c
{\displaystyle \operatorname {P} (T\geq cnH_{n})\leq {\frac {1}{c}
分散の計算
確率変数 ti の独立性を用いて、分散 が以下のように計算できる。
Var
(
T
)
=
Var
(
t
1
)
+
Var
(
t
2
)
+
⋯
+
Var
(
t
n
)
=
1
−
p
1
p
1
2
+
1
−
p
2
p
2
2
+
⋯
+
1
−
p
n
p
n
2
<
(
n
2
n
2
+
n
2
(
n
−
1
)
2
+
⋯
+
n
2
1
2
)
=
n
2
⋅
(
1
1
2
+
1
2
2
+
⋯
+
1
n
2
)
<
π
2
6
n
2
{\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}
なぜならば、
π
2
6
=
1
1
2
+
1
2
2
+
⋯
+
1
n
2
+
⋯
{\displaystyle {\frac {\pi ^{2}{6}={\frac {1}{1^{2}+{\frac {1}{2^{2}+\cdots +{\frac {1}{n^{2}+\cdots }
であるからである(バーゼル問題 を参照)。
チェビシェフの不等式 を使用して、所望の確率を決めることができる。
P
(
|
T
−
n
H
n
|
≥
c
n
)
≤
π
2
6
c
2
{\displaystyle \operatorname {P} \left(|T-nH_{n}|\geq cn\right)\leq {\frac {\pi ^{2}{6c^{2}
テールの推定
異なる上限は、以下の計算から導き出すことができる。
Z
i
r
{\displaystyle {Z}_{i}^{r}
を最初の
r
{\displaystyle r}
回の試行で
i
{\displaystyle i}
番目のクーポンが引けない事象を表すとする。
P
[
Z
i
r
]
=
(
1
−
1
n
)
r
≤
e
−
r
/
n
{\displaystyle {\begin{aligned}P\left[{Z}_{i}^{r}\right]=\left(1-{\frac {1}{n}\right)^{r}\leq e^{-r/n}\end{aligned}
したがって、
r
=
β
n
log
n
{\displaystyle r=\beta n\log n}
については
P
[
Z
i
r
]
≤
e
(
−
β
n
log
n
)
/
n
=
n
−
β
{\displaystyle P\left[{Z}_{i}^{r}\right]\leq e^{(-\beta n\log n)/n}=n^{-\beta }
となる。
P
[
T
>
β
n
log
n
]
=
P
[
⋃
i
Z
i
β
n
log
n
]
≤
n
⋅
P
[
Z
1
β
n
log
n
]
≤
n
−
β
+
1
{\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}
拡張と一般化
P
(
T
<
n
log
n
+
c
n
)
→
e
−
e
−
c
(
n
→
∞
)
{\displaystyle \operatorname {P} (T<n\log n+cn)\to e^{-e^{-c}\quad (n\to \infty )}
ドナルド・J・ニューマン(英語版 ) とローレンス・シェップ(英語版 ) は、全クーポンを m 枚ずつ収集する必要がある場合として、クーポンコレクター問題を一般化 した。各クーポンを m 枚収集するのにかかる時間を Tm とする。彼らは、この場合の期待値が以下を満たしていることを示した。
E
(
T
m
)
=
n
log
n
+
(
m
−
1
)
n
log
log
n
+
O
(
n
)
(
n
→
∞
)
{\displaystyle \operatorname {E} (T_{m})=n\log n+(m-1)n\log \log n+O(n)\quad (n\to \infty )}
ここで、 m は固定されている。 m = 1のとき、上述の式が得られる。
同じ一般化のもとでエルデシュとレーニは以下を導いた。
P
(
T
m
<
n
log
n
+
(
m
−
1
)
n
log
log
n
+
c
n
)
→
e
−
e
−
c
/
(
m
−
1
)
!
(
n
→
∞
)
{\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] によると、不均一な確率分布の一般的なケースでは、以下のようになる。
E
(
T
)
=
∫
0
∞
(
1
−
∏
i
=
1
n
(
1
−
e
−
p
i
t
)
)
d
t
{\displaystyle E(T)=\int _{0}^{\infty }{\big (}1-\prod _{i=1}^{n}(1-e^{-p_{i}t}){\big )}dt}
関連項目
脚注
注釈
^ この項目全体において、log は自然対数 を指す。Θについてはランダウの記号 を参照。
^ 全50種類のクーポンを収集するための試行回数の期待値は E(50) = 50(1 + 1/2 + 1/3 + ... + 1/50) = 224.9603 である。期待値の概算は
n
log
n
+
γ
n
+
1
/
2
{\displaystyle n\log n+\gamma n+1/2}
で行え、この場合は
50
log
50
+
50
γ
+
1
/
2
≈
195.6011
+
28.8608
+
0.5
≈
224.9619
{\displaystyle 50\log 50+50\gamma +1/2\approx 195.6011+28.8608+0.5\approx 224.9619}
となる。
出典
出典
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 , MR 1265713 , 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, MR 0150807 , 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 , MR 0120672
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 , MR 1189469 , 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 , MR 1329545 , 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, MR 1344451 , https://books.google.com/books?id=QKVY4mDivBEC&pg=PA57 .
外部リンク