本书详细地介绍了概率技术以及在概率算法与分析发展中使用过的范例。本书分两部分，第一部分介绍了随机抽样、期望、马尔可夫不等式、切比雪夫不等式、切尔诺夫界、球和箱子模型、概率技术和马尔可夫链等核心内容。第二部分主要研究连续概率、有限独立性的应用、熵、马尔可夫链蒙特卡罗方法、耦合、鞅和平衡配置等比较高深的课题。
本书适合作为高等院校计算机科学和应用数学专业高年级本科生与低年级研究生的教材，也适合作为数学工作者和科技人员的参考书。
WU
第2版前言
本书的初版已经过了10年，随着大数据分析、机器学习和数据挖掘的重要性越来越突出，概率方法对于计算机科学来说也变得越来越核心．许多相关领域的应用成果，其算法和思路都是建立在对概率与统计的成熟理解基础之上的，要想正确地使用这些工具，对于这些数学概念的透彻理解是必不可少的．而第2版新增的主要内容就是着重于这些概念的介绍．
近年来，诸如万维网、社交网络、基因数据等使得我们能够产生、收集和存储大量的样本数据集，这对我们建立模型和分析这些数据的结构提出了新的挑战．熟练掌握一些标准的分布可以给建立和分析模型打下一个好的基础，新增的第9章包含了绝大多数常见的统计分布，同时也像之前一样，会强调这些分布在计算机科学中如何应用，比如确定分布的尾界等．然而，诸如万维网和社交网络等现代数据集有着一个奇妙的现象，在其中我们往往见不到正态分布，取而代之的是一种有着非常不同性质的、很少见的、特征明显的重尾分布．例如，在万维网中，一些页面经常会有大量的网页链接它们，其被链接的数量要高过平均水平一个数量级．第2版新增的第16章将包含对于建模和理解这种现代数据集来说非常重要的那些特殊分布．
机器学习是近年来计算机科学领域的重大成果之一，它提供了许多高效的工具来建模、理解和预测大数据．但是预测的准确性，特别是准确性和样本容量的关系这一点却常常被人忽略．第2版中新增的第14章将会对这些重要的内容进行详细的介绍．
在新版中，我们也对之前的部分内容进行了充实和更新．例如，我们介绍了重要的洛瓦兹局部引理的算法变化的一些新进展，也新增了一小节用来介绍布谷鸟散列这种享誉盛名且越来越实用的散列法．最后，除了这些新增内容，新版也包括了修正、勘误和许多新习题．
我们对几年来向我们发送了诸多勘误的读者表示由衷的感谢，可惜人数过于众多，我们在此不一一列出了，还望海涵．
第1版前言
为什么要研究随机性
计算机科学家为什么要研究和使用随机性呢?这是因为计算机出现了太多不可预见的状况!加入随机性似乎是一个缺点,它使得有效地使用计算机这种已经具有挑战性的工作变得更加复杂．
从20世纪开始,科学研究已经将随机性视为建模和分析中的基本组成部分．例如,在物理学上,牛顿定律使人们相信宇宙的位置是确定的:如果有一个足够大的计算工具和合适的初始条件,人们可以确定若干年后行星的位置．然而量子理论的发展却提出了不同的观点:宇宙仍旧按照自然法则运转,但是这些自然法则的核心是随机性的．“上帝不会同宇宙玩骰子”，这是爱因斯坦用来反驳现代量子力学的一句名言．然而,当代亚微粒子物理学的主要理论仍然是建立在随机现象和统计规律基础之上的,并且在从生物学的遗传与进化到自由市场经济的价格波动模型等几乎所有其他科学领域中,随机性都起着非常重要的作用．
计算机科学也不例外，从一些概率定理证明的高深理论到个人计算机以太网卡的实用性设计,随机性和概率方法在现代计算机科学中都扮演了关键角色．过去20年以来,概率论在计算中的应用得到了巨大的发展,越来越高级、越来越复杂的概率技术已经被应用于更加广泛和更富挑战性的计算机科学应用中．在本书中,我们主要研究随机性应用于计算机科学的基本方法:随机化算法和算法的概率分析．
随机化算法:随机化算法是执行过程中要求作随机选择的算法．实际上,随机化程序会使用由随机数发生器产生的数值,从若干执行分支中决定下一步执行哪个分支．例如,以太网卡协议用随机数决定何时试图访问共享的以太网通信介质．随机性在打破对称性、防止不同的以太网卡同时重复访问介质方面是非常有用的．随机化算法的其他常见应用还包括蒙特卡罗模拟和密码学中的初始检验．在这些以及其他重要应用中,随机化算法比最有名的确定性方法更有效,并且在大多数情况下更简单,更容易编写程序．
当然，这些优点也是需要付出一定代价的,问题的答案在一定的概率下是不正确的,或者只以某个概率保证有效．虽然设计一个有可能错误的算法似乎有点奇怪,但是如果错误发生的概率很小,那么提高运行速度和减少占用的内存是有价值的．
算法的概率分析:复杂性理论根据计算的复杂性对问题进行分类,尤其是区分简单问题和有难度的问题．例如,复杂性理论认为流动推销员问题是一个NP难题．如果城市数量以次指数增长,那么不可能存在可以解决流动推销员问题的任何一个实用的算法．对于经典的最坏情况复杂性理论,一个令人困惑的现象是,在分类上属于有难度的计算问题,实际上却很容易解决，概率分析对这种现象给出了理论上的解释．虽然对某些不合理的输入数据,问题难以解决,但对大多数输入(尤其是在日常的应用中),这些问题实际上却容易解决．更确切地说,如果我们认为输入是随机选择的结果,而随机选择是根据所有可能输入数据集上的某个概率分布作出的,就很有可能得到一个易于解答的问题实例,而这些实例不能求解的概率是相对较小的．算法的概率分析是研究当输入来自某一适当定义的概率空间时算法如何运行的一种方法．书中我们将会看到,即使是NP难题,也会有对于几乎所有输入都极其有效的算法．
关于本书
本书可以作为计算机科学和应用数学专业高年级本科生或低年级研究生一至两个学期的课程教材．在众多较好的大学中,随机化和概率技术已经从高年级研究生讨论班的主题变为高年级本科生和低年级研究生的正式课程．在这方面有大量相当高深的、研究性的著作,但仍然需要一本介绍性的教科书,我们希望本书能起到这方面的作用．
本书的内容是从近几年在布朗大学(CS 155)和哈佛大学(CS 223)讲授计算机科学中的概率方法这类课程发展而来的．这些课程和本书强调的是概率技术以及具体的范例,而非特定的应用领域．每章介绍一种方法或者技术,通过一些随机化算法分析或基于随机输入算法的概率分析例子来阐述．其中许多例子来自网络中的问题,反映了网络领域的主要趋势(和作者的兴趣)．
本书第1版共有14章,可分成两部分,第一部分(第1～7章)是核心内容．本书只要求读者具备基本的概率论知识,相当于计算机科学专业的离散数学课程包含的内容．第1～3章复习初等概率论,并介绍一些有意义的应用,内容包括随机抽样、期望、马尔可夫不等式、方差和切比雪夫不等式．如果教学班有充分的概率论背景,那么这几章可以很快地讲过去,但是建议读者不要跳过这些章节,因为这里介绍了随机化算法和算法的概率分析概念,并且还有一些贯穿全书的例子．
第4～7章介绍高级课题,包括切尔诺夫界、球和箱子模型、概率方法和马尔可夫链．同前面几章相比,这几章介绍的内容更具有挑战性．难度特别大的章节书中标有星号(教师可以根据需要考虑是否跳过这部分内容)．根据教学进度,前7章介绍的核心内容可以作为四分之一学年或半学年的课程．
本书第二部分(第8章、第10～13章、第15章、第17章)介绍另外一些高级内容,这些内容既可以作为基本课程的必要补充,也可以作为另一门更高级的课程．这些章节是各自独立的,教师可以选择最适合学生的内容来讲授．将连续概率和熵这两章纳入基本课程中可能是比较好的选择．对连续概率(第8章)的介绍主要集中在均匀分布和指数分布,其中还包括一些排队论的例子,对熵(第10章)的介绍包括如何度量随机性,以及在随机提取、压缩和编码中，熵是如何自然地产生的．
第11章和第12章分别介绍了蒙特卡罗方法和耦合,这两章是密切相关的,最好放在一起学习；第13章是关于鞅的知识,包含了如何处理相关随机变量的各种重要问题；而第15章则从不同的思路继续研究两两独立和消去随机性的进展；最后一章(第17章)讨论了均衡配置问题,介绍了作者的一些想法,该章与第5章的球和箱子问题密切相关．
本书各个章节的顺序,尤其是第一部分的顺序,是根据它们在算法中的相对重要性安排的,例如,我们先介绍切尔诺夫界,而其他一些基本的概率知识(如马尔可夫链)则放在后面,但是,教师在讲授时可以按照不同顺序进行．在更强调一般随机过程的课程中,可以在第1～3章后直接讲授马尔可夫链(第7章),随后讲授球、箱子和随机图(第5章,略去哈密顿圈的例子），接下来可以跳过第6章关于概率方法的内容,而讲授连续概率和泊松过程(第8章)．本书其余大部分内容都会用到第4章中关于切尔诺夫界的知识．
书中的大部分练习都是理论性的,但我们也选取了一些编程练习——包括两个需要编程的探索性作业．我们发现偶尔的编程练习,对于加强本书的思想和增添课程的多样性很有帮助．
我们将本书的内容严格限制在数学分析的方法和技术之内,除去一些特殊情况,本书的所有定理都给出了完整的证明．显然,许多相当有用的概率方法并不在这种严格的限制之内．例如,在蒙特卡罗方法的重要领域中,大多数实际解具有启发性,从而证实了试验估计比严格数学分析更有效．我们认为,为了很好地应用和理解启发性方法的优缺点,扎实地掌握基础概率理论和本书给出的严格技术是十分必要的,我们希望读者在学完本书之后能够喜欢这种处理方式．
致谢
首先我们要感谢许多曾经研究本书选取的极好题材的概率论专家和计算机科学家．我们没有把大量原始论文作为参考文献放入书中,只是提供一些优秀的参考书目作为本书各章的背景材料和更进一步的讨论依据．
书中许多内容来自布朗大学CS 155课程和哈佛大学CS 223课程的学生和老师的建议和反馈,我们特别要感谢Aris Anagnostopoulos、Eden Hochbaum、Rob Hunter和Adam Kirsch,他们阅读了本书的初稿,并提出了修改意见．
我们尤其要感谢Dick Karp,2003年秋季,他在伯克利大学授课(CS 174)期间,使用了本教材的初稿,他的早期建议和修改意见对改进教材是非常有价值的．Peter Bartlett在2004年春季于伯克利大学授课(CS 174)期间,也提出了很多有用的建议和修改意见．
感谢在本书编写过程中认真读过部分初稿的同事,他们在内容及表达方面指出许多错误,提出重要的改进意见．他们是:Artur Czumaj、Alan Frieze、Claire Kenyon、Joe Marks、Salil Vadhan、Eric Vigoda．另外,感谢为出版社审稿的一些不知道姓名的评审者．
感谢Rajeev Motwani和Prabhakar Raghavan同意我们引用他们优秀的著作《Randomized Algorithms》中的某些练习．
最后感谢剑桥大学出版社的Lauren Cowles,她在本书的准备和组织过程中提供了很多编辑方面的帮助和意见．
本书的写作得到了美国国家科学基金会信息技术研究基金(授权号CCR-0121154)的部分资助．
数学
随机化和概率技术在现代计算机科学中发挥着重要作用, 其应用范围从组合优化与机器学习到通信网络与安全协议。
本书是概率论与计算机科学相结合的完美教材，系统地介绍概率论、随机过程及样本复杂度、VC维度和拉德马赫复杂度等理论知识，以及一些解决实际问题的算法设计技巧，旨在帮助你学会如何利用概率理论及计算机求解实际问题。你仅需有离散数学的基础知识就能阅读本书, 书中包含大量的实例和应用，其内容严谨，并有较好的可读性。
[美] 迈克尔·米森马彻（Michael Mitzenmacher） 伊莱·阿法尔（Eli Upfal） 著：迈克尔·米森马彻（Michael Mitzenmacher）是哈佛大学的计算机科学教授，他于1996年在加州大学伯克利分校获得博士学位。在1999年进入哈佛大学之前，他是PaloAlto数字系统研究实验室的研究员。他获得了NSF职业奖和艾尔弗雷德·P·斯隆研究奖学金。2002年，他因在纠错码方面的工作而获得IEEE信息理论学会“最佳论文”奖。
Eli Upfal是布朗大学计算机科学系的教授、系主任。他在以色列耶路撒冷的希伯来大学获得了博士学位，在1997年进入布朗大学之前，他是IBM研究部的研究员，以色列魏兹曼科学研究所的教授。 他的主要研究兴趣是随机计算与算法的概率分析及其在优化算法中的应用， 通信网络，并行和分布式计算，以及计算生物学等。
冉启康 译：暂无简介
在现实世界中，不确定现象（或者随机现象）是普遍存在的．这类随机现象表面看起来无法把握，其实，在其不确定的背后，往往隐藏着某种确定的概率规律，因此，以概率为基础的随机理论应运而生．由于其广泛的应用价值，随机理论成为20世纪至21世纪发展最为迅速的学科之一．现在它已经成为数学、物理、天文、地理、经济、军事、农业、医疗等众多学科的基本工具．同样，随机理论在计算机科学中也发挥着越来越重要的作用，几乎所有的随机理论在计算机科学中都可见其踪迹，其中，随机变量及其分布、高斯过程、马尔可夫过程、鞅、幂律分布等更是计算科学中的常用工具．
由哈佛大学的Michael Mitzenmacher教授和布朗大学的Eli Upfal教授编写的《Probability and Computing:Randomization and Probabilistic Techniques in Algorithms and Data Analysis》是一本非常有特色的不可多得的好教材,这本书不仅详细介绍了随机化算法和算法的概率分析,而且采用了大量生动的例子来说明这些理论和方法是如何应用在实际生活中的,让读者在获得随机化算法和算法的概率分析知识的同时,也体会到了随机理论的应用魅力．
本书第1版的中文版于2007年由史道济等翻译,机械工业出版社出版，出版后深受国内师生的欢迎,对我国的计算机随机化理论的教学产生了很大的影响．经过十年的修改和锤炼,原书作者在2017年出版了第2版，除了对第1版进行大幅度的修改外，第2版还增加了朴素贝叶斯分类器、霍夫丁界、正态分布、样本复杂度、VC维度、拉德马赫复杂度、幂律及相关分布等章节，内容得到极大的丰富．为了满足国内读者的需求，受机械工业出版社的委托，我将第2版翻译成中文．我在翻译本书的过程中,参考了第1版的中译本,在此对第1版的译者表示感谢，相信这个版本也一定会受到国内各界的欢迎．在本书的翻译过程中，上海财经大学数学学院研究生林嘉恒、姬智会为初稿校对、文字输入做了大量的工作，在此对两位表示感谢．限于时间和水平，译文的不当之处在所难免，敬请读者和相关领域的专家、学者批评指正．
冉启康
2019年4月
译者序
第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
