赠券收集问题

题目

某零食每袋随机送一张赠券，一共 n 种图案，集齐一套能换大奖。假设你已经收集了 $k$ 种，那么“再集到一种新图案”平均还要买几袋？集齐全部 $n$ 种，平均总共需要买多少袋？

答案与解析

已经集了 $k$ 种时，下一袋是“新的”概率是 $\frac{n-k}{n}$。几何分布的期望是倒数，所以集到第 $k+1$ 种平均需要：

$\frac{n}{n-k}\ \text{袋}$

把从 0 到 $n-1$ 各阶段加起来：

$E = n\left(\frac1n + \frac1{n-1} + \cdots + \frac11\right) = n\,H_n$

其中 $H_n$ 是第 $n$ 个调和数，约等于 $\ln n + \gamma$（$\gamma\approx0.577$）。

例如 $n=50$：$E \approx 50(\ln 50)\approx 50\times 3.91 \approx 196$ 袋！远比“50 袋就够”的直觉大得多。而且越接近集齐，每新一张越难——最后一种平均要等 $n=50$ 袋才出现。

背后的数学

这是赠券收集问题（Coupon Collector），是概率论里“等待时间”的标志性模型。

它解释了现实中很多“长尾”现象：集卡、抽卡游戏、哈希表填满所有桶、DNA 测序覆盖全基因组——最后一点进展都异常缓慢。结论里的 $n\ln n$ 告诉我们：完全覆盖的代价，随规模超线性增长，永远别低估“收尾”的成本。