贈券收集問題(Coupon collector's problem) 是機率論中的著名題目,其目的在解答以下問題:
- 假設有n種贈券,每種贈券獲取機率相同,而且贈券亦無限供應。若取贈券t張,能集齊n種贈券的機率多少?
計算得出,平均需要
次才能集齊n種贈券——这就是赠券收集问题的时间复杂度。例如n = 50時大約要取
次才能集齊50種贈券。
贈券收集問題的特徵是開始收集時,可以在短時間內收集多種不同的贈券,但最後數種則要花很長時間才能集齊。例如有50種贈券,在集齊49種以後要約多50次收集才能找到最後一張,所以贈券收集問題的答案t的期望值要比50要大得多。
假設T是收集所有n種贈券的次数,
是在收集了第i-1種贈券以後,到收集到第i種贈券所花的次数,那麼T和
都是隨機變量。在收集到i-1種贈券後能再找到「新」一種贈券的概率是
,所以
是一種幾何分佈,並有期望值
。根據期望值的線性性質,

其中
是調和數,根據其近似值,可化約為:

其中
是歐拉-馬歇羅尼常數.
那麼,可用馬爾可夫不等式求取機率的上限:

基於
相互獨立的特性,則有:

最末一行的等式來自黎曼ζ函數的巴塞爾問題。此式繼而可用切比雪夫不等式求取機率上限:

我們亦可用以下方法求另一個的上限:假設
表示在首r次收集中未有見到第i種贈券,則
![{\displaystyle {\begin{aligned}P\left[{Z}_{i}^{r}\right]=\left(1-{\frac {1}{n}}\right)^{r}\leq e^{-r/n}\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/67a53982df76dc7d07840b856926f1e1c66f71d8)
所以,若
,則有
.
![{\displaystyle {\begin{aligned}P\left[T>\beta n\log n\right]\leq P\left[\bigcup _{i}{Z}_{i}^{\beta n\log n}\right]\leq n\cdot P[{Z}_{1}]\leq n^{-\beta +1}\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fb8eeb1aa9b184794402e9a32f0b74d40135734a)
另一種解決贈券收集問題的方法是用生成函數。
觀察得出,贈券收集的過程必然如下:
- 收集第一張贈券,其出現的機率是

- 收集了若干張第一種贈券
- 收集到一張第二種贈券,其出現的機率是

- 收集了若干張第一種或第二種贈券
- 收集到一張第三種贈券,其出現的機率是

- 收集了若干張第一種、第二種或第三種贈券
- 收集到一張第四種贈券,其出現的機率是


- 收集到一張最後一種贈券,其出現的機率是

若某一刻已若干種贈券,再收集到一張已重覆的贈券的機率是p,那麼,再收集到m張已重覆的贈券的機率就是
。則就此部分而言,有關m的概率母函数(PGF)是

若將上述收集過程分割為多個階段,則整個收集過程所花的時間的概率母函数為各部分的乘積,亦即

那麼,根據機率生成函數的特性,總收集次數T的期望值是

而某一T的機率則是

計算E(T)可先化簡
為

因為

所以

故此可得出

其中的連加部分可化簡:

所以得出:
用機率生成函數可同時求取變異量。變異量可寫作

其中
![{\displaystyle {\begin{aligned}\operatorname {E} (T(T-1))=&\left.{\frac {\mathrm {d} ^{2}}{\mathrm {d} z^{2}}}G(z)\right|_{z=1}\\=&\left[G(z)\left({\frac {n}{z}}+{\frac {1}{n-z}}+{\frac {2}{n-2z}}+{\frac {3}{n-3z}}\cdots +{\frac {n-1}{n-(n-1)z}}\right)^{2}\right.\\&\;\left.\left.+G(z)\left(-{\frac {n}{z^{2}}}+{\frac {1^{2}}{(n-z)^{2}}}+{\frac {2^{2}}{(n-2z)^{2}}}+{\frac {3^{2}}{(n-3z)^{2}}}\cdots +{\frac {(n-1)^{2}}{(n-(n-1)z)^{2}}}\right)\right]\right|_{z=1}\\=&n^{2}H_{n}^{2}-n+\sum _{k=1}^{n-1}{\frac {k^{2}}{(n-k)^{2}}}\\=&n^{2}H_{n}^{2}-n+\sum _{k=1}^{n-1}{\frac {(n-k)^{2}}{k^{2}}}\\=&n^{2}H_{n}^{2}-n+n^{2}H_{n-1}^{(2)}-2nH_{n-1}+(n-1).\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a5676a52167ca8fdc95c974d97eef3f8aaea8c2d)
故得出:

- Paul Erdős and Alfréd Rényi, On a classical problem of probability theory, Magyar Tud. Akad. Mat. Kutato Int. Kozl, 1961.
- William Feller, An introduction to Probability Theory and its Applications, 1957.
- Michael Mitzenmacher and Eli Upfal, Probability and Computing: Randomized Algorithms and Probabilistic Analysis, Cambridge University Press, 2005
- Donald J. Newman and Lawrence Shepp, The Double Dixie Cup Problem, American Mathematical Monthly, Vol. 67, No. 1 (Jan., 1960), pp. 58–61.
- Philippe Flajolet, Danièle Gardy, Loÿs Thimonier Birthday paradox, coupon collectors, caching algorithms and self-organizing search. (页面存档备份,存于互联网档案馆), Discrete Applied Mathematics, Vol. 39, (1992), pp. 207–229