CLRS 5.2 节详解:用指示随机变量(Indicator Random Variables)求期望的完整实战
CLRS 5.2 节详解:用指示随机变量(Indicator Random Variables)求期望的完整实战
本篇技术指南以开源仓库 CLRS(Solutions to Introduction to Algorithms Third Edition)中 docs/Chap05/5.2.md 为骨架,系统讲解《算法导论》第 5.2 节"指示随机变量"(Indicator Random Variables)的核心方法与全部习题解答。你将掌握:如何把"某个事件是否发生"编码为 0-1 随机变量、如何借助期望的线性性质(linearity of expectation)在完全不依赖各事件独立性的前提下求出复杂随机量的期望,并能在雇佣问题(HIRE-ASSISTANT)、掷骰子、帽子检查问题(hat-check problem)与随机排列逆序对等经典场景中独立推演。
方法总览:指示随机变量与期望的线性性质
指示随机变量是一种将"事件是否发生"转化为数值的技术。对样本空间中的一个事件 ,其指示随机变量 定义为:
它最核心的性质是:期望等于事件发生的概率,
因为 。
再加上期望的线性性质——对任意(甚至高度相关的)随机变量 都有
我们就能把"复杂总量"的期望拆解为"若干简单事件"期望之和,从而绕开对联合分布的计算。第 5.2 节的五道习题正是这一方法的五个经典应用场景;在仓库的 mkdocs.yml 导航中,本节被组织为 "5.2 Indicator random variables",同属第 I 部分 Foundations 的第 5 章"概率分析与随机化算法"。文档中的公式均通过 js/katex.js 与 css/katex.css 等 KaTeX 资源在站点渲染(参见 custom/main.html 对移动端公式渲染的修复)。
习题 5.2-1:HIRE-ASSISTANT 恰好雇佣一次 / 恰好雇佣 n 次的概率
在 中,假设候选人按随机顺序呈现,恰好雇佣一次的概率是多少?恰好雇佣 次的概率是多少?
恰好雇佣一次。 只有在"最佳候选人排在最前面"时,算法才会在第一轮就选中最优者并停止雇佣,此后不再有人能替代他。最佳候选人固定在首位共有 种排列方式,因此
恰好雇佣 次。 这意味着每一位候选人都比前一位更优秀,即候选人按排名严格递增的顺序呈现(,其中 为最佳)。满足这一条件的排列只有 1 种,因此
习题 5.2-2:恰好雇佣两次的概率
假设候选人随机呈现,恰好雇佣两次的概率是多少?
先梳理 的必然事实:
- 候选人 1(第一个被面试者)总是会被雇佣——他是唯一的初始标杆;
- 最佳候选人(排名为 )总是会被雇佣——他最终必然胜过所有前人;
- 如果最佳候选人恰好就是候选人 1,那么只雇佣这一次。
要恰好雇佣两次,需要候选人 1 的排名是某个 (),并且所有排名为 的候选人都必须在最佳候选人(排名 )之后才被面试。这样一来,候选人 1 之后先遇到的是排名不超过 的人(不会替换),而第一个超过 的、即最佳候选人一旦出现就替换掉他,此后无人再能超越,恰好完成第二次雇佣。
令 表示"候选人 1 的排名为 "这一事件,则 ()。在 发生的条件下,问题转化为:在排名为 的这 位候选人中,排名 的最佳候选人必须恰好是第一位被面试的,其概率为 。于是恰好雇佣两次的概率为
令 ,该式即 ,其中 为第 个调和数。这与 5.2-1 的 与 互相印证,形成了对雇佣次数分布两侧极值的完整刻画。雇佣问题本身的定义与 过程见同章的 docs/Chap05/5.1.md,其中 5.1-1 论证了"总能比较出最佳候选人"等价于候选人排名构成全序关系,这是本节概率计算的前提。
习题 5.2-3:用指示随机变量计算 个骰子的期望点数之和
用指示随机变量计算 个骰子的点数之和的期望。
虽然严格来说骰子点数 并不是 0-1 指示变量,但本节用同一思路说明:期望的线性性质不要求各变量独立,因此可以先把单个骰子的期望算出来,再累加。
单颗骰子点数 的期望为
对 颗骰子(各次投掷互不独立也无妨),利用线性性质:
即 颗骰子点数之和的期望恰好是 ,与"平均每颗贡献 3.5 点"的直觉完全一致。
习题 5.2-4:帽子检查问题(hat-check problem)
用指示随机变量解决下述著名的帽子检查问题: 位顾客将帽子交给餐厅的寄存员,寄存员以随机顺序把帽子还给顾客。期望有多少位顾客拿回自己的帽子?
设 为拿回自己帽子的顾客数, 为"顾客 拿回自己的帽子"这一事件的指示随机变量。由于帽子是随机归还的,每位顾客拿到自己帽子的概率都是 (无论其他顾客结果如何),于是
这个看似出人意料的结论(期望只有 1 人拿回帽子)正是指示随机变量方法的典型成果:我们从未计算任何顾客之间结果的联合分布,仅凭每个单点的概率 与线性性质就得到了精确期望。这也是该方法相对于"先求整体分布再算期望"的最大优势。
习题 5.2-5:随机排列中逆序对的期望个数
设 是 个互异数字组成的数组。若 且 ,则称 为 的一个逆序对(更多讨论见 Problem 2-4)。假设 的元素构成 的一个均匀随机排列,用指示随机变量计算逆序对的期望个数。
对每一对 ,定义指示随机变量
则逆序对总数 。在均匀随机排列中, 与 两个位置上的元素谁大谁小是对称的,因此 。于是
即长度为 的均匀随机排列期望含有 个逆序对。这一结果的工程含义是:插入排序的运行时间正比于输入中的逆序对数量(见 docs/Chap02/Problems/2-4.md 的解答 c 部分),因此上式给出了"随机输入下插入排序平均需要移动多少元素"的精确期望;而该问题解答 d 部分给出的 (基于归并排序的 计数算法)则是把这一概念用于确定性算法设计的经典例子。本习题则展示:即使逆序对之间存在复杂的相关性,线性期望依然让答案化为一连串独立同分布概率的简单求和。
延伸:指示随机变量在第五章内的其他应用
第 5.2 节建立的这套方法贯穿整个第 5 章,仓库中另有大量使用同一工具的结果可供交叉印证:
- 第 5.1 节 docs/Chap05/5.1.md:5.1-3 利用 构造无偏随机数的 ,其"每次迭代视为一次伯努利试验、成功概率 、期望试验次数 "的分析,与本节 5.2-3 的线性期望思路一脉相承。
- 第 5.4 节 docs/Chap05/5.4.md:5.4-4 用指示随机变量估计"三人生日相同"所需人数( 给出近似值 94);5.4-6 把 个球投入 个箱,用 指示"箱子 为空",得空箱期望 ,恰含一球的期望 。
- 问题 5-1(概率计数) docs/Chap05/Problems/5-1.md:证明每次 的期望增量恰为 1,从而 次操作后期望计数为 ;当 时计数服从二项分布,方差为 。
- 问题 5-2(无序数组搜索) docs/Chap05/Problems/5-2.md: 的期望抽取次数为 ( 为目标出现次数);确定性线性搜索的平均运行时间用指示随机变量推导为 。
这些练习共同说明:指示随机变量 + 线性期望是概率分析工具箱中性价比最高的组合——它把期望计算降维成"单点概率的累加",是后续第 5.3 节"随机化算法"(docs/Chap05/5.3.md,含 与 的均匀性证明)以及全书大量随机化分析的基础。
如何在本仓库中阅读与验证本节内容
本仓库是一个以 Markdown + KaTeX 组织的《算法导论(第三版)》习题解答站点(见 README.md),按章节目录组织,完整导航配置在 mkdocs.yml 中。要阅读本节及相关材料:
- 本节正文:docs/Chap05/5.2.md;
- 章节上下文:5.1 雇佣问题 docs/Chap05/5.1.md、5.3 随机化算法 docs/Chap05/5.3.md、5.4 生日悖论与指示随机变量 docs/Chap05/5.4.md;
- 章末综合问题:docs/Chap05/Problems/5-1.md 与 docs/Chap05/Problems/5-2.md;
- 前置概念:逆序对与归并排序计数 docs/Chap02/Problems/2-4.md。
仓库采用 MkDocs + Material for MkDocs 构建,数学公式由 KaTeX 渲染(mkdocs.yml 中配置了 js/katex.js、css/katex.css 及 CDN 版 KaTeX 资源)。你可以直接浏览各 Markdown 文件核对本节推导的每一步,也可以在本地安装 MkDocs 后通过 mkdocs serve 在浏览器中查看渲染效果。