第 5 章概率分析与随机算法 (Probabilistic Analysis and Randomized Algorithms)

核心结论

概率分析 (Probabilistic Analysis)：假设输入服从某个分布，分析算法的平均情况运行时间。前提是知道或能合理假设输入分布。
指示随机变量 (Indicator Random Variables)：把「事件 A 是否发生」编码为 0/1 随机变量；期望值 = 事件概率 (引理 5.1)。线性期望 (linearity of expectation) 让求和交换。
随机算法 (Randomized Algorithms)：算法本身引入随机性（伪随机数生成器），而非依赖输入分布。分析「期望运行时间」。
雇用问题的指示变量分析：假设候选人随机顺序，期望雇用次数 = ln n + O(1)——只需花「ln n 倍」雇用费。
生日悖论 (Birthday Paradox)：n = 365 时，只需 ~23 人生日就有 50% 概率两人同生日；更一般地，n 元素两两不重复只需 ~√n 步。
球与箱子 (Balls and Bobs)：n 球投入 n 箱——某一箱恰好 ≥ 2 球的概率 = 1 - (n! / n^n) ≈ 1 - 1/e ≈ 0.632；最大箱球数 ≈ Θ(ln n / ln ln n)。

本章主旨

本章是「概率 + 算法」的开端。先用雇用问题引入概率分析（依赖输入分布），再用指示随机变量这一关键技术分析雇用问题的期望代价（ln n）；然后引入随机算法（算法主动引入随机数）；最后用三个经典问题（生日悖论、球与箱、连续胜负、在线雇用）展示概率工具在算法分析与设计中的应用。

一、核心概念

本章围绕 6 个核心概念展开：先引入雇用问题作为概率分析的载体，再用指示随机变量求解；区分概率分析与随机算法；最后用三个经典概率问题展示工具的应用。

概念	定义 + 重要性	实现提示
雇用问题 (Hiring Problem)	逐一面试候选人，若比当前更优则雇用。模型：寻找「在线最大值更新」的代价。	§5.1；最坏 O(n) 次雇用，平均（输入随机） = ln n + O(1)。
指示随机变量 (Indicator R.V.)	把事件 A 编码为 0/1 随机变量 \(I\{A\}\)；期望值 = Pr{A}（引理 5.1）。	§5.2；配合「线性期望」= 强大求和工具。
概率分析 vs 随机算法	概率分析：假设输入分布，分析平均情况。随机算法：算法主动调用 RANDOM，分析期望。	§5.1；二者目标相同（期望运行时间），但假设不同——随机算法不依赖输入。
生日悖论 (Birthday Paradox)	n 元素两两不重复的步数 ≈ √(2n ln(1/(1-p)))；对 n = 365、p = 1/2 → ~23。	§5.4.1；用于散列碰撞分析（第 11 章）。
球与箱子 (Balls and Bins)	n 球投入 n 箱，碰撞概率 = 1 - (n!/n^n) ≈ 1 - 1/e；最大箱球数 ≈ Θ(ln n / ln ln n)。	§5.4.2；用于散列表最坏性能与并行调度分析。
在线雇用问题 (Online Hiring)	必须立即决定是否雇用，无回头机会；算法：先拒前 k 个（记录最优），后雇用首个超过该最优的；最优 k = n/e。	§5.4.4；秘书问题的简化版，期望雇用 ~n/e 人。

概念

定义 + 重要性

实现提示

雇用问题 (Hiring Problem)

逐一面试候选人，若比当前更优则雇用。模型：寻找「在线最大值更新」的代价。

§5.1；最坏 O(n) 次雇用，平均（输入随机） = ln n + O(1)。

指示随机变量 (Indicator R.V.)

把事件 A 编码为 0/1 随机变量 \(I\{A\}\)；期望值 = Pr{A}（引理 5.1）。

§5.2；配合「线性期望」= 强大求和工具。

概率分析 vs 随机算法

概率分析：假设输入分布，分析平均情况。随机算法：算法主动调用 RANDOM，分析期望。

§5.1；二者目标相同（期望运行时间），但假设不同——随机算法不依赖输入。

生日悖论 (Birthday Paradox)

n 元素两两不重复的步数 ≈ √(2n ln(1/(1-p)))；对 n = 365、p = 1/2 → ~23。

§5.4.1；用于散列碰撞分析（第 11 章）。

球与箱子 (Balls and Bins)

n 球投入 n 箱，碰撞概率 = 1 - (n!/n^n) ≈ 1 - 1/e；最大箱球数 ≈ Θ(ln n / ln ln n)。

§5.4.2；用于散列表最坏性能与并行调度分析。

在线雇用问题 (Online Hiring)

