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章放在一起讀。