CLRS 5.2 节详解:用指示随机变量(Indicator Random Variables)求期望的完整实战

原创2026-10-12 13:11:331,417 阅读
文章标签:文档教程

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)与随机排列逆序对等经典场景中独立推演。

方法总览:指示随机变量与期望的线性性质

指示随机变量是一种将"事件是否发生"转化为数值的技术。对样本空间中的一个事件 AA,其指示随机变量 XAX_A 定义为:

XA={1若 A 发生,0若 A 不发生,X_A = \begin{cases} 1 & \text{若 } A \text{ 发生,}\\ 0 & \text{若 } A \text{ 不发生,}\end{cases}

它最核心的性质是:期望等于事件发生的概率,

E[XA]=Pr⁡{A},\text E[X_A] = \Pr\{A\},

因为 1⋅Pr⁡{A}+0⋅Pr⁡{¬A}=Pr⁡{A}1 \cdot \Pr\{A\} + 0 \cdot \Pr\{\neg A\} = \Pr\{A\}。

再加上期望的线性性质——对任意(甚至高度相关的)随机变量 X1,X2,…,XnX_1, X_2, \dots, X_n 都有

E[∑i=1nXi]=∑i=1nE[Xi],\text E\left[\sum_{i=1}^{n} X_i\right] = \sum_{i=1}^{n} \text E[X_i],

我们就能把"复杂总量"的期望拆解为"若干简单事件"期望之和,从而绕开对联合分布的计算。第 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 次的概率

在 HIRE-ASSISTANT\text{HIRE-ASSISTANT} 中,假设候选人按随机顺序呈现,恰好雇佣一次的概率是多少?恰好雇佣 nn 次的概率是多少?

恰好雇佣一次。 只有在"最佳候选人排在最前面"时,算法才会在第一轮就选中最优者并停止雇佣,此后不再有人能替代他。最佳候选人固定在首位共有 (n−1)!(n - 1)! 种排列方式,因此

Pr⁡{恰好雇佣 1 次}=(n−1)!n!=1n.\Pr\{\text{恰好雇佣 1 次}\} = \frac{(n - 1)!}{n!} = \frac{1}{n}.

恰好雇佣 nn 次。 这意味着每一位候选人都比前一位更优秀,即候选人按排名严格递增的顺序呈现(1,2,…,n1, 2, \dots, n,其中 nn 为最佳)。满足这一条件的排列只有 1 种,因此

Pr⁡{恰好雇佣 n 次}=1n!.\Pr\{\text{恰好雇佣 } n \text{ 次}\} = \frac{1}{n!}.

习题 5.2-2:恰好雇佣两次的概率

假设候选人随机呈现,恰好雇佣两次的概率是多少?

先梳理 HIRE-ASSISTANT\text{HIRE-ASSISTANT} 的必然事实:

  • 候选人 1(第一个被面试者)总是会被雇佣——他是唯一的初始标杆;
  • 最佳候选人(排名为 nn)总是会被雇佣——他最终必然胜过所有前人;
  • 如果最佳候选人恰好就是候选人 1,那么只雇佣这一次。

要恰好雇佣两次,需要候选人 1 的排名是某个 ii(1≤i≤n−11 \le i \le n - 1),并且所有排名为 i+1,i+2,…,n−1i + 1, i + 2, \dots, n - 1 的候选人都必须在最佳候选人(排名 nn)之后才被面试。这样一来,候选人 1 之后先遇到的是排名不超过 ii 的人(不会替换),而第一个超过 ii 的、即最佳候选人一旦出现就替换掉他,此后无人再能超越,恰好完成第二次雇佣。

令 EiE_i 表示"候选人 1 的排名为 ii"这一事件,则 P(Ei)=1/nP(E_i) = 1 / n(1≤i≤n1 \le i \le n)。在 EiE_i 发生的条件下,问题转化为:在排名为 i+1,i+2,…,ni + 1, i + 2, \dots, n 的这 n−in - i 位候选人中,排名 nn 的最佳候选人必须恰好是第一位被面试的,其概率为 1/(n−i)1 / (n - i)。于是恰好雇佣两次的概率为

∑i=1n−1P(Ei)⋅1n−i=∑i=1n−11n⋅1n−i.\sum_{i = 1}^{n - 1} P(E_i) \cdot \frac{1}{n - i} = \sum_{i = 1}^{n - 1} \frac{1}{n} \cdot \frac{1}{n - i}.

令 j=n−ij = n - i,该式即 1n∑j=1n−11j=Hn−1n\frac{1}{n}\sum_{j=1}^{n-1}\frac{1}{j} = \frac{H_{n-1}}{n},其中 Hn−1H_{n-1} 为第 n−1n-1 个调和数。这与 5.2-1 的 1/n1/n 与 1/n!1/n! 互相印证,形成了对雇佣次数分布两侧极值的完整刻画。雇佣问题本身的定义与 HIRE-ASSISTANT\text{HIRE-ASSISTANT} 过程见同章的 docs/Chap05/5.1.md,其中 5.1-1 论证了"总能比较出最佳候选人"等价于候选人排名构成全序关系,这是本节概率计算的前提。

习题 5.2-3:用指示随机变量计算 nn 个骰子的期望点数之和

用指示随机变量计算 nn 个骰子的点数之和的期望。

虽然严格来说骰子点数 Xk∈{1,2,…,6}X_k \in \{1, 2, \dots, 6\} 并不是 0-1 指示变量,但本节用同一思路说明:期望的线性性质不要求各变量独立,因此可以先把单个骰子的期望算出来,再累加。

单颗骰子点数 XkX_k 的期望为

E[Xk]=∑i=16iPr⁡{Xk=i}=1+2+3+4+5+66=216=3.5.\begin{aligned} \text E[X_k] & = \sum_{i = 1}^6 i \Pr\{X_k = i\} \\\\ & = \frac{1 + 2 + 3 + 4 + 5 + 6}{6} \\\\ & = \frac{21}{6} \\\\ & = 3.5. \end{aligned}

对 nn 颗骰子(各次投掷互不独立也无妨),利用线性性质:

E[X]=E[∑i=1nXi]=∑i=1nE[Xi]=∑i=1n3.5=3.5⋅n.\begin{aligned} \text E[X] & = \text E\Bigg[\sum_{i = 1}^n X_i \Bigg] \\\\ & = \sum_{i = 1}^n \text E[X_i] \\\\ & = \sum_{i = 1}^n 3.5 \\\\ & = 3.5 \cdot n. \end{aligned}

即 nn 颗骰子点数之和的期望恰好是 3.5n3.5n,与"平均每颗贡献 3.5 点"的直觉完全一致。

习题 5.2-4:帽子检查问题(hat-check problem)

用指示随机变量解决下述著名的帽子检查问题:nn 位顾客将帽子交给餐厅的寄存员,寄存员以随机顺序把帽子还给顾客。期望有多少位顾客拿回自己的帽子?

设 XX 为拿回自己帽子的顾客数,XiX_i 为"顾客 ii 拿回自己的帽子"这一事件的指示随机变量。由于帽子是随机归还的,每位顾客拿到自己帽子的概率都是 1/n1 / n(无论其他顾客结果如何),于是

E[X]=E[∑i=1nXi]=∑i=1nE[Xi]=∑i=1n1n=1.E[X] = E\Bigg[\sum_{i = 1}^n X_i\Bigg] = \sum_{i = 1}^n E[X_i] = \sum_{i = 1}^n \frac{1}{n} = 1.

这个看似出人意料的结论(期望只有 1 人拿回帽子)正是指示随机变量方法的典型成果:我们从未计算任何顾客之间结果的联合分布,仅凭每个单点的概率 1/n1/n 与线性性质就得到了精确期望。这也是该方法相对于"先求整体分布再算期望"的最大优势。

习题 5.2-5:随机排列中逆序对的期望个数

设 A[1..n]A[1..n] 是 nn 个互异数字组成的数组。若 i<ji < j 且 A[i]>A[j]A[i] > A[j],则称 (i,j)(i, j) 为 AA 的一个逆序对(更多讨论见 Problem 2-4)。假设 AA 的元素构成 ⟨1,2,…,n⟩\langle 1, 2, \ldots, n \rangle 的一个均匀随机排列,用指示随机变量计算逆序对的期望个数。

对每一对 i<ji < j,定义指示随机变量

Xi,j={1若 A[i]>A[j],0否则,X_{i, j} = \begin{cases} 1 & \text{若 } A[i] > A[j],\\ 0 & \text{否则,}\end{cases}

则逆序对总数 X=∑i<jXi,jX = \sum_{i < j} X_{i, j}。在均匀随机排列中,A[i]A[i] 与 A[j]A[j] 两个位置上的元素谁大谁小是对称的,因此 Pr⁡{A[i]>A[j]}=1/2\Pr\{A[i] > A[j]\} = 1 / 2。于是

E[∑i<jXi,j]=∑i<jE[Xi,j]=∑i=1n−1∑j=i+1nPr⁡{A[i]>A[j]}=12∑i=1n−1(n−i)=12⋅n(n−1)2=n(n−1)4.\begin{aligned} \text E\Bigg[\sum_{i < j} X_{i, j}\Bigg] & = \sum_{i < j} E[X_{i, j}] \\\\ & = \sum_{i = 1}^{n - 1}\sum_{j = i + 1}^n \Pr\{A[i] > A[j]\} \\\\ & = \frac{1}{2} \sum_{i = 1}^{n - 1} (n - i) \\\\ & = \frac{1}{2} \cdot \frac{n(n - 1)}{2} \\\\ & = \frac{n(n - 1)}{4}. \end{aligned}

即长度为 nn 的均匀随机排列期望含有 n(n−1)4\frac{n(n-1)}{4} 个逆序对。这一结果的工程含义是:插入排序的运行时间正比于输入中的逆序对数量(见 docs/Chap02/Problems/2-4.md 的解答 c 部分),因此上式给出了"随机输入下插入排序平均需要移动多少元素"的精确期望;而该问题解答 d 部分给出的 COUNT-INVERSIONS\text{COUNT-INVERSIONS}(基于归并排序的 Θ(nlg⁡n)\Theta(n \lg n) 计数算法)则是把这一概念用于确定性算法设计的经典例子。本习题则展示:即使逆序对之间存在复杂的相关性,线性期望依然让答案化为一连串独立同分布概率的简单求和。

延伸:指示随机变量在第五章内的其他应用

第 5.2 节建立的这套方法贯穿整个第 5 章,仓库中另有大量使用同一工具的结果可供交叉印证:

  • 第 5.1 节 docs/Chap05/5.1.md:5.1-3 利用 BIASED-RANDOM\text{BIASED-RANDOM} 构造无偏随机数的 UNBIASED-RANDOM\text{UNBIASED-RANDOM},其"每次迭代视为一次伯努利试验、成功概率 2p(1−p)2p(1-p)、期望试验次数 1/(2p(1−p))1/(2p(1-p))"的分析,与本节 5.2-3 的线性期望思路一脉相承。
  • 第 5.4 节 docs/Chap05/5.4.md:5.4-4 用指示随机变量估计"三人生日相同"所需人数(E[X]=(k3)/n2E[X] = \binom{k}{3}/n^2 给出近似值 94);5.4-6 把 nn 个球投入 nn 个箱,用 XiX_i 指示"箱子 ii 为空",得空箱期望 n(n−1n)nn\left(\frac{n-1}{n}\right)^n,恰含一球的期望 n(n−1n)n−1n\left(\frac{n-1}{n}\right)^{n-1}。
  • 问题 5-1(概率计数) docs/Chap05/Problems/5-1.md:证明每次 INCREMENT\text{INCREMENT} 的期望增量恰为 1,从而 nn 次操作后期望计数为 nn;当 ni=100in_i = 100i 时计数服从二项分布,方差为 99n99n。
  • 问题 5-2(无序数组搜索) docs/Chap05/Problems/5-2.md:RANDOM-SEARCH\text{RANDOM-SEARCH} 的期望抽取次数为 n/kn/k(kk 为目标出现次数);确定性线性搜索的平均运行时间用指示随机变量推导为 (n+1)/(k+1)(n + 1) / (k + 1)。

这些练习共同说明:指示随机变量 + 线性期望是概率分析工具箱中性价比最高的组合——它把期望计算降维成"单点概率的累加",是后续第 5.3 节"随机化算法"(docs/Chap05/5.3.md,含 RANDOMIZE-IN-PLACE\text{RANDOMIZE-IN-PLACE} 与 PERMUTE-BY-SORTING\text{PERMUTE-BY-SORTING} 的均匀性证明)以及全书大量随机化分析的基础。

如何在本仓库中阅读与验证本节内容

本仓库是一个以 Markdown + KaTeX 组织的《算法导论(第三版)》习题解答站点(见 README.md),按章节目录组织,完整导航配置在 mkdocs.yml 中。要阅读本节及相关材料:

仓库采用 MkDocs + Material for MkDocs 构建,数学公式由 KaTeX 渲染(mkdocs.yml 中配置了 js/katex.js、css/katex.css 及 CDN 版 KaTeX 资源)。你可以直接浏览各 Markdown 文件核对本节推导的每一步,也可以在本地安装 MkDocs 后通过 mkdocs serve 在浏览器中查看渲染效果。

登录后查看全文
CLRS