本课程中的若干分析,实际上都是关于平均值的陈述:随机化排序的期望比较次数、哈希表中的期望碰撞数、偶尔失败的随机化子程序的期望重复次数。每一个都是期望的计算,而同一个工具使它们都变得简短:把所求的量写成若干指示变量之和,再把各自的期望相加。本节建立只需计数的有限概率语言,证明两个基本事实(期望的线性性与 Markov 不等式),并加以应用。本节以本章的计数各节为基础,因为均匀概率就是两个计数之比。
定义
定义 1.5.1
(有限概率空间与事件)
有限概率空间由有限集 (样本空间)和函数 组成,满足 。事件是子集 ,其概率为 。若对每个 有 ,则称空间为均匀的,此时 。由定义得 ,并且对任意事件 ,并集界成立:
因为并集中每个结果在右边至少被计算一次。若 ,则称事件 独立。当 时,条件概率为 。
定义 1.5.2
(随机变量、期望与指示变量)
随机变量是函数 。它的期望(均值)为
其中第二个和对 所取的有限多个值 求和;把取值相同的结果归在一起,便知两种写法相等。事件 的指示变量是随机变量 :当 时 ,否则为 。于是 。若对所有取值 都有 ,则称随机变量 独立。
线性性与 Markov 不等式
定理 1.5.3
(期望的线性性)
设 是同一个有限概率空间上的随机变量, 为实常数,则
不要求各 相互独立。
证明
(交换两个有限和)
按对结果求和的定义, ,其中交换了两个有限和的次序。
定理 1.5.4
(Markov 不等式)
若 在每个结果上都有 ,且 ,则 。
证明
(在阈值处拆分求和)
把 的和拆成 的结果与其余结果。每一项都非负,所以 。两边除以 即得。
定理 1.5.5
(独立变量的乘积)
若 与 独立,则 。
证明
(独立性使求和分解)
按取值对分组,。
指示变量法。 要求某个“坏对象”个数 的期望 ,可写 ,其中 是第 个候选对象为坏对象的事件。由线性性,。只需要各个概率 ,这些事件之间可能很复杂的相依关系完全不必考虑。
命题 1.5.6
(期望等待时间)
设某实验每次试验独立地以概率 成功, 为第一次成功的试验序号。则对 有 ,且 。
证明
(对尾概率求和)
事件 表示前 次试验全部失败,其概率为 。对取值于 的变量 ,有 ,因为 且各项非负(上述定义对非负变量可原样推广到可数样本空间)。因此
例题
例题 1.5.7
(随机排列的不动点)
设 是 的均匀随机排列, 为其不动点个数。令 。满足 的排列有 个,所以 。于是 ,对每个 都有 。各事件 并不独立,但线性性并不需要独立。
以 验算,列出全部六个排列:恒等排列有 个不动点;三个对换各有 个;两个 -循环各有 个。六个排列共有 个不动点,平均为 。
例题 1.5.8
(哈希中的碰撞)
把 个键独立且均匀地哈希到 个槽。设 为落在同一槽的键对 的个数, 为键 与键 碰撞的事件。已知键 的槽,键 必须选同一个槽:。共有 对,所以 。当 、 时为 。因为 且取整数值,取 的 Markov 不等式给出 。
例题 1.5.9
(随机排列的逆序数)
排列 的逆序是满足 且 的一对位置。固定 ,排列 与把位置 上的值交换后得到的排列同样可能出现,而且恰有一个在 处有逆序;所以 。共有 对,期望逆序数为 。当 时,六个排列 的逆序数为 ,总和 ,平均 。这也是插入排序处理随机输入次序时元素移位的期望次数。
例题 1.5.10
(期望重复次数)
某随机化子程序每次独立运行时,以概率 返回正确答案,并且可以识别答案是否正确。重复运行直到成功,需要 次,。若 ,则 ,且 。
常见错误与细节
反例模式
乘积公式不能去掉独立性
一个诱人的说法是:像线性性一样,对所有变量都有 。设 取 和 的概率各为 ,且 。则 ,所以 ,但 。这两个变量并不独立:。乘积公式需要上述定理中的独立性假设;线性性则不需要。
常见错误
(把均值当作变量的典型取值)
期望是加权平均,不是变量通常取的值。骰子的均值是 ,却永远掷不出;第一个例题中不动点个数的均值为 ,但当 时以正概率等于 。
常见错误
(把期望搬进非线性函数内)
一般有 。设 在 上均匀,则 而 ; 而 。
常见错误
(过分解读粗略的界)
并集界对任意事件都成立,但右边可能超过 ,此时它什么也没说明。Markov 不等式要求 ,所给的尾界也较粗;对于以概率 取 、否则取 的变量(均值为 ),它恰好取等号,说明其常数一般不能改进。
最后,用指示变量法时,必须按所述的随机实验计算 。在哈希例题中,各键哈希值的独立性使 ;对较弱的哈希族,则需另外证明 ,同一论证便给出上界。
练习
快速检查
(掷一枚公平硬币 次。求正面次数的期望,以及满足“第 次与第 次都是正面”的位置 个数的期望。)
解答 · 答案
设 为第 次掷出正面的指示变量,。正面次数的期望为 。对相邻位置,因为各次独立,“第 次与第 次都是正面”的概率为 ,这样的位置有 个,由线性性期望为 。
快速检查
(设 是 的均匀随机排列,下降是满足 的位置 。求期望下降数,并对 求值。)
解答 · 答案
对固定的 ,值对 取 与取 同样可能,所以 。共 个位置,期望为 ; 时等于 。
快速检查
(一个非负随机变量的均值为 。用 Markov 不等式界定 ,并给出一个随机变量说明这个界不能改进。)
解答 · 答案
Markov 给出 。令 以概率 取 ,否则取 。则 ,,等号成立。
快速检查
(某检验在每次独立运行中,接受一个合数的概率至多为 。证明 次运行全都接受该合数的概率至多为 ,并求使其小于 的最小 。)
解答 · 答案
各次运行独立,所以 次运行都接受该合数的概率是各次接受概率的乘积,每个至多为 ,故至多为 。要求 ,即 。因为 ,,所以最小的 为 。
练习 1.5.11
(两个球独立且均匀地投入 个箱子。分别用 (a) 指示变量和 (b) 按两球是否落在同一箱作条件,求空箱个数的期望。)
核心
解答(3)
- 1
用指示变量计算
令 表示箱子 为空。这要求两球都不落入该箱,所以 ,由线性性,空箱个数的期望为 。
- 2
按两球是否落在同一箱作条件
以概率 ,第二个球与第一个球落在同一箱,此时有 个空箱;否则(概率 )有两个箱子被占用, 个为空。期望为 。
- 3
比较两种方法
两种方法都给出空箱个数的期望为 。