第05章 概率分析与随机化算法 — 章节汇总

章节概览

本章是第4章的自然延伸，从确定性的算法分析转向概率分析与随机化算法。前半部分（5.15.2）以雇佣问题为引例，系统介绍了概率分析的基本思想与核心工具——指示器随机变量；后半部分（5.35.4）阐述了随机化算法的设计理念，并通过生日悖论、球与箱子、连续正面、在线雇佣等经典问题展示了概率分析的广泛应用。本章的核心贡献在于：(1) 建立了概率分析的方法论框架；(2) 引入了指示器随机变量 + 期望线性性这一强大分析工具；(3) 阐明了概率分析与随机化算法的本质区别。

---

5.1~5.2 概率分析与指示器随机变量

小节	核心主题	关键结论
5.1 雇佣问题	雇佣问题引入概率分析	最坏情况 $O(c_{h}n)$；平均情况 $O(c_h\ln n)$
5.2 指示器随机变量	指示器随机变量与期望线性性	$E[I\{A\}]=\mathrm{Pr}\{A\}$；期望线性性不要求独立性

核心思路：雇佣问题是”在序列中维护当前最大值”这一常见计算范式的模型。HIRE-ASSISTANT 算法在最坏情况下雇佣 $n$ 次（费用 $O(c_{h}n)$），但通过假设候选人以均匀随机排列到达，利用指示器随机变量分析可得期望雇佣次数为第 $n$ 个调和数 $H_n\approx \ln n$，费用降至 $O(c_h\ln n)$。指示器随机变量 $I\{A\}$ 将概率问题转化为期望计算，结合期望的线性性（即使随机变量不独立），可以极大地简化涉及多个事件的期望值推导。

---

5.3~5.4 随机化算法与进阶应用

小节	核心主题	关键结论
5.3 随机化算法	随机化算法的设计与正确性	RANDOMIZE-IN-PLACE 产生均匀随机排列；概率分析 vs 随机化算法
5.4 概率分析与指示器随机变量的进一步应用	四个经典概率分析案例	生日悖论（23人→50%碰撞）、球与箱子、连续正面、在线雇佣

核心思路：5.3 随机化算法阐明了概率分析与随机化算法的本质区别——概率分析假设输入服从某种分布来分析确定性算法，而随机化算法在算法内部引入随机性，使得对于任何输入都能保证期望性能。RANDOMIZE-IN-PLACE 过程通过原地位换产生均匀随机排列，是实际中最常用的随机置换方法。5.4 概率分析与指示器随机变量的进一步应用通过四个经典问题展示了概率分析工具的广泛适用性：生日悖论揭示了碰撞概率远高于直觉的惊人事实，球与箱子问题是哈希分析的基础模型，连续正面展示了如何利用指示器随机变量计算特定模式的期望等待时间，在线雇佣问题则将雇佣问题推广到需要在线做出不可撤回决策的场景。

---

本章核心知识点

关键定义

概念	定义	出处
概率分析	利用概率论分析算法的运行时间或其它量，需要假设输入的分布	5.1 雇佣问题
指示器随机变量	$I\{A\}=\{\begin{array}{ll}1& \text{若事件 }A\text{ 发生}\\ 0& \text{否则}\end{array}$	5.2 指示器随机变量
随机化算法	在算法执行过程中做出随机选择的算法，期望性能不依赖特定输入	5.3 随机化算法
均匀随机排列	$n$ 个元素的 $n!$ 种排列中每种等可能（概率 $1/n!$）	5.3 随机化算法

关键定理与引理

编号	内容	出处
引理 5.1	$E[I\{A\}]=\mathrm{Pr}\{A\}$	5.2 指示器随机变量
引理 5.2	HIRE-ASSISTANT 的平均情况总雇佣费用为 $O(c_h\ln n)$	5.2 指示器随机变量
引理 5.3	PERMUTE-BY-SORTING 产生均匀随机排列	5.3 随机化算法
引理 5.4	RANDOMIZE-IN-PLACE 产生均匀随机排列	5.3 随机化算法
生日悖论	$k\ge 23$ 人时至少两人生日相同的概率 $\ge 1/2$	5.4 概率分析与指示器随机变量的进一步应用

核心分析工具

概率分析工具链：
  指示器随机变量 I{A}  →  E[I{A}] = Pr{A}  →  期望的线性性  →  复杂期望值的简化计算

---

与前序章节的知识关联

前序章节	关联方式
第1章 算法在计算中的角色	雇佣问题是算法作为技术的具体实例
第2章 入门	循环不变式用于证明 RANDOMIZE-IN-PLACE 的正确性；插入排序的最坏/平均分析是概率分析的前置
第3章 运行时间刻画	渐近记号（$O$、$\Theta$、$\Omega$）用于表达概率分析的结论
第4章 分治策略	分治法中的递归关系式求解（主定理）为概率分析提供数学基础

---

学习路线

第5章学习路径：
  5.1 雇佣问题（引例，建立直觉）
    → 5.2 指示器随机变量（核心工具）
      → 5.3 随机化算法（设计理念）
        → 5.4 进阶应用（工具巩固）

学习建议

本章是算法分析从确定性到概率性的关键转折点。建议按 5.1 → 5.2 → 5.3 → 5.4 的顺序学习。5.2 节的指示器随机变量是全书后续概率分析的基础工具，务必彻底理解。如果概率论基础薄弱，建议先复习附录 C.1~C.4（计数与概率）。

概率分析与随机化算法