# 赠券收集问题

## 解答

### 计算期望值

{\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 \operatorname {E} (T)=n\cdot H_{n}=n\ln n+\gamma n+{\frac {1}{2))+o(1),\ \ {\text{as))\ n\to \infty ,}$

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

### 方差

{\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 {\begin{aligned}P\left[{Z}_{i}^{r}\right]=\left(1-{\frac {1}{n))\right)^{r}\leq e^{-r/n}\end{aligned))}

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

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

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

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

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