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