同一个试验,不同的问题
假设独立选出的 个人各有 种可能的生日,且每种生日等可能。我们忽略闰日和季节差异;这是一个模型,并不是断言真实的生日满足这些假设。我们可以问是否有两人生日相同、出现了多少个不同的生日,或者要选多少人才能见齐所有生日。这些问题出自同一个机制,研究的却是不同的随机变量。
更一般地,设 相互独立且在 上服从均匀分布,其中 是正整数。前 次抽取构成一个有序序列; 个序列的概率都是 。令 为前 次中出现的不同类别数, 为首次见齐全部 个类别时的抽取次数。类别可以重复;计数基本序列时要考虑次序,但 本身不记录次序。
第一次碰撞
定理 31.1.1
(没有重复类别)
当 时,
当 时,这个概率为零。 时空乘积为一。至少出现一次碰撞的概率是它的补事件的概率。
证明
(按次序计数或逐步取条件)
第一次有 种选择;若第二次与第一次不同,则有 种选择,依此类推。相乘得到无重复的有序序列的个数,再除以等可能序列的总数 即得公式。也可以逐步来看:已有 个不同类别时,下一次避开它们的概率是 。若 ,由抽屉原理必有碰撞。
取补事件特别方便,因为碰撞可以以多种相互重叠的方式发生:可能有一对相同,也可能几对同时相同。直接把各对相同的概率相加,会重复计算有多对相同的结果。当 相对于 很小时,利用小 时的近似 ,无碰撞概率的对数约为 。这是近似而不是恒等式;它说明了为什么当 是 的量级时,碰撞的机会就可能不小,远在 达到 之前。
例题 31.1.2
(二十三人与三百六十五天)
取 、。把 个因子 ()相乘,得
所以至少有一对生日相同的概率约为 。近似式给出 ;由于 相对于 很小,它与精确值相当接近。在这个模型中, 个人已使碰撞概率超过一半,尽管 远小于 。
出现了多少个类别?
若类别 在前 次中出现,令 ,否则为零。于是 ;按定义 。
定理 31.1.3
(被占类别数的期望与方差)
当 时,令 ,并在 时令 。则
若 ,则对 有 ,方差为零。
证明
(示性变量及其协方差)
类别 在全部 次独立抽取中都不出现的概率为 ,所以 。期望的线性性不要求这些示性变量相互独立,对 求和即得 。
当 且 不同时,两类都不出现的概率为 。由容斥原理,,因此 。把总和的方差展开为 个方差 与 个协方差,即得公式。
协方差项不能省略:这些示性变量共享同一个固定的抽取次数。由于 推出 ,这里的协方差非正。
例题 31.1.4
(从三个类别中抽取三次)
共有 个等可能的序列。三类都出现的序列有 个,所以 。只出现一类的序列有三个,所以 ;剩下的概率为 。因此
于是 。期望公式也给出 。
反例模式
边缘概率相同并不足够
改设 ,两者是同一次从 中均匀抽取的结果,。每次抽取单独看都是均匀的,但两次并不独立。碰撞的概率为一,而不是 ;并且 几乎必然成立。前面的公式既需要均匀性,也需要独立性。
等到集齐所有类别
定义 为首次满足 的 。已收集到 个不同类别后,由抽取的独立性,下一次得到新类别的概率是 。令 表示从这时起直到首次得到新类别为止的抽取次数,包括成功的那一次。在给定此前历史的条件下, 服从成功概率为 的几何分布,所以它的条件期望与无条件期望都是 。最终几乎必然能够集齐:任一指定类别在 次之后仍未出现的概率为 ,而类别只有有限个。
定理 31.1.5
(集券问题的期望)
在独立均匀模型下,
证明
(把各个等待阶段分开)
各个等待阶段恰好把直到最后一个新类别出现为止的抽取分成若干段,所以 对每条样本路径都成立。取值于 、成功概率为 的几何随机变量的期望是 ,所以 。由线性性,
最后一步作代换 。
证明透视
为什么最后几个类别占去大部分时间
关键一步是度量从一个新类别到下一个新类别的时间,而不是跟踪已收集类别的整个集合。在第 阶段只有一个数要紧,即仍然缺少的类别所占的比例 ;独立均匀的抽取使这一阶段无论此前发生了什么都是几何等待。这是唯一用到模型假设的地方。
之后由线性性完成论证;各 在这里确实相互独立,但计算期望并不需要这一点。调和和显示了时间花在哪里:前一半类别平均每个至多需要 次抽取,而仅最后一个缺少的类别就需要 次。这就是总期望在 时大于 ,并以 的量级增长的原因。
当 时,三个阶段的平均等待分别是 、、,所以 。这并不是说一定在第 或第 次集齐: 是随机的,而且可以任意大。
例题 31.1.6
(集齐骰子的六个点数)
对一颗均匀的骰子,,各阶段的平均等待为 。它们的和为
仅最后一个阶段就占 ,最后两个阶段共占 ,超过总数的一半。退化情形 与公式一致:,而事实上 ,因为第一次抽取就已出现唯一的类别。
常见错误
常见错误
(把各对相同的概率相加)
个人、 天时共有 对,每对相同的概率为 。它们的和 是生日相同的对数的期望,而不是碰撞概率;碰撞概率约为 。这个和会把有多对相同的结果重复计算。它是碰撞概率的上界,而补事件公式给出精确值。
常见错误
(把占据示性变量当作相互独立)
当 时,若假设独立,会得到 。协方差项 不可忽略;正确的方差是 ,约为前者的一半。
练习与解答
快速检查
(从五个类别中独立均匀地抽取四次。求出现碰撞的概率,以及不同类别数的期望。)
利用无碰撞的乘积以及 的公式。
解答 · 答案
无碰撞的概率为 ,所以碰撞的概率为 。类别数的期望为 。
快速检查
(设 。求第一个类别出现之后还需要的额外抽取次数的分布及期望。)
之后每次抽取都以概率 得到另一个类别。
解答 · 答案
之后每次抽取都独立地以概率 得到另一个类别。对 ,等待恰为 次的概率是 ,期望为 。第一次抽取已经发生,不计入这段等待,所以 。
快速检查
(一位同学认为第二次抽到新类别的概率是 ,于是算出 。指出错误并给出正确值。)
想一想第一次抽取贡献了什么。
解答 · 答案
第一次抽取必然贡献一个新类别,而不是以概率 贡献。第二次以概率 贡献新类别,所以 。示性变量公式给出同样的结果:。