概率与计算 算法与数据分析中的随机化和概率技术(原书第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.3Bloom过滤器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.5Parrondo悖论141
7.6练习144
第8章连续分布与泊松过程149
8.1连续随机变量149
8.1.1R中的概率分布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.3M/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.2DNF计数问题的接近多项式随机方案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.5Azuma-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.2VC维度266
14.2.1VC维度的其他例子267
14.2.2增长函数268
14.2.3VC维度的合成界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.1Zipf定律和其他例子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