赠券收集问题

赠券收集问题的特征是开始收集时，可以在短时间内收集多种不同的赠券，但最后数种则要花很长时间才能集齐。例如有50种赠券，在集齐49种以后要约多50次收集才能找到最后一张，所以赠券收集问题的答案t的期望值要比50要大得多。

计算期望值

假设T是收集所有n种赠券的次数，${\displaystyle t_{i}}$ 是在收集了第i-1种赠券以后，到收集到第i种赠券所花的次数，那么T和${\displaystyle t_{i}}$ 都是随机变量。在收集到i-1种赠券后能再找到“新”一种赠券的概率是${\displaystyle p_{i}={\frac {n-i+1}{n}}}$ ，所以${\displaystyle t_{i}}$ 是一种几何分布，并有期望值${\displaystyle {\frac {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}}}$ 

其中${\displaystyle H_{n}}$ 是调和数，根据其近似值，可化约为：

${\displaystyle \operatorname {E} (T)=n\cdot H_{n}=n\ln n+\gamma n+{\frac {1}{2}}+o(1),\ \ {\text{as}}\ n\to \infty ,}$ 

其中${\displaystyle \gamma \approx 0.5772156649}$ 是欧拉-马歇罗尼常数.

那么，可用马尔可夫不等式求取概率的上限：

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

方差

基于${\displaystyle 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}}}\\&\leq {\frac {n^{2}}{n^{2}}}+{\frac {n^{2}}{(n-1)^{2}}}+\cdots +{\frac {n^{2}}{1^{2}}}\\&\leq n^{2}\cdot \left({\frac {1}{1^{2}}}+{\frac {1}{2^{2}}}+\cdots \right)={\frac {\pi ^{2}}{6}}n^{2}\leq 2n^{2},\end{aligned}}}$ 

最末一行的等式来自黎曼ζ函数的巴塞尔问题。此式继而可用切比雪夫不等式求取概率上限：

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

尾部估算

我们亦可用以下方法求另一个的上限：假设${\displaystyle {Z}_{i}^{r}}$ 表示在首r次收集中未有见到第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]\leq P\left[\bigcup _{i}{Z}_{i}^{\beta n\log n}\right]\leq n\cdot P[{Z}_{1}]\leq n^{-\beta +1}\end{aligned}}}$ 

用生成函数的解法

另一种解决赠券收集问题的方法是用生成函数。

观察得出，赠券收集的过程必然如下：

• 收集第一张赠券，其出现的概率是${\displaystyle n/n=1}$ 
• 收集了若干张第一种赠券
• 收集到一张第二种赠券，其出现的概率是${\displaystyle (n-1)/n}$ 
• 收集了若干张第一种或第二种赠券
• 收集到一张第三种赠券，其出现的概率是${\displaystyle (n-2)/n}$ 
• 收集了若干张第一种、第二种或第三种赠券
• 收集到一张第四种赠券，其出现的概率是${\displaystyle (n-3)/n}$ 
• ${\displaystyle \ldots }$ 
• 收集到一张最后一种赠券，其出现的概率是${\displaystyle 1/n}$ 

若某一刻已若干种赠券，再收集到一张已重复的赠券的概率是p，那么，再收集到m张已重复的赠券的概率就是${\displaystyle p^{m}}$ 。则就此部分而言，有关m的概率母函数（PGF）是

${\displaystyle G(z)=\sum _{m=0}^{\infty }p^{m}z^{m}=1+pz+p^{2}z^{2}+p^{3}z^{3}+\cdots ={\frac {1}{1-pz}}}$ 

若将上述收集过程分割为多个阶段，则整个收集过程所花的时间的概率母函数为各部分的乘积，亦即

${\displaystyle G(z)={\frac {n}{n}}z\cdot {\frac {1}{1-{\frac {1}{n}}z}}\cdot {\frac {n-1}{n}}z\cdot {\frac {1}{1-{\frac {2}{n}}z}}\cdot {\frac {n-2}{n}}z\cdot {\frac {1}{1-{\frac {3}{n}}z}}\cdot {\frac {n-3}{n}}z\cdots {\frac {1}{1-{\frac {n-1}{n}}z}}\cdot {\frac {n-(n-1)}{n}}z.}$ 

那么，根据概率生成函数的特性，总收集次数T的期望值是

${\displaystyle \operatorname {E} (T)=\left.{\frac {\mathrm {d} }{\mathrm {d} z}}G(z)\right|_{z=1}}$ 

而某一T的概率则是

${\displaystyle \Pr(T=k)=\left.{\frac {1}{k!}}{\frac {\mathrm {d} ^{k}G(z)}{\mathrm {d} z^{k}}}\right|_{z=0}}$ 

计算E(T)可先化简${\displaystyle G(z)}$ 为

${\displaystyle G(z)=z^{n}{\frac {n-1}{n-z}}{\frac {n-2}{n-2z}}{\frac {n-3}{n-3z}}\cdots {\frac {n-(n-1)}{n-(n-1)z}}}$ 

因为

${\displaystyle {\frac {\mathrm {d} }{\mathrm {d} z}}{\frac {n-k}{n-kz}}={\frac {k(n-k)}{(n-kz)^{2}}}}$ 

所以

${\displaystyle {\frac {\mathrm {d} }{\mathrm {d} z}}G(z)=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)}$ 

故此可得出

${\displaystyle {\begin{aligned}\operatorname {E} (T)&=\left.{\frac {\mathrm {d} }{\mathrm {d} z}}G(z)\right|_{z=1}\\&=G(1)\left(n+{\frac {1}{n-1}}+{\frac {2}{n-2}}+{\frac {3}{n-3}}\cdots +{\frac {n-1}{n-(n-1)}}\right)\\&=n+\sum _{k=1}^{n-1}{\frac {k}{n-k}}\end{aligned}}}$ 

其中的连加部分可化简：

${\displaystyle \sum _{k=1}^{n-1}{\frac {k}{n-k}}=\sum _{k=1}^{n-1}\left({\frac {k}{n-k}}-{\frac {n}{n-k}}\right)+nH_{n-1}=nH_{n-1}-(n-1)}$ 

所以得出： ${\displaystyle \operatorname {E} (T)=n+nH_{n-1}-(n-1)=nH_{n-1}+1=nH_{n}}$ 

用概率生成函数可同时求取变异量。变异量可写作

${\displaystyle \operatorname {Var} (T)=\operatorname {E} (T(T-1))+\operatorname {E} (T)-\operatorname {E} (T)^{2}}$ 

其中

${\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}}}$ 

故得出：

${\displaystyle {\begin{aligned}\operatorname {Var} (T)&=\;n^{2}H_{n}^{2}-1+n^{2}H_{n-1}^{(2)}-2nH_{n-1}+nH_{n-1}+1-n^{2}H_{n}^{2}\\&=\;n^{2}H_{n-1}^{(2)}-nH_{n-1}<{\frac {\pi ^{2}}{6}}n^{2}\end{aligned}}}$ 

• 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

• "Coupon Collector Problem （页面存档备份，存于互联网档案馆）" by Ed Pegg, Jr., the Wolfram Demonstrations Project. Mathematica package.
• Coupon Collector Problem （页面存档备份，存于互联网档案馆）, Java applet.
• How Many Singles, Doubles, Triples, Etc., Should The Coupon Collector Expect? （页面存档备份，存于互联网档案馆）, a short note by Doron Zeilberger.
• （英文） getir indirim kodu（页面存档备份，存于互联网档案馆）