基本信息
内容简介
作译者
[美] 迈克尔·米森马彻（Michael Mitzenmacher） 伊莱·阿法尔（Eli Upfal） 著：迈克尔·米森马彻（Michael Mitzenmacher）是哈佛大学的计算机科学教授，他于1996年在加州大学伯克利分校获得博士学位。在1999年进入哈佛大学之前，他是PaloAlto数字系统研究实验室的研究员。他获得了NSF职业奖和艾尔弗雷德·P·斯隆研究奖学金。2002年，他因在纠错码方面的工作而获得IEEE信息理论学会“最佳论文”奖。
Eli Upfal是布朗大学计算机科学系的教授、系主任。他在以色列耶路撒冷的希伯来大学获得了博士学位，在1997年进入布朗大学之前，他是IBM研究部的研究员，以色列魏兹曼科学研究所的教授。 他的主要研究兴趣是随机计算与算法的概率分析及其在优化算法中的应用， 通信网络，并行和分布式计算，以及计算生物学等。
Eli Upfal是布朗大学计算机科学系的教授、系主任。他在以色列耶路撒冷的希伯来大学获得了博士学位，在1997年进入布朗大学之前，他是IBM研究部的研究员，以色列魏兹曼科学研究所的教授。 他的主要研究兴趣是随机计算与算法的概率分析及其在优化算法中的应用， 通信网络，并行和分布式计算，以及计算生物学等。
目录
译者序
第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
第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
前言
第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章)的介绍包括如何度量随机性,以及在随机提取、压缩和编码中，熵是如何自然地产生的．
本书的初版已经过了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章)的介绍包括如何度量随机性,以及在随机提取、压缩和编码中，熵是如何自然地产生的．
媒体评论
随机化和概率技术在现代计算机科学中发挥着重要作用, 其应用范围从组合优化与机器学习到通信网络与安全协议。
本书是概率论与计算机科学相结合的完美教材，系统地介绍概率论、随机过程及样本复杂度、VC维度和拉德马赫复杂度等理论知识，以及一些解决实际问题的算法设计技巧，旨在帮助你学会如何利用概率理论及计算机求解实际问题。你仅需有离散数学的基础知识就能阅读本书, 书中包含大量的实例和应用，其内容严谨，并有较好的可读性。
本书是概率论与计算机科学相结合的完美教材，系统地介绍概率论、随机过程及样本复杂度、VC维度和拉德马赫复杂度等理论知识，以及一些解决实际问题的算法设计技巧，旨在帮助你学会如何利用概率理论及计算机求解实际问题。你仅需有离散数学的基础知识就能阅读本书, 书中包含大量的实例和应用，其内容严谨，并有较好的可读性。
