概率是现代计算机科学核心理论不可或缺的一部分。算法的概率分析、随机化算法以及概率组合构造已经成为计算机科学和应用数学的基本工具。本书全面讲述了离散概率及其在计算中的应用，适于计算科学、数学、工程学等专业高年级本科生阅读。
　　　　　　　　　　　　　　　　　——Richard M. Karp, 加州大学伯克利分校
　　这是一本有关随机化算法的新书。它极好地涵盖了所有基本主题，并包括许多有用的现代应用。
　　　　　　　　　　　　　　　　　——Alan Frieze, 卡内基-梅隆大学

　　随机化与概率技术在现代计算科学中起着重要的作用，其应用遍及组合优化、机器学习、通信网络以及安全协议等诸多领域。
　　本书详细地介绍了概率技术以及在概率算法与分析发展中使用过的范例。本书分两部分，第一部分介绍了随机抽样、期望、马尔可夫不等式、切比雪夫不等式、切尔诺夫界、球和箱子模型、概率技术和马尔可夫链等核心内容。第二部分主要研究连续概率、有限独立性的应用、熵、马尔可夫链蒙特卡罗方法、耦合、鞅和平衡配置等比较高深的课题。

无

为什么要研究随机性
　　计算机科学家为什么要研究和使用随机性？因为计算机出现了太多不可预见的性态！随机性似乎是一种缺点,它使得有效地使用计算机这种已经具有挑战性的工作更加复杂．
　　20世纪,科学研究已经将随机性视为建模和分析中的基本组成部分．例如,在物理方面,牛顿定律使人们相信宇宙的位置是确定的：如果有一个足够大的计算工具和合适的初始条件,人们可以确定若干年后行星的位置．而量子论的发展却提出了非常不同的观点：宇宙仍旧按照自然法则运转,但是这些自然法则的核心是随机性．“上帝不会同宇宙玩骰子．”这是爱因斯坦用来反驳现代量子力学的一句名言．然而,当代亚微粒子物理学的主要理论仍然建立在随机现象和统计规律的基础上,并且在从生物学的遗传和进化到自由市场经济的价格波动模型等几乎所有其他科学领域中,随机性都起着重要的作用．
　　计算机科学也不例外．从一些概率定理证明的高深的理论性概念到个人计算机以太网卡的实用性设计,随机性和概率方法在现代计算机科学中都扮演了关键角色．过去20年来，概率论在计算中的应用得到了巨大的发展,越来越高级、越来越复杂的概率技术已用于更加广泛和更富挑战性的计算机科学应用中．在本书中,我们主要研究随机性影响计算机科学的基本方法:随机化算法和算法的概率分析．
　　随机化算法:随机化算法是执行过程中要求作出随机选择的算法．实际上,随机化程序会使用由随机数发生器产生的数值，从若干执行分支中决定下一步执行哪个分支．例如,以太网卡协议用随机数决定何时试图访问共享的以太网通信介质．随机性在破除对称性、阻止不同的以太网卡同时重复访问介质方面是很有用的．随机化算法的其他常见应用还包括蒙特卡罗模拟和密码学中的初始检验．在这些以及其他重要应用中,随机化算法比最著名的确定性方法更有效,并且在大多数情况下更简单，更容易编程．
　　这些获益是需要付出一定代价的，问题的答案可以有某个不正确的概率,或者只以某个概率保证有效．虽然设计一个有可能不正确的算法似乎有点奇怪,但是如果错误的概率很小,那么提高运行速度和减少占用的内存是有价值的．
　　算法的概率分析:复杂性理论根据计算的复杂性对问题进行分类,尤其是区分简单问题和困难问题．例如,复杂性理论认为流动推销员问题是一个NP难题．如果城市数量以次指数增长的话,那么不可能存在一个可以解决流动推销员问题的任何一个实例的算法．对于经典的最坏情况复杂性理论,一个令人困惑的现象是,在分类上属于困难的计算问题,实际上却很容易解决．概率分析对这种现象给出了理论上的解释．虽然对某些不合理的输入集合,问题难以解决,但对大多数输入(尤其是在日常的应用中),这些问题实际上却容易解决．更确切地说,如果我们认为输入是随机选择的结果,而随机选择是根据所有可能输入集合上的某个概率分布作出的,就很有可能得到一个易于解答的问题实例,而这些实例以相对较小的概率是难解的．算法的概率分析是研究当输入来自恰当定义的概率空间时,算法如何运行的一种方法．正如我们将要看到的,即使是NP难题,也会有对于几乎所有输入都极其有效的算法．
　　关于本书
　　本教材供计算机科学和应用数学专业高年级本科生或低年级研究生一至两个学期的课程使用．在众多优秀的大学中,随机化和概率技术已经从高年级研究生讨论班的主题变为高年级本科生和低年级研究生的正式课程．在这方面有大量相当高深的、研究性的书籍,但仍然需要一本介绍性的教科书,我们希望本书能满足这方面的要求．
　　本书的内容是从最近几年布朗大学(CS 155)和哈佛大学(CS 223)讲授计算机科学中的概率方法课程发展而来的．这些课程和本书强调的是概率技术以及范例,而非特定的应用领域．每章介绍一种方法或者技术,通过一些随机化算法分析或基于随机输入算法的概率分析例子来阐述．其中许多例子来自网络中的问题,反映了网络领域的主要趋势(和作者的兴趣)．
　　本书共14章，可分成两部分,第一部分(第1~7章)是核心内容．本书只要求读者具备基本的概率论知识,相当于计算机科学专业离散数学标准课程包含的内容．第1~3章复习初等概率论,并介绍一些有意义的应用,内容包括随机抽样、期望、马尔可夫不等式、方差和切比雪夫不等式．如果教学班有充分的概率背景,那么这几章可以很快地讲过去,但是建议读者不要跳过这些章节,因为这里介绍了随机化算法和算法的概率分析概念,并且还有一些贯穿全书的例子．
　　第4~7章介绍高级课题,包括切尔诺夫界、球和箱子模型、概率方法和马尔可夫链．同前面几章相比,这几章介绍的内容更加具有挑战性．难度特别大的部分章节(教师可以根据需要考虑跳过这部分内容)标上了星号．根据教学进度,前七章介绍的核心内容可以作为四分之一学年或半学年的课程．
　　本书第二部分(第8~14章)介绍其他一些高级内容,这些内容既可以作为基本课程的必要补充,也可以作为另一门更高级的课程．这些章节是各自独立的,所以教师可以选择最适合学生的内容来讲授．将关于连续概率和熵的两章纳入基本课程中可能是最适合的．对连续概率(第8章)的介绍主要集中在均匀分布和指数分布,其中还包括一些排队论的例子．对于熵(第9章)的介绍包括如何度量随机性,以及在随机提取、压缩和编码中熵是如何自然地产生的．
　　第10章和第11章分别介绍了蒙特卡罗方法和耦合，这两章密切相关,最好在一起学习．第12章是关于鞅的,涵盖了如何处理相关随机变量的各种重要问题,而第13章则从不同的思路继续研究两两独立和消去随机性的进展．最后一章(第14章)讨论平衡配置问题,介绍了作者的一些想法,与第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 Matwani和Prabhakar Raghavan同意我们引用他们优秀的著作《Randomized Algorithms》中的某些练习．
　　最后感谢剑桥大学出版社的Lauren Cowles,她在本书的准备和组织中提供了很多编辑方面的帮助和意见．
　　本书的写作得到了美国国家科学基金会信息技术研究基金(授权号CCR0121154)的部分资助．

