优惠券收集问题：集齐一套平均要抽多少次

一套券有 A、B、C、D、E、F 六种。每次随机得到一张，六种出现的机会相同，已经有的券还会再次出现。目标是每种至少收集一张。

抽 6 次，张数刚好够一套，但只有大约 1.54% 的机会恰好集齐。把过程重复很多局，集齐的平均抽取次数是 14.7 次；若希望有九成把握集齐，则至少要准备 23 次。

这三个数字回答了不同的问题。先亲自抽一局，看看多出来的次数花在了哪里。

从六种券开始

这里的“优惠券”只表示需要收集的不同种类，也可以换成贴纸、卡片，或公平骰子的六个点数。本文讨论的是收集时间，不涉及券的面额或使用规则。

实验默认展示同一局的前 6 次抽取。点击“抽 1 次”继续，或点击“重看本局”从头核对。每次出现“重复”，抽取次数会增加，已收集的种数却不会增加。

一种可能的抽取顺序是

第 10 次才第一次见到 F，至此集齐。10 次抽取中，有 6 次带来新种类，另外 4 次是重复。换一局，集齐时间可能更早，也可能更晚。

为什么恰好 6 次集齐这么少见？第一张一定是新的；第二张必须避开第一种，成功机会是 ；第三张必须避开前两种，机会是 。这样乘下去：

表示“括号内事件发生的概率”。这里的乘法按“前面已经抽到不同种类”的条件逐步计算。也可以直接数：六次结果共有 种等可能顺序，而六种各出现一次的顺序只有 种，感叹号表示从 6 一直乘到 1。

模型的约定

把券的总种数记为正整数 。每次只抽一张，各种券的概率都是 ；各次抽取独立，即过去抽到什么，不改变下一次的概率。券可重复出现，概率始终不变，不交换、不补发，也没有保底。

从空手开始，到首次集齐为止的总抽取次数，记为 。它包括最后抽中缺券的那一次。一次具体游戏里， 是一个整数；游戏尚未开始时，它的取值由随机抽取决定，因此称为随机变量。

这就是经典的优惠券收集问题（coupon collector’s problem）。以下正文和实验都使用上述规则。

把集齐拆成等到下一种

刚开始，任何券都是新的。已有 5 种时，只有剩下的 1 种能推进收集；下一次推进的概率从 1 降到了 。

更一般地，已经有 种时，还缺 种，所以

在这段等待中，只要抽到的仍是旧券，已收集的种数就保持为 ，下一次的成功概率也不变。于是可以把全过程拆成 个阶段：从 0 种等到 1 种，从 1 种等到 2 种，直到从 种等到 种。

成功概率为 p，平均要等 1/p 次

先用一个更小的问题计算等待：每次成功概率固定为 ，各次独立，从现在开始一直抽到第一次成功。记平均需要的次数为 。

至少要抽一次。如果这次成功，等待结束；如果失败，概率是 ，随后又回到了相同的等待状态，平均还需 次。因此

这里的“平均”也叫期望，记作 ：按各种结果发生的概率给次数加权平均。它描述大量重复实验的平均水平；不表示每次都会恰好等待这么久。例如 时，平均等待 6 次，其中包括最终成功的一次。

为什么平均等待存在，以及几何分布的完整计算

设 是第一次成功所需的次数，。等到第 次才成功，要求前 次失败、随后成功，所以

这个分布称为几何分布。采用的计数起点是 1；有些资料只数成功前的失败次数，会从 0 开始，期望也会少 1。

对每个取正整数值的等待时间，都有

原因是：若某次等待实际为 ，它会在 中恰好被计入 次。将这些非负计数取平均、再交换求和次序，就得到这个等式；非负项允许这样的交换。

而 ，故

这也确认了正文递推式中使用有限平均数是合法的。

六个阶段的等待相加

把上面的 换成 ，就得到：已有 种时，等到下一种新券的平均抽取次数是 。

对六种券，逐项写出来：

已有种数	下一张是新券的概率	等到下一种的平均次数
0		1
1		1.2
2		1.5
3		2
4		3
5		6

改动下面的总种数，再拖动“已经收集”的滑块。最后一根柱子始终最高；它表示只差最后一种时的平均等待。

