要多久才能见到每一种?
设想随机测试独立地抽取 个情况之一,问题是要抽多少次,才能使每个情况至少被抽到一次。只有抽样模型正确时,答案才描述该测试的覆盖情况。
定义 8.1.1
(集齐时间与等待时间)
假设每次独立抽取都等概率地返回 种类中的一种,有放回,每次概率相同。集齐时间 是见到所有 种类所需的抽取次数。对 ,在已出现 种不同种类之后,令 为等到下一种新种类的额外抽取次数,包括成功的那一次。于是 ,且 。
定理 8.1.2
(期望集齐时间)
在上述模型下,,其中 。
证明
(几何等待时间)
见过 种之后,下一次抽到新种类的概率为 。在第 种不同种类出现时的历史条件下,之后的抽取仍是独立而均匀的,所以 服从成功率为 的几何分布,期望为 。因此
第一个等号把每次抽取恰好算进一个等待阶段。期望的线性性不要求各等待时间相互独立;每个成功率都大于零,所以各期望有限。
证明透视
为什么每个等待时间只取决于一个数量
这个分解在每次出现新种类的时刻把整个过程切开,所以每次抽取恰好属于一个 。不寻常的一点是:在第 个新种类出现之后,再抽到新种类的机会 只取决于已见过多少种,而不取决于是哪几种。这正是用到等概率的地方,也是每个 为几何分布的原因。各次抽取独立,使每个切点之后都是重新开始。于是期望的线性性把各平均值相加,无须对 之间的相依性作任何断言;每个成功率至少为 ,所以有限性是自动的。
平均值不是期限
单凭平均值不能说到那个时刻一定集齐。我们可以为等待过久的概率给出上界。
定理 8.1.3
(集齐时间的尾部界)
对每个整数 ,
因此,给定 ,每个整数 都保证 。
证明
(对缺少种类取并集界)
某一指定种类在 次抽取后仍缺少的概率为 。若 ,则至少缺少一种,对 种使用并集界即得第一个不等式;第二个不等式来自 。至于后半部分, 给出 。
不同种类缺少的事件可以重叠,所以上界可能偏松;证明并没有假设这些事件独立。这个结果是高概率的充分界,不是每次运行都成功的保证,并且仍依赖上述理想的独立均匀抽样模型。 时并集界大于一,虽然无害,却没有信息。
例题详解
例题 8.1.4
(两种类)
当 ,第一次抽取必定见到一种。之后每次抽到缺少种类的概率为 ,所以平均次数是 。两次抽取可以集齐,但并非总是如此:,因为第二次必须与第一次不同。
例题 8.1.5
(三种类)
当 ,各等待时间的平均值为 、 和 ,所以 。事件 要求三次抽取各不相同; 个等可能序列中有 个符合,所以 。
例题 8.1.6
(十种类所需的抽取次数)
对 及失败概率至多为 ,取 。此时该界给出 。这是充分的抽取次数,不一定是最小的可行整数。
例题 8.1.7
(两种类的精确尾部概率)
当 、 时,失败概率为 :三次抽取必须全部为同一种类。此例中并集界恰好等于真值,因为在非空的抽取序列之后,两个缺少事件不可能同时发生。
假设为何重要?
若某种类的概率为零,便永远无法集齐。若各类概率 不相等但都为正,而抽取仍独立,指定种类缺少的概率为 ,有效的并集界是 。但等待新种类的概率取决于已见过哪一些,而非仅取决于数量,所以均匀公式 未必成立。若抽取之间有相关性,连上述缺少概率的乘积形式也可能失效。
反例模式
概率不相等会改变平均值
一个诱人的说法是:无论各种类的概率如何,都有 。取 ,两种类的概率为 和 。若第一次抽到的是常见种类,其概率为 ,缺少的便是罕见种类,平均还要再抽 次。若第一次抽到的是罕见种类,缺少的便是常见种类,平均还要再抽 次。因此
失效的一步是:下一次抽取的成功概率现在取决于已见过哪些种类,而不只是见过多少种。等概率正是使 恢复成立的假设。
常见错误
常见错误
(把平均值当作期限)
当 ,平均值为 ,但 。事实上,对每个 都有 ,所以不存在一个必定足够的有限抽取次数。平均值说明分布的中心在哪里,并没有说明它在哪里终止。
常见错误
(把并集界当作精确概率)
当 、,并集界给出 ,但精确值是 。三个缺少事件相互重叠:三次抽取全相同的序列会使两个种类同时缺少,并集界把它计算了两次。
练习
快速检查
(当 ,求 与 。)
用前两次抽取描述事件 。
解答 · 答案
第二次与第一次不同的概率为 ,故 。事件 表示三次抽取全相同,概率为 。
快速检查
(当 ,求 。)
数一数三次抽取见到三个不同种类的序列。
解答 · 答案
三次抽取必须各不相同。 个等可能序列中有 个符合,故概率为 。
快速检查
(对 及失败概率至多为 ,上述界给出多少次抽取足够?)
使用 并向上取整。
解答 · 答案
取 。这是充分界,不一定是最小的整数。
快速检查
(为何 不需要缺少事件独立?)
这是哪一个一般的不等式?
解答 · 答案
这是并集界,对任意事件都成立。抽取的独立性是另外用来计算各个缺少概率的。