必须立即决定是否雇用，无回头机会；算法：先拒前 k 个（记录最优），后雇用首个超过该最优的；最优 k = n/e。

§5.4.4；秘书问题的简化版，期望雇用 ~n/e 人。

二、详细笔记

5.1 雇用问题 (Hiring Problem)

What：依次面试 n 个候选人；若当前候选人优于之前所有人，则「雇用」并解雇现任。关注雇用次数 m——决定总成本。

Why：雇用问题是「在线极值追踪」的模型——许多场景需要实时更新最大值（最大子数组变形、在线最大值、在线学习中位数等）；分析期望雇用次数 = Θ(ln n) 展示了概率工具的威力。

How：三种分析角度（§5.1）：

最坏情况：候选按递增顺序到达，每次都比之前更优 → 雇用 n 次 → 总成本 O(n c_h)。
概率分析：假设候选人到达顺序是均匀随机排列；求期望雇用次数。
随机算法：候选人列表已知，每天随机抽一个面试——把「输入随机」变为「算法主动随机」。

HIRE-ASSISTANT 伪代码（§5.1）：

\[\begin{array}{rl} 1 & best = 0 \quad \text{// 最差虚拟候选人} \\ 2 & \textbf{for } i = 1 \textbf{ to } n \\ 3 & \quad \text{interview candidate } i \\ 4 & \quad \textbf{if } candidate(i) \text{ better than } candidate(best) \\ 5 & \quad\quad best = i \\ 6 & \quad\quad hire candidate(i) \end{array}\]

成本模型：面试成本 c_i（低）、雇用成本 c_h（高）；总成本 = O(c_i n + c_h m)。通常关心雇用次数 m。

When：当输入可能有随机性、或可以主动引入随机性时；当最坏情况分析给出过于悲观的上界时；当需要「在线」决策（不知道未来输入）时。

Example：n = 10 时，最坏情况雇用 10 次；输入随机时期望雇用 ln 10 + O(1) ≈ 3 次——10 倍改进。

5.2 指示随机变量 (Indicator Random Variables)

What：把样本空间中的事件 A 编码为 0/1 随机变量：

\[I\{A\} = \begin{cases} 1 & \text{if } A \text{ occurs} \\ 0 & \text{otherwise} \end{cases}\]

（式 5.1）

Why：把概率问题转化为期望问题——而期望可用线性期望拆分求和。这是把「事件计数」转化为「期望」的利器。

How：核心引理（引理 5.1）：

\[E[I\{A\}] = \Pr\{A\}\]

证明：\(E[I\{A\}\) = 1 \cdot \Pr{A} + 0 \cdot \Pr\{\bar A\} = \Pr{A}]。

线性期望（附录 C.21）：无论随机变量是否独立，

\[E\left[\sum_i X_i\right] = \sum_i E[X_i]\]

雇用问题分析（§5.2）：

设 \(X_i = I\{\text{candidate } i \text{ is hired}\}\)。
\(X = \sum_{i=1}^n X_i\) = 总雇用次数。
候选 \(i\) 被雇用 ⟺ 它比前 i-1 个候选都优 → 在 i 个随机顺序中它是「最优」的概率 = 1/i。
\(E[X_i\) = \Pr\{\text{candidate } i \text{ hired}\} = 1/i]（式 5.3）。
\(E[X\) = \sum_{i=1}^n 1/i = \ln n + O(1)]（式 5.5，调和级数）。

When：

当需要计算「事件发生次数」的期望时。
当事件之间可能相关时（线性期望不要求独立）。
当概率直接计算复杂时（用指示变量转化为期望后用线性求和）。

Example：n 次掷公平硬币，「正面次数」的期望：

设 \(X_i = I\{\text{i-th toss is heads}\}\)，\(E[X_i\) = 1/2]。
\(X = \sum X_i\)，\(E[X\) = n/2]。

5.3 概率分析 vs 随机算法

What：

概率分析：对已知输入分布求平均运行时间；假设外部环境提供「随机」输入。
随机算法：算法内部主动调用 RANDOM(a, b) 产生随机数；行为由「输入 + 随机数」共同决定。分析期望运行时间（对随机数求期望）。

Why：当我们不知道输入分布、或不能合理假设时，概率分析失效；随机算法把「随机性」控制在自己手中——保证期望性能而不依赖输入。

How：随机雇用问题（§5.1）：

候选人列表提前给定，每天随机抽取一个面试（而不是按给定顺序）。
不需要假设「输入随机」——是算法主动打乱顺序。
期望雇用次数与概率分析相同 = ln n + O(1)（因为打乱后的顺序 = 均匀随机排列）。

关键差异：

平均情况：概率分布是输入。
期望运行时间：概率分布是随机数生成器。

When：

概率分析：当能合理假设输入分布（如所有输入等概率）。
随机算法：当输入分布未知但可以「洗牌」时；当随机化能带来性能优势（如哈希中的通用哈希，第 11 章；快速排序的随机化版本，第 7 章）。

Example：

快速排序（第 7 章）：随机化 pivot 选择 → 期望 O(n lg n)，不依赖输入顺序（避免已排序输入的最坏情况）。
通用哈希（第 11 章）：随机选哈希函数 → 期望 O(1) 操作，不依赖具体键。
Treap / Skip List：随机化平衡 → 期望 O(lg n) 操作。

5.4 生日悖论 (Birthday Paradox)

What：n 个元素（出生在 365 天）随机排列，两人同日出生的概率 p 随 n 的变化。

Why：生日悖论揭示「碰撞」发生得远比直觉快——是散列分析的基础（最坏情况下两个键哈希到同一槽）。

How：概率推导（§5.4.1）：

所有生日两两不同的概率：

\[\Pr\{\text{all distinct}\} = \prod_{k=1}^{n-1} \left(1 - \frac{k}{365}\right)\]

用 1 - x ≤ e^{-x}：

\[\Pr\{\text{all distinct}\} \leq \prod_{k=1}^{n-1} e^{-k/365} = e^{-\sum_{k=1}^{n-1} k/365} = e^{-n(n-1)/730}\]

至少两人同日 = 1 - 上式。取 p = 1/2，解 n ≈ √(2 \cdot 365 \cdot \ln 2) ≈ 23。

一般情形：n 个元素随机落入 N 天，至少一对碰撞的概率 p：

\[n \approx \sqrt{2N \ln(1/(1-p))}\]

When：当评估散列函数、bloom filter、概率数据结构的最坏碰撞概率时；密码学（生日攻击）。

Example：n = 23, N = 365 时，碰撞概率约 50.7%；n = 70 时超过 99.9%。散列表设计时：要让碰撞概率 < 0.01，需 N >> n²（与 n² 成正比扩张）。

5.5 球与箱子 (Balls and Bins)

What：n 个球独立均匀随机投入 n 个箱子。分析每个箱子的球数、最大箱球数等。

Why：球与箱模型是分析散列、并行调度、负载均衡、随机图等问题的核心概率工具。

How：核心结论（§5.4.2）：

某箱恰好 ≥ 2 球（即有碰撞）的概率：

\[\Pr\{\text{collision}\} = 1 - \frac{n!}{n^n} \approx 1 - 1/e \approx 0.632\]

最大箱球数：以高概率，最大箱球数 = Θ(ln n / ln ln n)。

证明：第 k 个球落在某特定箱的概率 1/n。固定某箱有 ≥ k 球的概率：

\[\Pr\{\text{某箱} \geq k\} \leq n \binom{n}{k} (1/n)^k \approx \frac{n}{(k/e)^k}\]

取 k = c ln n / ln ln n，让上式 < 1/n。

When：

评估散列表最坏访问长度（链接法）。
评估并行任务调度的负载均衡。
评估随机图 G(n, p) 的最大度。
- 评估随机二叉树的高度（~4.311 ln n）。

Example：n = 1000 个球随机投入 1000 箱——以高概率存在含 ≥ 13 个球的箱子（因为 ln 1000 / ln ln 1000 ≈ 6.9 / 2 ≈ 3.5，乘以常数得 ~10）。

5.6 在线雇用问题 (Online Hiring)

What：必须立即决定是否雇用每个面试者——无回头机会；目标是最大化录用者质量（其排名）。

Why：在线决策的经典模型——面试过程中我们不知道后面是否有更优候选人；「试探 + 决策」是经典策略。

How：Secretary 算法（§5.4.4）：

选参数 k（拒绝前 k 人）。
拒掉前 k 个候选人，记录其中最优者（参考标准）。
之后雇用「第一个超过参考标准」的人。
若未找到，则雇用最后一人。

分析（§5.4.4）：

假设候选随机顺序。
候选 \(i\) 被雇用 ⟺ 它是「后 n-i 个候选中最佳」且 \(i > k\)。
期望雇用次数：

\[E[X] = \sum_{i=k+1}^{n} \Pr\{\text{candidate } i \text{ hired}\} = \sum_{i=k+1}^{n} \frac{1}{n-i+1} \cdot \frac{k}{i-1}\]

最优 k = ⌊n/e⌋，此时期望雇用 ≈ n/e。

When：任何「在线选择问题」——必须立即决策、不能回头、目标选最优。Secretary 问题是一类「最优停止」问题的代表。

Example：n = 100，最优 k = ⌊100/e⌋ ≈ 37。拒掉前 37 人；从第 38 起第一个比前 37 最优者更好的人雇用——约 100/e ≈ 37 人会被雇用。

三、关键图表

核心公式对照表

式编号

内容

式 5.1

指示随机变量定义：\(I\{A\}\) = 1 若 A 发生，否则 0

式 5.2

雇用次数分解：\(X = \sum_{i=1}^n X_i\)

式 5.3

\(E[X_i\) = 1/i]

式 5.4

期望的线性：\(E[X\) = \sum E[X_i]]

式 5.5

雇用问题期望：\(E[X\) = \ln n + O(1)]

引理 5.1

\(E[I\{A\}\) = \Pr{A}]

引理 5.2

雇用问题：期望雇用 \(\ln n + O(1)\) 次

生日悖论

n ≈ √(2N ln 2) ≈ 1.18 √N 使碰撞概率 ≈ 1/2

球与箱

某箱 ≥ 2 球概率 ≈ 1 - 1/e；最大箱 ≈ Θ(ln n / ln ln n)

在线雇用

最优 k = n/e；期望雇用 ≈ n/e

四、思维导图

mindmap
  root((第 5 章 概率与随机算法))
    雇用问题
      最坏O(n)
      平均ln n
      增量更新
    指示随机变量
      0-1编码
      E[I]=Pr
      线性期望
    概率分析
      输入分布
      平均情况
    随机算法
      算法主动随机
      期望运行时间
      不依赖输入
    生日悖论
      23人50%
      √n碰撞
    球与箱
      碰撞≈1-1/e
      最大Θ(ln n/ln ln n)
    在线雇用
      Secretary
      k=n/e
      ~n/e人
    应用
      快速排序
      散列
      跳表

五、重点与易错点

指示随机变量 = 0/1 编码事件：不要把它和「一般随机变量」混淆；它的威力在于「线性期望」不需要独立性。
线性期望不要求独立（附录 C.21）！即使事件相关，\(E[\sum X_i\) = \sum E[X_i]]；这是指示变量方法的关键。
雇用问题最坏 O(n)，平均 ln n：直觉错误——以为「平均情况下也会雇用 Θ(n)」。概率分析揭示「指数级改进」。
概率分析与随机算法的区别：分布对象不同——前者是输入，后者是算法内部随机数。
生日悖论的「违反直觉」：n = 23 人（仅 365 天的 6.3%）就有 50% 概率两人同生日。直觉错误根源：人脑用「和自己比」而非「两两比较」。
球与箱的「碰撞概率 ≈ 1 - 1/e」：n 球投入 n 箱，至少一对碰撞的概率 ≈ 63.2%，与 n 无关（只要 n 足够大）。
最大箱球数 Θ(ln n / ln ln n)：增长非常慢，但仍是 ω(1)——散列表最坏情况可能 Θ(ln n / ln ln n) 个键冲突。
秘书问题的「拒绝 k 个」策略：最优 k = n/e 是经典结果；不能「等到最后才决定」也不能「过早决策」——平衡。
期望 vs 高概率 (with high probability, w.h.p.)：「期望」= 平均意义；「w.h.p.」= ≥ 1 - 1/n^c 概率。两者不同——随机算法分析常用 w.h.p. 给出更强保证。
调和级数 \(\sum 1/i = \ln n + O(1)\)（式 A.7）：雇用问题期望推导关键；许多算法分析的常用结果。
RANDOM(a, b) 的独立性：伪随机数生成器实际是确定性的，但「看起来随机」——本书假设它是真随机。实际工程需用更好的 PRNG（Mersenne Twister 等）。
生日悖论对密码学的警示：碰撞概率 ≈ √(2^N) 增长——生日攻击可在约 2^(N/2) 次尝试内找到碰撞；这是 hash 函数长度设计的基础。
秘书问题要求「严格排序」：候选人必须可比（总序）；不适用于「多维评估」场景。
概率工具不仅用于「最坏输入分析」：也用于「随机算法设计」（如随机化快速排序、随机化 Treap）和「数据结构优化」（如跳表、布谷鸟哈希）。
本章是后续随机算法的「语法基础」：第 7 章随机化快速排序、第 11 章通用哈希、第 12 章随机 BST 等都用本章工具。

第 5 章 概率分析与随机算法 (Probabilistic Analysis and Randomized Algorithms)

核心结论

一、核心概念

二、详细笔记

5.1 雇用问题 (Hiring Problem)

5.2 指示随机变量 (Indicator Random Variables)

5.3 概率分析 vs 随机算法

5.4 生日悖论 (Birthday Paradox)

5.5 球与箱子 (Balls and Bins)

5.6 在线雇用问题 (Online Hiring)

三、关键图表

四、思维导图

五、重点与易错点

第 5 章概率分析与随机算法 (Probabilistic Analysis and Randomized Algorithms)