赠券收集问题

赠券收集问题(Coupon collector's problem) 是几率论中的著名题目，其目的在解答以下问题：

假设有n种赠券，每种赠券获取几率相同，而且赠券亦无限供应。若取赠券t张，能集齐n种赠券的几率多少？

计算得出，平均需要$\Theta(n\ln(n))$次才能集齐n种赠券——这就是赠券收集问题的时间复杂度。例如n = 50时大约要取 $50\ln(50)+50\gamma+1/2 \approx 195.6011+28.8608+0.5\approx 224.9619$次才能集齐50种赠券。

## 问题内容

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

## 解答

### 计算期望值

假设T是收集所有n种赠券的次数，$t_i$是在收集了第i-1种赠券以后，到收集到第i种赠券所花的次数，那么T和$t_i$都是随机变量。在收集到i-1种赠券后能再找到“新”一种赠券的概率是$p_i = \frac{n - i + 1}{n}$，所以$t_i$是一种几何分布，并有期望值$\frac{1}{p_i}$。根据期望值的线性性质。

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

其中$H_n$是调和数，根据其近似值，可化约为：

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

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

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

$$\operatorname{P}(T \geq c \, n H_n) \le \frac1c.$$

### 变异数

基于$t_i$相互独立的特性，则有：

$$\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} \\ & \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 \le 2 n^2, \end{align}$$

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

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

### 尾部估算

我们亦可用以下方法求另一个的上限：假设${Z}_i^r$表示在首r次收集中未有见到第i种赠券，则

$$\begin{align} P\left [ {Z}_i^r \right ] = \left(1-\frac{1}{n}\right)^r \le e^{-r / n} \end{align}$$

所以，若$r = \beta n \log n$，则有$P\left [ {Z}_i^r \right ] \le e^{(-\beta n \log n ) / n} = n^{-\beta}$.

$$\begin{align} P\left [ T > \beta n \log n \right ] \le P \left [ \bigcup_i {Z}_i^{\beta n \log n} \right ] \le n \cdot P [ {Z}_1 ] \le n^{-\beta + 1} \end{align}$$

### 用生成函数的解法

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

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

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

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

$$G(z)=\sum_{m=0}^\infty p^mz^m = 1 + p z + p^2 z^2 + p^3 z^3 + \cdots = \frac{1}{1 - p z}$$

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

$$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的期望值是

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

而某一T的几率则是

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

计算E(T)可先化简$G(z)$为

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

因为

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

所以

$$\frac{\mathrm{d}}{\mathrm{d}z} G(z) = G(z) \left( <pre> \frac{n}{z} + \frac{1}{n-z} + \frac{2}{n-2z} + \frac{3}{n-3z} \cdots + \frac{n-1}{n-(n-1)z} </pre> \right)$$

故此可得出

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

其中的连加部分可化简：

$$\sum_{k=1}^{n-1} \frac{k}{n-k} = \sum_{k=1}^{n-1} \left( \frac{k}{n-k} - \frac{n}{n-k} \right) + n H_{n-1} = n H_{n-1} - (n-1)$$

所以得出：

$$\operatorname{E}(T) = n + n H_{n-1} - (n-1) = n H_{n-1} + 1 = n H_n$$

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

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

其中

$$\begin{align} \operatorname{E}(T(T-1)) =& \left. \frac{\mathrm{d}^2}{\mathrm{d}z^2} G(z) \right|_{z=1}\\ =& \left[ <pre> 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. \\ </pre> & \;\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)} - 2 n H_{n-1} + (n-1). \end{align}$$

故得出：

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

## 外部链接

- " 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.