Michael Mitzenmacher;Eli Upfal：Michael Mitzenmacher:Michael Mitzenmacher 1996年于加州大学伯克利分校获得博士学位，现为哈佛大学计算机科学教授。在1999年进入哈佛大学之前，他是Palo Alto数字系统研究实验室的研究人员。他曾获美国科学基金（NSF）CAAREER奖和Alfred P. Sloan研究基金。2002年，由于在纠错码方面的出色工作，他获得了IEEE信息论学会的“最佳论文”奖。
Eli Upfal:Eli Upfal 于以色列耶路撒冷希伯来大学获得博士学位，现为布朗大学计算机科学教授、系主任。在1997年进入布朗大学之前，他是IBM研究部的研究人员、以色列Weizmann科学院的教授。他的主要研究兴趣包括随机化计算和算法的概率分析及其在最优化算法、通信网络、并行计算和分布式计算、计算生物学中的应用。

史道济 等：暂无简介

随着人类对客观世界认识的不断加深，现在人们普遍认为实际中一切可观测对象几乎都具有随机性．计算机科学领域也不例外，许多比较高深的概率方法在计算机科学中获得了越来越广泛的应用，其中最主要的问题就是随机化算法及算法的概率分析．
　　随机化算法就是在运行到某一步时需要在诸多可能中随机选择其中之一作为下一步的算法． 在某些问题中，这种算法比最好的确定性算法还有效，而且常常比较简单，易于编写程序． 算法的概率分析则是研究对具有某种分布的随机输入，即使是一个理论上的NP难题，也有很大可能成为一个容易解决的实例． 这些内容已成为计算机科学与应用数学的基本工具，本书正是为这些学科以及某些工科的高年级本科生与研究生而写的，具有以下几个特点：
　　1.内容安排与传统做法不一样． 各章次序是以文献中的相对重要性排序的，前一部分（第1~7章）是核心内容，后一部分（第8~14章）是相对高深的内容． 因此教师在讲授时，可根据需要进行适当调整．
　　2.理论与实际相结合． 每章介绍一种方法，并给出利用随机化算法或对算法的概率分析的例子，但这并不说明本书仅强调实际应用，事实上，除了一些特殊情况，书中对所有的定理都给出了严格的证明．
　　3.大量的练习与例子． 全书共有300多道练习，其中有些练习要求读者自己编写程序，并在计算机上运行，检查与相关理论是否一致． 这些例子与练习有助于培养学生的实际编程能力，不仅对理解书中的内容有帮助，更是计算机科学与应用数学及某些工科学生的自主创新所不可缺少的环节．
　　本书由史道济、李璠、刘晶、郭慧、贺广婷、吴新荣、李秀敏、蔡霞、辛凌雯、徐付霞、王秀林、刘娟和张春英共同翻译完成，史道济翻译了第8、11两章，并进行了全书的审查和统稿工作． 对原书中出现的某些印刷错误，我们已作了改正，不再一一指出．
　　限于译者的水平，译文难免有不妥之处，欢迎专家和读者批评指正．

