概率與計算(算法與數據分析中的隨機化和概率技術原書第2版)

邁克爾·米森馬徹(Michael Mitzenmacher）是哈佛大學的計算機科學教授，他於1996年在加州大學伯克利分校獲得博士學位。在1999年進入哈佛大學之前，他是PaloAlto數字系統研究實驗室的研究員。他獲得了NSF職業獎和艾爾弗雷德·P·斯隆研究獎學金。2002年，他因在糾錯碼方面的工作而獲得IEEE信息理論學會“最佳論文”獎。

譯者序
第2版前言
第1版前言
第1章 事件與概率
1.1 應用：驗證多項式恒等式
1.2 概率論公理
1.3 應用：驗證矩陣乘法
1.4 應用：樸素貝葉斯分類器
1.5 應用：小割隨機化算法
1.6 練習
第2章 離散型隨機變量與期望
2.1 隨機變量與期望
2.1.1 期望的線性性
2.1.2 詹森不等式
2.2 伯努利隨機變量和二項隨機變量
2.3 條件期望
2.4 幾何分布
2.5 應用：快速排序的期望運行時間
2.6 練習
第3章 矩與離差
3.1 馬爾可夫不等式
3.2 隨機變量的方差和矩
3.3 切比雪夫不等式
3.4 中位數和平均值
3.5 應用：計算中位數的隨機化算法
3.5.1 算法
3.5.2 算法分析
3.6 練習
第4章 切爾諾夫界與霍夫丁界
4.1 矩母函數
4.2 切爾諾夫界的導出和應用
4.2.1 泊松試驗和的切爾諾夫界
4.2.2 例：投擲硬幣
4.2.3 應用：估計參數
4.3 某些特殊情況下更好的界
4.4 應用：集合的均衡
4.5 霍夫丁界
*4.6 應用：稀疏網絡中的數據包路由選擇
4.6.1 超立方體網絡上排列的路由選擇
4.6.2 蝶形網絡上排列的路由選擇
4.7 練習
第5章 球、箱子和隨機圖
5.1 例：生日悖論
5.2 球放進箱子
5.2.1 球和箱子模型
5.2.2 應用：桶排序
5.3 泊松分布
5.4 泊松近似
5.5 應用：散列法
5.5.1 鏈散列
5.5.2 散列：二進制數字串
5.5.3 Bloom過濾器
5.5.4 放棄對稱性
5.6 隨機圖
5.6.1 隨機圖模型
5.6.2 應用：隨機圖中的哈密頓圈
5.7 練習
5.8 探索性作業
第6章 概率方法
6.1 基本計數論證
6.2 期望論證
6.2.1 應用：求最大割
6.2.2 應用：最大可滿足性
6.3 利用條件期望消除隨機化
6.4 抽樣和修改
6.4.1 應用：獨立集合
6.4.2 應用：有較大圍長的圖
6.5 二階矩方法
6.6 條件期望不等式
6.7 洛瓦茲局部引理
6.7.1 應用：邊不相交的路徑
6.7.2 應用：可滿足性
*6.8 利用洛瓦茲局部引理的顯式構造
6.9 洛瓦茲局部引理：一般情況
*6.10 洛瓦茲算法局部引理
6.11 練習
第7章 馬爾可夫鏈及隨機遊動
7.1 馬爾可夫鏈：定義及表示
7.1.1 應用：2-可滿足性的隨機化算法
7.1.2 應用：3-可滿足性的隨機化算法
7.2 狀態分類
7.3 平穩分布
7.4 無向圖上的隨機遊動
7.5 Parrondo悖論
7.6 練習
第8章 連續分布與泊松過程
8.1 連續隨機變量
8.1.1 R中的概率分布
8.1.2 聯合分布與條件概率
8.2 均勻分布
8.3 指數分布
8.3.1 指數分布的其他性質
*8.3.2 例：有反饋的球和箱子
8.4 泊松過程
8.4.1 到達間隔分布
8.4.2 組合與分解泊松過程
8.4.3 條件到達時間分布
8.5 連續時間馬爾可夫過程
8.6 例：馬爾可夫排隊論
8.6.1 均衡的M/M/1排隊
8.6.2 均衡的M/M/1/K排隊
8.6.3 M/M/∞排隊中的顧客數
8.7 練習
第9章 正態分布
9.1 正態分布
9.1.1 標準正態分布
9.1.2 一般單變量正態分布
9.1.3 矩母函數
*9.2 二項分布的極限
9.3 中心極限定理
*9.4 多維正態分布
9.5 應用：生成正態分布的隨機值
9.6 大似然點估計
9.7 應用：針對混合高斯分布的EM算法
9.8 練習
第10章 熵、隨機性和信息
10.1 熵函數
10.2 熵和二項式系數
10.3 熵：隨機性的測度
10.4 壓縮
*10.5 編碼：香農定理
10.6 練習
第11章 蒙特卡羅方法
11.1 蒙特卡羅方法
11.2 應用：DNF計數問題
11.2.1 樸素算法
11.2.2 DNF計數問題的完全多項式隨機方案
11.3 從近似抽樣到近似計數
11.4 馬爾可夫鏈蒙特卡羅方法
11.5 練習
11.6 最小支撐樹的探索作業
*第12章 馬爾可夫鏈的耦合
12.1 變異距離和混合時間
12.2 耦合
12.2.1 例：洗牌
12.2.2 例：超立方體上的隨機遊動
12.2.3 例：固定大小的獨立集合
12.3 應用：變異距離是不增的
12.4 幾何收斂
12.5 應用：正常著色法的近似抽樣
12.6 路徑耦合
12.7 練習
第13章 鞅
13.1 鞅
13.2 停時
13.3 瓦爾德等式
13.4 鞅的尾部不等式
13.5 Azuma-Hoeffding不等式的應用
13.5.1 一般形式
13.5.2 應用：模式匹配
13.5.3 應用：球和箱子
13.5.4 應用：色數
13.6 練習
第14章 樣本覆雜度、VC維度以及拉德馬赫覆雜度
14.1 “學習”問題
14.2 VC維度
14.2.1 VC維度的其他例子
14.2.2 增長函數
14.2.3 VC維度的界
14.2.4 ε-網和ε-樣本
14.3 ε-網定理
14.4 應用：PAC學習
14.5 ε-樣本定理
14.5.1 應用：不可知