CLRS 5.2 随机变量与期望详解：HIRE-ASSISTANT 雇佣次数、帽子核对问题与逆序对期望

• 文档
• 教程
• 示例工程

导读

本节围绕《算法导论》（Introduction to Algorithms）第 5 章"概率分析与随机化算法"的习题 5.2-1 至 5.2-5 展开，核心工具是指示器随机变量（indicator random variable）与期望的线性性（linearity of expectation）。文章以 HIRE-ASSISTANT 雇佣过程为主线，逐一推导"恰好雇佣 1 次 / n 次 / 2 次的概率"、n 个骰子点数和的期望、帽子核对问题的期望人数，以及随机排列下数组逆序对数的期望，并结合本仓库 C02 逆序对计数实现 与 C++ 版本 印证结论。读完本文，你将掌握用指示器随机变量把"复杂的计数期望"拆解为"简单事件概率之和"的通用套路，并能直接套用到雇佣问题、生日悖论、抛球入箱等经典随机模型。

帽子核对问题（5.2-4）的指示器随机变量推导手稿

背景：HIRE-ASSISTANT 过程与指示器随机变量

第 5 章引入的 HIRE-ASSISTANT 过程描述了一家公司面试 n 位候选人的情景：候选人按随机顺序到达，公司设定一个初始"最合适"的虚拟候选（quality 为 −∞），每面试一人，若其 quality 高于当前最佳者，则雇佣他并更新最佳者。由于一旦雇佣，后续只有 quality 更高的候选人才会触发下一次雇佣，雇佣次数是一个随机变量。

本仓库 5.1.md 中 5.1-1 指出，HIRE-ASSISTANT 能始终确定"谁是最佳"的前提是候选人质量之间存在全序关系（total order）。习题 5.2 系列正是基于这一过程，用指示器随机变量精确刻画雇佣次数的概率分布。

指示器随机变量的核心性质（书中 Lemma 5.1）：对事件 A 定义

X_A = 1 若 A 发生，否则 0

则E[X_A] = Pr{A}，即指示器的期望恰好等于事件发生的概率。结合期望的线性性

E[X_1 + X_2 + ... + X_n] = E[X_1] + E[X_2] + ... + E[X_n]

（该性质对任意随机变量成立，不要求相互独立），我们就能把"总雇佣次数""拿回自己帽子的人数""逆序对数"这类总和型随机变量，分解成若干个 0/1 指示器逐个求期望再求和，从而绕开复杂的联合分布计算。

5.2-1：恰好雇佣一次与恰好雇佣 n 次的概率

题目：在 HIRE-ASSISTANT 中，候选人以随机顺序出现，求恰好雇佣 1 次的概率，以及恰好雇佣 n 次的概率。

解答：假设 n 个候选人的质量是 1, 2, ..., n（互不相同），且所有 n! 种排列等可能。

• 恰好雇佣 1 次：只雇佣一次，意味着第 1 位候选人就是全场最佳（quality 为 n）。在随机排列中，质量最高的候选人身处第 1 位的概率是1/n，因此Pr{恰好雇佣 1 次} = 1/n。

• 恰好雇佣 n 次：雇佣 n 次意味着每面试一位都触发雇佣，即候选人的质量严格递增。在随机排列中，n 个互异元素构成严格递增序列，只有 1 种排列满足（质量恰好按 1, 2, ..., n 的顺序到达），因此Pr{恰好雇佣 n 次} = 1/n!。

直观对照：一次都不雇佣不可能发生（第 1 位候选人必然优于虚拟初始候选人），所以雇佣次数 X 满足 1 ≤ X ≤ n；两个极端值分别对应"第一位就是冠军"和"全程一路走高"两种极端排列。

5.2-2：恰好雇佣两次的概率

题目：求恰好雇佣 2 次的概率。

解答：设第一位候选人的质量为 k（1 ≤ k ≤ n − 1）。若最终只雇佣两次，则：

1. 质量高于 k 的所有 n − k 位候选人必须全部排在"质量最高者"之后，即最佳候选人的位置必须在所有比 k 高的候选人之前；
2. 质量最高的候选人一旦出现就会触发第二次（也是最后一次）雇佣，此后不再有人比他更好。

给定第一位质量为 k 时，n − k 个更优候选人的相对顺序中，质量最高者排在最前面的概率为1/(n − k)。而第一位质量为 k 的概率为1/n。对 k 求和得：

Pr{恰好雇佣 2 次} = Σ_{k=1}^{n−1} (1/n) · (1/(n−k)) = (1/n) · Σ_{k=1}^{n−1} 1/k = H_{n−1} / n

其中H_{n−1} = Σ_{k=1}^{n−1} 1/k是第 n − 1 个调和数。当 n 较大时，H_{n−1} ≈ ln n + γ（γ 为欧拉常数），因此恰好雇佣两次的概率约为(ln n)/n。

这个结果与书中 5.1 节"平均雇佣次数约为 ln n"的结论互为印证：雇佣次数期望增长缓慢，正是源于大部分候选人质量低于当前最佳者、触发雇佣的只是少数"破纪录者"。

5.2-3：n 个骰子点数和的期望

