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

本書詳細地介紹了概率技術以及在概率算法與分析發展中使用過的範例。本書分兩部分，第壹部分介紹了隨機抽樣、期望、馬爾可夫不等式、切比雪夫不等式、切爾諾夫界、球和箱子模型、概率技術和馬爾可夫鏈等核心內容。第二部分主要研究連續概率、有限獨立性的應用、熵、馬爾可夫鏈蒙特卡羅方法、耦合、鞅和平衡配置等比較高深的課題。
本書適合作為高等院校計算機科學和應用數學專業高年級本科生與低年級研究生的教材，也適合作為數學工作者和科技人員的參考書。

概率論與計算機科學相結合的完美教材，全面闡釋算法與數據分析中的隨機化和概率技術

譯者序
第2版前言
第1版前言
第1章　事件與概率1
　1.1　應用：驗證多項式恒等式1
　1.2　概率論公理2
　1.3　應用：驗證矩陣乘法6
　1.4　應用：樸素貝葉斯分類器9
　1.5　應用：最小割隨機化算法11
　1.6　練習13
第2章　離散型隨機變量與期望17
　2.1　隨機變量與期望17
2.1.1　期望的線性性18
2.1.2　詹森不等式19
　2.2　伯努利隨機變量和二項隨機變量20
　2.3　條件期望21
　2.4　幾何分佈24
　2.5　應用：快速排序的期望運行時間27
　2.6　練習29
第3章　矩與離差33
　3.1　馬爾可夫不等式33
　3.2　隨機變量的方差和矩33
　3.3　切比雪夫不等式36
　3.4　中位數和平均值38
　3.5　應用：計算中位數的隨機化算法40
3.5.1　算法40
3.5.2　算法分析41
　3.6　練習44
第4章　切爾諾夫界與霍夫丁界46
　4.1　矩母函數46
　4.2　切爾諾夫界的導出和應用47
4.2.1　泊松試驗和的切爾諾夫界47
4.2.2　例：投擲硬幣50
4.2.3　應用：估計參數50
　4.3　某些特殊情況下更好的界51
　4.4　應用：集合的均衡53
　4.5　霍夫丁界54
　*　4.6　應用：稀疏網絡中的數據包路由選擇56
4.6.1　超立方體網絡上排列的路由選擇56
4.6.2　蝶形網絡上排列的路由選擇61
　4.7　練習65
第5章　球、箱子和隨機圖69
　5.1　例：生日悖論69
　5.2　球放進箱子70
5.2.1　球和箱子模型70
5.2.2　應用：桶排序71
　5.3　泊松分佈72
　5.4　泊松近似75
　5.5　應用：散列法81
5.5.1　鏈散列81
5.5.2　散列：二進制數字串82
5.5.3　Bloom過濾器83
5.5.4　放棄對稱性85
　5.6　隨機圖85
5.6.1　隨機圖模型85
5.6.2　應用：隨機圖中的哈密頓圈87
　5.7　練習92
　5.8　探索性作業95
第6章　概率方法97
　6.1　基本計數論證97
　6.2　期望論證99
6.2.1　應用：求最大割99
6.2.2　應用：最大可滿足性100
　6.3　利用條件期望消除隨機化101
　6.4　抽樣和修改102
6.4.1　應用：獨立集合102
6.4.2　應用：有較大圍長的圖103
　6.5　二階矩方法103
　6.6　條件期望不等式105
　6.7　洛瓦茲局部引理107
6.7.1　應用：邊不相交的路徑109
6.7.2　應用：可滿足性109
　*　6.8　利用洛瓦茲局部引理的顯式構造110
　6.9　洛瓦茲局部引理：一般情況113
　*　6.10　洛瓦茲算法局部引理114
　6.11　練習118
第7章　馬爾可夫鏈及隨機遊動122
　7.1　馬爾可夫鏈：定義及表示122
7.1.1　應用：2可滿足性的隨機化算法124
7.1.2　應用：3可滿足性的隨機化算法127
　7.2　狀態分類130
　7.3　平穩分佈133
　7.4　無向圖上的隨機遊動138
　7.5　Parrondo悖論141
　7.6　練習144
第8章　連續分佈與泊松過程149
　8.1　連續隨機變量149
8.1.1　R中的概率分佈149
8.1.2　聯合分佈與條件概率150
　8.2　均勻分佈152
　8.3　指數分佈155
8.3.1　指數分佈的其他性質155
*　8.3.2　例：有反饋的球和箱子157
　8.4　泊松過程159
8.4.1　到達間隔分佈161
8.4.2　組合與分解泊松過程162
8.4.3　條件到達時間分佈163
　8.5　連續時間馬爾可夫過程165
　8.6　例：馬爾可夫排隊論167
8.6.1　均衡的M/M/1排隊167
8.6.2　均衡的M/M/1/K排隊169
8.6.3　M/M/∞排隊中的顧客數170
　8.7　練習171
第9章　正態分佈176
　9.1　正態分佈176
9.1.1　標準正態分佈176
9.1.2　一般單變量正態分佈177
9.1.3　矩母函數179
　*　9.2　二項分佈的極限180
　9.3　中心極限定理182
　*　9.4　多維正態分佈184
　9.5　應用：生成正態分佈的隨機值187
　9.6　最大似然點估計189
　9.7　應用：針對混合高斯分佈的EM算法192
　9.8　練習195
第10章　熵、隨機性和信息198
　10.1　熵函數198
　10.2　熵和二項式係數200
　10.3　熵：隨機性的測度201
　10.4　壓縮205
　*　10.5　編碼：香農定理207
　10.6　練習213
第11章　蒙特卡羅方法218
　11.1　蒙特卡羅方法218
　11.2　應用：DNF計數問題219
11.2.1　樸素算法220
11.2.2　DNF計數問題的完全多項式隨機方案221
　11.3　從近似抽樣到近似計數223
　11.4　馬爾可夫鏈蒙特卡羅方法226
　11.5　練習229
　11.6　最小支撐樹的探索作業231
*第12章　馬爾可夫鏈的耦合232
　12.1　變異距離和混合時間232
　12.2　耦合234
12.2.1　例：洗牌235
12.2.2　例:超立方體上的隨機遊動235
12.2.3　例：固定大小的獨立集合236
　12.3　應用：變異距離是不增的237
　12.4　幾何收斂239
　12.5　應用：正常著色法的近似抽樣240
　12.6　路徑耦合243
　12.7　練習246
第13章　鞅250
　13.1　鞅250
　13.2　停時251
　13.3　瓦爾德等式254
　13.4　鞅的尾部不等式256
　13.5　Azuma-Hoeffding不等式的應用257
13.5.1　一般形式257
13.5.2　應用：模式匹配259
13.5.3　應用：球和箱子260
13.5.4　應用：色數260
　13.6　練習260
第14章　樣本複雜度、VC維度以及拉德馬赫複雜度264
　14.1　“學習”問題265
　14.2　VC維度266
14.2.1　VC維度的其他例子267
14.2.2　增長函數268
14.2.3　VC維度的合成界269
14.2.4　ε-網和ε-樣本270
　14.3　ε-網定理271
　14.4　應用：PAC學習274
　14.5　ε-樣本定理276
14.5.1　應用：不可知學習279
14.5.2　應用：數據挖掘279
　14.6　拉德馬赫複雜度281
14.6.1　拉德馬赫複雜度和樣本錯誤283
14.6.2　估計拉德馬赫複雜度284
14.6.3　應用：二值分類的不可知學習285
　14.7　練習286
第15章　兩兩獨立及通用散列函數288
　15.1　兩兩獨立288
15.1.1　例：兩兩獨立的二進制數字的構造288
15.1.2　應用：消去最大割算法的隨機性289
15.1.3　例：構造關於一個素數模的兩兩獨立的值290
　15.2　兩兩獨立變量的切比雪夫不等式291
　15.3　通用散列函數族293
15.3.1　例：一個2維通用散列函數族295
15.3.2　例：強2維通用散列函數族295
15.3.3　應用：完美散列297
　15.4　應用：在數據流中尋找重量級的源終點299
　15.5　練習302
第16章　冪律及相關的分佈305
　16.1　冪律分佈：基本定義和性質305
　16.2　語言中的冪律307
16.2.1　Zipf定律和其他例子307
16.2.2　語言優化307
16.2.3　猴子隨意打字308
　16.3　偏好鏈接309
　16.4　冪律在算法分析中的應用312
　16.5　其他相關的分佈314
16.5.1　對數正態分佈314
16.5.2　具有指數截斷的冪律315
　16.6　練習315
第17章　平衡分配和布穀鳥散列318
　17.1　兩種選擇的影響力318
　17.2　兩種選擇：下界322
　17.3　兩種選擇影響力的應用324
17.3.1　散列法324
17.3.2　動態資源分配325
　17.4　布穀鳥散列325
　17.5　布穀鳥散列的擴展332
17.5.1　帶刪除的布穀鳥散列332
17.5.2　處理故障333
17.5.3　更多的選擇和更大的箱子334
　17.6　練習335
延伸閱讀339