01 / 导读
导读
引用
Mitzenmacher, M., & Upfal, E. (2017). Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis (2nd ed.). Cambridge University Press.
章节概要
每一章围绕一种概率技术，通过分析随机化算法或算法在随机输入上的表现来阐明该技术。带星号的小节是进阶内容，每章以习题结尾。前言把全书分为核心部分（第1至7章）和基本相互独立的章节（第8至17章）。
第1章：事件与概率
通过多个应用复习初等概率论：验证多项式恒等式、验证矩阵乘法、朴素贝叶斯分类器和随机化最小割算法。概率公理也结合这些例子一并展开。
第2章：离散随机变量与期望
涵盖随机变量与期望（包括期望的线性性和 Jensen 不等式）、伯努利与二项随机变量、条件期望和几何分布。主要应用是集券者问题和快速排序的期望运行时间。
第3章：矩与偏差
引入马尔可夫不等式、方差与矩、切比雪夫不等式，以及中位数与均值的关系，最后讲解计算中位数的随机化算法。
第4章：Chernoff 界与 Hoeffding 界
从矩母函数出发推导 Chernoff 界并用于泊松试验之和，再讨论特殊情形下更好的界、集合平衡和 Hoeffding 界。章末的进阶一节讨论超立方体和蝶形网络上的排列路由。前言指出，后面的大部分内容都需要这一章。
第5章：球、箱与随机图
从生日悖论和球入箱模型开始，展开泊松分布与泊松近似。应用包括桶排序、链式哈希、布隆过滤器以及随机图中的哈密顿圈。本章以一项带编程的探索性作业结尾。
第6章：概率方法
通过基本计数论证、期望论证、取样与修改、二阶矩方法和条件期望不等式来证明存在性，然后讲解利用条件期望的去随机化和 Lovász 局部引理，一般情形与算法版本放在进阶小节中。
第7章：马尔可夫链与随机游走
定义马尔可夫链，并用于2-可满足性和3-可满足性的随机化算法；随后讲状态分类、平稳分布和无向图上的随机游走（含 s–t 连通性算法），以帕隆多悖论结束。
第8–9章：连续分布与泊松过程；正态分布
第8章转向连续随机变量、均匀分布与指数分布、泊松过程、连续时间马尔可夫过程和马尔可夫排队模型。第9章讲正态分布、中心极限定理和多元正态分布，应用于生成正态分布随机值、极大似然估计，以及高斯混合模型的 EM 算法。
第10–12章：熵、随机性与信息；蒙特卡洛方法；马尔可夫链的耦合
第10章引入熵函数、压缩和香农编码定理。第11章讲蒙特卡洛方法、DNF 计数、从近似采样到近似计数，以及包含 Metropolis 算法的马尔可夫链蒙特卡洛方法。第12章展开变差距离、混合时间和耦合，包括路径耦合和对合法着色的采样。前言建议把第11章和第12章放在一起讲授。
第13章：鞅
定义鞅和停时，证明 Wald 等式，并推导尾部不等式，尤其是 Azuma–Hoeffding 不等式，应用于模式匹配、球入箱和色数。
第14章：样本复杂度、VC 维与 Rademacher 复杂度
第二版新增。先建立学习设定并引入 VC 维，再讲 ε-网定理和 ε-样本定理，应用包括 PAC 学习、不可知学习和数据挖掘，最后是 Rademacher 复杂度。
第15–17章：两两独立与全域哈希函数；幂律及相关分布；均衡分配与布谷鸟哈希
第15章讲两两独立、去随机化、全域哈希函数族、完美哈希和数据流中的重击者。第16章（本版新增）讲幂律、齐普夫定律、优先连接以及对数正态分布等相关分布。第17章讲“两个选择的威力”和布谷鸟哈希，包括删除、失败处理和各种变体。
核心概念
第1–3章：基本工具
- 期望的线性性：和的期望等于期望之和，无论变量是否独立。
- 马尔可夫不等式与切比雪夫不等式：先后利用均值和方差得到的最早的尾部界。
第4–7章：核心技术
- Chernoff 界：借助矩母函数得到的、对独立试验之和的指数级小的尾部界。
- 球与箱：生日悖论、哈希和负载问题背后的模型。
- 概率方法：通过证明随机对象以正概率具有所需性质，来证明该对象存在。
- 平稳分布：马尔可夫链的长期行为。
第8–14章：进一步的主题
- 泊松过程：连续时间中的随机到达，是排队例子的基础。
- 熵：随机性的度量，与压缩和编码相联系。
- 耦合与混合时间：证明马尔可夫链快速逼近平稳分布的工具。
- Azuma–Hoeffding 不等式：鞅的集中不等式。
- VC 维：集合类容量的度量，样本量界背后的概念。
第15–17章：哈希与数据结构
- 全域哈希族：只需很少随机性、却对冲突有可证明保证的哈希函数。
- 两个选择的威力：在两个随机箱中选较空的一个，可以显著降低最大负载。
评析
优点
- 以技术为中心的结构。 前言说明重点是概率技术和范式而非具体应用，每章一种方法，例子大多取自网络领域。
- 全书严谨。 除少数例外，结论都附完整证明；前言为此辩护，认为要恰当使用蒙特卡洛等启发式方法，必须牢固掌握其背后的理论。
- 路标清晰。 前七章被标明为核心，进阶小节带星号，后面的章节被说明为基本独立，前言还提出了其他的章节顺序。
- 面向数据驱动工作的更新。 第二版为应对海量数据和机器学习，新增了正态分布、幂律和样本复杂度三章，以及布谷鸟哈希一节。
- 习题与作业。 每章都有习题，第5章和第11章还有带编程的探索性作业。
局限
- 习题以理论为主。 前言说大部分习题是理论性的，只有部分编程题，想要实现练习的读者需自行补充。
- 有意排除启发式方法。 全书只限于可严格分析的方法，因此实用的蒙特卡洛启发式方法只通过其数学基础来介绍。
- 很少指向原始文献。 作者选择不引用原始论文，而在“Further Reading”中给出一份简短的背景书目。
- 前言未完全更新。 第一版前言仍说全书有十四章，而本版有十七章。
在课程中的定位
在算法课程书单中，本书是关于随机化和概率分析的专门教材。Introduction to Algorithms、Algorithm Design Manual、Algorithms Illuminated 和 Algorithms Unlocked 讲授一般的设计与分析；Mitzenmacher 与 Upfal 则集中于随机化算法背后的概率论，因此它是在一般算法课之后读的，而不是替代后者。
Vazirani 的 Approximation Algorithms 与 Williamson 和 Shmoys 的 The Design of Approximation Algorithms 讨论相邻的研究生层次主题。在那里接触随机化方法的读者，可能会发现本书第4章和第6章的尾部界与概率方法是有用的背景。
如何使用本书
本书面向计算机科学和应用数学专业的高年级本科生和研究生低年级学生。前言只要求具备基本的概率论知识（相当于面向计算机科学家的离散数学课程），以及阅读完整证明的意愿。
一学期的安排：把第1至7章作为核心来读；若熟悉概率，可快速读过第1至3章，初次阅读时跳过带星号的小节。后面的章节按兴趣选择：连续概率与熵读第8章和第10章，蒙特卡洛方法与耦合把第11章和第12章放在一起读，鞅读第13章，去随机化与哈希读第15章，学习理论读第14章。第4章是后面大部分内容的前提。
证明才是重点，因此要拿起笔做习题，并完成第5章和第11章的两项探索性作业，亲眼看看这些界在实践中的表现。复习哈希时，可把第5.5节、第15.3节和第17章放在一起读。