单局里，总抽取次数等于各阶段等待次数之和。取平均后仍然可以逐项相加，这个性质称为期望的线性性，不要求各项独立。于是，集齐 种等概率券的平均次数为

这里定义 ，称为第 个调和数。这套分阶段推导也是 MIT 随机算法讲义中分析收集时间的方法。

代入 ：

平均而言，收齐前五种要 8.7 次，再补齐最后一种还要 6 次。“只差一种”在种数上接近终点，在时间上却可能还有很长一段。

不过，最后一种在总期望中所占的比例是 ，并非永远占一半或占据绝大部分。后面的阶段都在变慢，最后一种只是其中最慢的一段。

种类翻倍，平均次数不只翻倍

多出来的 ，意味着重复抽取的负担会随着种数增加而加重：

券的种数	集齐的平均次数	平均每种分摊的抽取次数
1	1	1
6	14.70	2.45
10	29.29	2.93
50	224.96	4.50
100	518.74	5.19

用自然对数 可以描述这种增长。它满足 ，随 增大得很慢。用曲线 下的面积比较调和数，可得到

因此，种数很大时，平均次数的主要增长部分是 。这是一条增长规律，不是把有限种数下的精确公式换掉。例如 时，，还明显低于精确期望 ；实际计算直接求 即可。

调和数的对数界从哪里来

函数 在正数范围单调下降。在每个区间 上，曲线高度不超过左端点的 ，所以

反过来，对 ，区间 上的曲线高度不小于右端点的 ，于是

这两个积分分别等于 和 ，给出正文中的上下界。两边除以 ，可得 ，所以

这里的箭头表示种数不断增大时，比值趋近于 1，不表示小种数时二者已经很接近。

平均次数和九成把握是两回事

“平均 14.7 次”不能回答“抽 15 次能不能集齐”。有的局很快结束，有的局会因为一直缺某一种而拖得很久。平均数没有指定有多少局已经结束。

另一个需要计算的量是

是允许抽取的总次数，取非负整数； 表示从零开始，在至多 次以内集齐的概率。它也叫 的累积分布函数。这里的分母始终包含所有从零开始的局，没有剔除那些特别慢的结果。

下面默认仍是 6 种券。把抽取次数从 15 调到 23，再调到 27，对比“理论平均次数”和“在此次数内集齐”两个读数。增加模拟局数，可以看随机样本中的比例怎样靠近理论曲线；拖动次数会继续使用同一批样本。

对 6 种券，有限规模下的计算结果是：

最多抽取次数	在这些次数内集齐的概率
6	约 1.54%
15	约 64.42%
23	约 91.08%
27	约 95.66%
36	约 99.15%

其中 23、27、36 分别是达到 90%、95%、99% 集齐概率所需的最少整数次数。达到 90% 的次数称为 90% 分位数。它仍然留下最多约一成没有集齐的可能；它不是保证完成的次数。

怎样算出整条概率曲线

用 3 种券 A、B、C 先看一种精确方法。抽 次都没出现 A 的概率是 ，没出现 B、C 也一样。直接相加得到 ，但“同时缺 A 和 B”的情况被算了两次，需要减掉一次。三种缺两种的组合各只有 的概率。

因此，至少缺一种的概率为 ，集齐的概率就是

比如抽 3 次时，。与直接计数吻合：总共 种顺序，集齐的只有 A、B、C 的 6 种排列。

这种“先加上、再扣掉重叠”的方法叫容斥原理。推广到 种，就得到精确公式

表示指定缺少的种数； 表示从 种中选出这 种的组合数； 是这些种类在 次里全部没出现的概率。正负号交替，修正缺少多种时的重复计数。 时另行定义 ，因为还没开始抽，任何正种数都无法集齐。MIT 的容斥原理课程讲解了这一计数工具及优惠券收集问题。

从缺券事件推导容斥公式，并用递推计算概率

设 是“前 次没有出现第 种券”的事件。未集齐就是 。指定任意 种缺券时，一次抽取避开这 种的概率为 ；各次独立，所以交集概率为 。这样的交集共有 个。

把容斥原理用于并集，再以 1 减去这个并集的概率，就得到正文公式。

实验中也可以按种数逐步推进。记 为抽取 次后，恰好拥有 种券的概率。要在下一次拥有 种，只可能从两种状态到达：已有 种又抽到旧券，或者已有 种再抽到新券。因此