目录
译者序
前言
第1章事件与概率
11应用:验证多项式恒等式
12概率论公理
13应用:验证矩阵乘法
14应用:最小割随机化算法
练习
第2章离散随机变量与期望
21随机变量与期望
211期望的线性性
212詹森不等式
22伯努利随机变量和二项随机变量
23条件期望
24几何分布
241例：赠券收集问题
25应用：快速排序的期望运行时间
练习
第3章矩与离差
31马尔可夫不等式
32随机变量的方差和矩
321例：二项随机变量的方差
33切比雪夫不等式
331例：赠券收集问题
34应用：计算中位数的随机化算法
341算法
342算法分析
练习
第4章切尔诺夫界
41矩母函数
42切尔诺夫界的导出和应用
421泊松试验和的切尔诺夫界
422例:投掷硬币
423应用:估计参数
43某些特殊情况下更好的界
44应用:集合的均衡
*45应用:稀疏网络中的数据包路由选择
451超立方体网络上排列的路由选择
452蝶形网络上排列的路由选择
练习
第5章球、箱子和随机图
51例:生日悖论
52球和箱子模型
521球和箱子模型
522应用：桶排序
53泊松分布
531二项分布的极限
54泊松近似
*541例:赠券收集问题再讨论
55应用:散列法
551链散列
552散列:二进制数字串
553Bloom过滤器
554放弃对称性
56随机图
561随机图模型
562应用:随机图中的哈密顿圈
练习
探索性作业
第6章概率方法
61基本计数论证
62期望论证
621应用：求最大割
622应用： 最大可满足性
63利用条件期望消除随机化
64抽样和修改
641应用：独立集合
642应用：有较大围长的图
65二阶矩方法
651应用：随机图的阈性质
66条件期望不等式
67洛瓦兹局部引理
671应用: 边不相交的路径
672应用：可满足性
*68利用洛瓦兹局部引理的显式构造
681应用：可满足性算法
69洛瓦兹局部引理: 一般情况
练习
第7章马尔可夫链及随机游动
71马尔可夫链：定义及表示
711应用：2可满足性的随机化算法
712应用：3可满足性的随机化算法
72状态分类
721例：赌徒的破产
73平稳分布
731例：简单的队列
74无向图上的随机游动
741应用：s-t连通性算法
75Parrondo悖论
练习
第8章连续分布与泊松过程
81连续随机变量
811R中的概率分布
812联合分布与条件概率
82均匀分布
821均匀分布的其他性质
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3M/M/∞排队中的顾客数
练习
第9章熵、随机性和信息
91熵函数
92熵和二项式系数
93熵：随机性的测度
94压缩
*95编码：香农定理
练习
第10章蒙特卡罗方法
101蒙特卡罗方法

102应用：DNF计数问题
1021朴素算法
1022DNF计数问题的完全
多项式随机方案
103从近似抽样到近似计数
104马尔可夫链蒙特卡罗方法
1041Metropolis算法
练习
最小支撑树的探索性作业
*第11章马尔可夫链的耦合
111变异距离和混合时间
112耦合
1121例：洗牌
1122例：超立方体上的随机游动
1123例：固定大小的独立集合
113应用：变异距离是不增的
114几何收敛
115应用：正常着色法的近似抽样
116路径耦合
练习
第12章鞅
121鞅
122停时
1221例：选举定理
123瓦尔德方程
124鞅的尾部不等式
125AzumaHoeffding不等式的应用
1251一般形式
1252应用：模式匹配
1253应用：球和箱子
1254应用：色数
练习
第13章两两独立及通用散列函数
131两两独立
1311例：两两独立的二进制数字的构造
1312应用：消去最大割算法的随机性
1313例：构造关于一个素数模的两两独立的值
132两两独立变量的切比雪夫不等式
1321应用：利用少量随机二进制数字的抽样
133通用散列函数族
1331例：一个2维通用散列函数族
1332例：一个2维强通用散列函数族
1333应用：完美散列
134应用：在数据流中寻找重量级的源终点
练习
*第14章平衡配置
141两种选择的影响力
1411上界
142两种选择：下界
143两种选择影响力的应用
1431散列
1432动态资源配置
练习
进一步阅读材料
索引