如果你收集过零食袋里附赠的贴纸，大概会记得这样的经历：一开始几乎每拆一袋都能拿到新贴纸，感觉很快就能集齐。可是等到贴纸册快要贴满时，拿到的却总是已有的贴纸，最后那一两张怎么也出不来。这并不是运气不好，而是概率本来就是这样运作的。用数学来解释这一现象的，正是“赠券收集问题（Coupon Collector’s Problem）”。
简单来说，赠券收集问题是一个概率问题，它问的是：“当多种类型中随机出现一种时，平均要抽多少次，才能把所有类型至少各集齐一次？”关键在于，答案比想象的大得多，而且其中大部分次数都花在等待最后几种上。
本文将依次介绍赠券收集问题是什么、计算平均次数的原理、用数字呈现的具体例子，以及这一问题在生活与技术中的应用和需要注意的地方。
最后一张代价最高：赠券收集问题
什么是赠券收集问题
这个问题的名称来自一种促销活动：每个麦片盒里放一张赠券，集齐所有种类就能换取奖品。从数学上看，它设定了以下条件。
(1) 种类数量是固定的
需要收集的赠券一共有 n 种，收集者事先知道这个数字。
(2) 每次随机出现一张
每买一盒，n 种中的某一种会以相同的概率出现，之前出现过什么不会影响下一次的结果。
(3) 会出现重复
已经拥有的赠券可能再次出现。多次拿到同一张赠券，正是让收集过程变长的原因。
换成骰子来说，这就相当于问：“平均要掷多少次骰子，六个面才会都至少出现一次？”
平均次数如何计算
如果把收集过程分成若干个“直到获得一种新类型为止”的阶段，计算就会变得简单。
(1) 一开始什么都是新的
手里什么都没有时，第一次抽到的必然是新类型，所以一次就够了。
(2) 收集得越多，出现新类型的概率越低
如果已经拥有 k 种，那么出现新类型的概率是 (n – k) / n。把成功概率为 p 的事情反复进行直到成功，平均需要 1 / p 次，因此这一阶段平均需要 n / (n – k) 次。
(3) 把所有阶段加起来
把各阶段的平均值相加，总平均次数就是 n × (1 + 1/2 + 1/3 + … + 1/n)。括号内的和称为调和数，当 n 变大时，总次数大约按 n × (n 的自然对数) + 0.577 × n 增长。法国数学家皮埃尔-西蒙·拉普拉斯（Pierre-Simon Laplace）也在 1812 年的概率论著作中讨论过这个问题。
用骰子实际算一算就很好理解。平均来说，第一个面需要 1 次，第二个新面需要 6/5 次，第三个需要 6/4 次，第四个需要 6/3 次，第五个需要 6/2 次，最后第六个需要 6/1 次。全部相加约为 14.7 次，其中仅等待最后一个面就平均要花 6 次。
从这个式子可以看出，在最后一个阶段，也就是只剩一种时，光是这一种就平均要等 n 次。已经收集的种类越多，遇到新类型就越难，正是这种结构拉长了收集的时间。
用数字看收集的现实
把计算结果换成具体数字，就能清楚看出它与直觉有多大差距。
- 骰子（Die）：如前所述，要看到全部六个面平均约需掷 14.7 次。看似六次就够，实际却超过两倍。
- 10 种赠券（Ten Coupons）：平均约需 29.3 次。
- 50 种赠券（Fifty Coupons）：平均约需 225 次。其中集齐前 25 种只需约 34 次，而集齐其余 25 种则需约 191 次。
- 100 种赠券（One Hundred Coupons）：平均约需 519 次，超过种类数的五倍。
这里的数字只是平均值，现实中花费更长时间的人也很多。此外，如果故意把某些种类放得很少，作为“稀有卡”，那么期望次数会比各种类概率相同时更大。
赠券收集问题的应用与注意事项
这个问题的应用远不止贴纸册，它出现在许多领域。
(1) 促销与消费设计
随机出现的收集型商品，其结构会让人为了得到最后几种而反复购买同一商品。站在消费者的角度，只要事先算一算期望花费，就能减少冲动消费。
(2) 计算机科学与算法
在估算随机选取的元素要多久才能把所有情况各经历一次时，就会用到这一计算，它也是随机算法教材中的经典例题。
(3) 交换可能就是答案
多人一起收集并互相交换重复的物品，每个人需要购买的数量会比独自收集时大幅减少。因为自己多出来的重复品，对别人来说可能正是缺少的那一张。
(4) 估算剩余次数的标准
如果已经集齐了多种，只需对剩下的种类用同样的方法计算即可。例如，在 50 种中已经集齐 49 种，就意味着平均还要再抽 50 次才能得到最后一张。
不过，实际商品中各种类的出现比例往往不同，或者并不公开，因此这一计算只能作为出发点。
赠券收集问题告诉我们，“收集得越多，越难得到新的”这一简单事实会造成多么大的差别。最后一张迟迟不出现，并不是运气不好，而是概率早已铺好的路。
开始收集之前，先算一算大概需要多少次，再找几个可以分享重复品的朋友，这就是明智收集的第一步。