初始条件为 ，其余为 0；越界的 视为 0。已集齐的状态 会一直保留，所以 。

递推和容斥计算同一个模型。上面的实验采用递推，避免种数较多时容斥公式中大数相减导致的精度损失；模拟曲线则是独立抽样结果，不参与理论曲线的计算。

抽了 n 次，平均还缺多少种

“每一种平均被抽到一次”和“每一种都已经被抽到”容易混淆。抽 次时，每一种的平均出现次数确实是 1，但重复会挤占其他种类的位置。

指定一种券，单次没抽到它的概率为 ；独立抽 次仍没见到它的概率为 。把每种券的“缺席”记作 1、“出现过”记作 0，再将它们相加，就是缺少的种数。对这个和取平均，得到

例如 6 种券抽 6 次，平均还缺约 2.01 种。种数很大且 时， 接近 ，其中 ，也就是平均仍有约 36.8% 的种类没出现。这是种数很大时的近似；六种券的精确缺席比例约为 33.5%。

这也说明为何从 次增加到约 次才接近集齐的尺度：在上述平均缺券数中，把 近似为 ，令 降到 1 左右，就得到 。这是帮助理解增长规律的估算；严格的平均完成时间已经由分阶段求和给出。

平均缺少 1 种，不代表每局都只缺 1 种，也不代表某个固定的集齐概率。 部分局可能已经集齐，部分还缺几种。实验三同时显示这两个读数，可以直接比较它们。

不用整条分布，也能给集齐概率一个保守下界

至少缺一种的概率，不超过各个缺券事件概率之和；这是概率的并集上界。于是

若右侧大于 1，这个界没有提供有效的概率改进；它不是未集齐概率的精确值。后一不等式用了 。该方法也见于 MIT 随机算法讲义的尾部概率分析。

希望未集齐的概率不超过 ，其中 ，一个足够条件是

例如 ，向上取整给出 29 次。这能保证集齐概率至少 95%，但比精确分布给出的最少 27 次更保守。这里的“保证”针对的是概率下界，不表示每局必定集齐。

固定 后，当 无限增大时，这个未集齐概率上界趋于 0。因此最终集齐的概率为 1；同时，只要 ，任何有限的抽取次数都仍有未集齐的可能，例如一直抽到 A。这两句话并不冲突。

稀有券、保底和交换会改变什么

经典公式 要求各类等概率、每次独立且概率不变。改变这些条件，需要重新检查“成功概率是多少、失败后是否回到同样的状态”。

如果 6 种券中某一种出现概率只有 1%，从零开始等到它首次出现，平均就需要 次。集齐必然不能早于它首次出现，因此总期望至少 100 次，已经远高于等概率模型的 14.7 次。这里的 100 是下界，其他五种可能在稀有券出现时还没有全到手。

当各种券的概率不一样时，“已经有 5 种”也不再足以确定下一次的成功概率：要看缺的具体是哪一种。缺普通券和缺稀有券，是不同的等待状态。

已有五种等概率券后，即使接连 20 次没抽到最后一种，下一次抽中它的机会仍是 。从此刻开始，平均仍需 6 次。过去的失败没有改变后续抽取规则；若有“第 30 次必出未拥有券”的保底，失败就会改变距离保底的次数，必须把它加入模型。

若抽到的种类会从池子里移除，保证不再重复，那么恰好抽 次即可集齐；若允许与别人交换，重复券也可能帮助填补缺口。这些规则改变了收集过程，不能再直接代入 。

对独立、等概率、允许重复的抽取，决定等待速度的是当前仍缺的种类占全部种类的比例。计算平均总次数，用各阶段的等待相加；计算有限次数内完成的把握，用 。是否存在稀有券、保底或交换，决定了这套计算能否用于实际活动。

参考资料

1. David R. Karger，MIT 6.856J Randomized Algorithms，Fall 2002，讲义 4：Coupon collecting、期望与尾部概率，第 1、4 页。
2. MIT 18.200 Principles of Discrete Applied Mathematics，Spring 2024，Lecture 3: Inclusion-Exclusion。

文中具体数值按上述模型计算。实验使用可复现的伪随机样本；随机模拟用于观察与核对，不替代公式推导。