题目：用指示器随机变量计算 n 个骰子点数之和的期望。

解答：设X_i为第 i 个骰子的点数（1 ≤ i ≤ n），每个骰子独立均匀地取 1 到 6。单个骰子的期望为

E[X_i] = (1 + 2 + 3 + 4 + 5 + 6) / 6 = 21/6 = 3.5

总点数X = X_1 + X_2 + ... + X_n，由期望的线性性（此处骰子相互独立，但线性性甚至不需要独立）：

E[X] = Σ_{i=1}^{n} E[X_i] = 3.5n

这道题展示了一个关键方法论：当总随机量是各分量之和时，只需分别求每个分量的期望，完全不需要知道和的分布。若想进一步得到 n 个骰子点数和的具体概率分布（如 3 个骰子和为 10 的概率），才需要枚举组合或使用生成函数，但期望层面 3.5n 已是精确答案。

5.2-4：帽子核对问题的期望人数

题目（经典"帽子核对问题"）：n 位顾客在餐厅寄存帽子，归还时帽子以随机顺序交还。求拿到自己帽子的顾客数的期望。

解答：对每位顾客 i 定义指示器随机变量

X_i = I{ 顾客 i 拿回了自己的帽子 }

总人数X = X_1 + ... + X_n。顾客 i 从 n 顶帽子中恰好拿到自己那一顶的概率为1/n，由指示器性质E[X_i] = Pr{...} = 1/n。再由期望的线性性：

E[X] = Σ_{i=1}^{n} E[X_i] = n · (1/n) = 1

结论：无论 n 多大，拿到自己帽子的顾客数期望恒为 1。这正是上图中手稿展示的四步推导：定义指示器 → 求和 → 逐个求期望（1/n）→ 线性性合并。这个看似"反直觉"的结果是期望线性性的经典示范——尽管 n 个事件{顾客 i 拿回自己的帽子}之间并不独立（一个人拿错会导致另一人拿对的概率变化），期望计算却完全不受影响。

5.2-5：随机排列中逆序对的期望

题目：设 A[1..n] 是 n 个互异数字的数组，若 i < j 且 A[i] > A[j]，则称 (i, j) 为逆序对（参见 Problem 2-4）。假设 A 的每个元素独立、均匀地从 1 到 n 中选取，用指示器随机变量求逆序对的期望个数。

解答：对每一对下标 (i, j)（i < j）定义指示器

Y_{ij} = I{ A[i] > A[j] }

由于数组元素互异且每个排列等可能，任意一对元素 A[i]、A[j] 谁大谁小各占一半，故

E[Y_{ij}] = Pr{A[i] > A[j]} = 1/2

设 X 为逆序对总数，则X = Σ_{i<j} Y_{ij}，总对数 k = C(n, 2) = n(n−1)/2。由期望的线性性：

E[X] = k · E[Y_{ij}] = C(n,2) · 1/2 = n(n−1)/4

直观验证：n 个互异元素共有 C(n,2) 对，每对要么正序要么逆序，随机排列下对称，期望逆序对数恰为总对数的一半。特别地：

• 完全升序排列逆序对数为 0，完全降序排列为 n(n−1)/2，随机排列的期望 n(n−1)/4 正好居中；
• 若元素允许重复，"互异"假设被破坏，Pr{A[i] > A[j]} = 1/2不再成立，结论将改变——这一点在推导中至关重要。

仓库中的 inversions.py 与 inversions.cpp 提供了逆序对计数的归并排序实现：合并两个有序子数组时，若右侧元素 R[j] 小于左侧 L[i]，则左侧剩余全部元素（len(L) - i个，C++ 中为n1 - i）都与 R[j] 构成逆序对，一次累加即可在 O(n log n) 内完成计数。这套"计数型归并"正是检验 5.2-5 结论的实验工具——对随机排列输入反复运行，计数结果的平均值会收敛到 n(n−1)/4。

小结：指示器随机变量的四步套路

纵观 5.2 系列习题，解法高度统一，可归纳为四步：

1. 定义指示器：把关心的总量 X 表示成若干 0/1 事件指示器之和，X = Σ X_i；
2. 求单个期望：利用E[X_i] = Pr{事件 i 发生}，把期望问题转化为单个事件的概率问题；
3. 调用线性性：E[X] = Σ E[X_i]，无需关心各事件是否独立；
4. 代入化简：完成求和并验证极端情况（如 n=1、完全有序/无序等边界）。

这套方法贯穿第 5 章后续内容：5.4 节的生日悖论（空箱数、生日碰撞）、本章 Problems 中的随机搜索期望（几何分布、n(ln n + O(1)) 的收集者问题）以及 5.1.2 中"只用 RANDOM(0,1) 实现 RANDOM(a,b)"的期望运行时间分析（对应仓库 myrandom.py 中的_m_random实现）都以同一思想为基础。掌握指示器随机变量，等于掌握了概率分析章节最核心的分析杠杆。

本仓库的完整习题解答请参见 C05 章节目录，相关代码与推导图（如 5.2-4.png）均可直接复现验证。

• 文档
• 教程
• 示例工程