《概率与计算》

摘要: 《概率与计算》这本书

【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：潮汐朝夕
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

这是一个挖坑贴，随机算法是大数据算法中的重要的算法，《概率与计算》是讲随机算法的书中风评比较好的，此外还有一本《数学女孩-随机算法》。这本书比较偏理论，但是有很多算法领域的例子及其对应的随机算法和概率分析，有部分习题需要编程解决。刷完这本书的工程量比较大，这里先看下这本书里都有什么内容。

本书信息：《概率与计算：算法与数据分析中的随机化和概率技术》
时间: 2019
作者: [美] 迈克尔·米森马彻（Michael Mitzenmacher） 伊莱·阿法尔（Eli Upfal） 著

probability-computing-2nd

---

第一部分：Chap1~7，基础

• Chap1~3: 复习基础概率论，包括 random sampling, expectation, Markov’s inequality, variance, and Chebyshev’s inequality
• Chap4~7: 概率论高阶内容，包括 Chernoff bounds, balls-and-bins models, the probabilistic method, and Markov chains.

第二部分：Chap8~17，additional advanced topic，各章独立

---

第1章　事件与概率

• 1.1　应用：验证多项式恒等式
• 1.2　概率论公理
• 1.3　应用：验证矩阵乘法
• 1.4　应用：朴素贝叶斯分类器
• 1.5　应用：最小割随机化算法

第2章　离散型随机变量与期望

• 2.1　随机变量与期望
  • 2.1.1　期望的线性性
  • 2.1.2　詹森不等式
• 2.2　伯努利随机变量和二项随机变量
• 2.3　条件期望
• 2.4　几何分布
• 2.5　应用：快速排序的期望运行时间

第3章　矩与离差

• 3.1　马尔可夫不等式
• 3.2　随机变量的方差和矩
• 3.3　切比雪夫不等式
• 3.4　中位数和平均值
• 3.5　应用：计算中位数的随机化算法
  • 3.5.1　算法
  • 3.5.2　算法分析

---

第4章　切尔诺夫界与霍夫丁界

• 4.1　矩母函数
• 4.2　切尔诺夫界的导出和应用
  • 4.2.1　泊松试验和的切尔诺夫界
  • 4.2.2　例：投掷硬币
  • 4.2.3　应用：估计参数
• 4.3　某些特殊情况下更好的界
• 4.4　应用：集合的均衡
• 4.5　霍夫丁界
• 4.6　应用：稀疏网络中的数据包路由选择
  • 4.6.1　超立方体网络上排列的路由选择
  • 4.6.2　蝶形网络上排列的路由选择

第5章　球、箱子和随机图

• 5.1　例：生日悖论
• 5.2　球放进箱子
  • 5.2.1　球和箱子模型
  • 5.2.2　应用：桶排序
• 5.3　泊松分布
• 5.4　泊松近似
• 5.5　应用：散列法
  • 5.5.1　链散列
  • 5.5.2　散列：二进制数字串
  • 5.5.3　Bloom过滤器
  • 5.5.4　放弃对称性
• 5.6　随机图
  • 5.6.1　随机图模型
  • 5.6.2　应用：随机图中的哈密顿圈
• 5.8　探索性作业

第6章　概率方法

• 6.1　基本计数论证
• 6.2　期望论证
  • 6.2.1　应用：求最大割
  • 6.2.2　应用：最大可满足性
• 6.3　利用条件期望消除随机化
• 6.4　抽样和修改
  • 6.4.1　应用：独立集合
  • 6.4.2　应用：有较大围长的图
• 6.5　二阶矩方法
• 6.6　条件期望不等式
• 6.7　洛瓦兹局部引理
  • 6.7.1　应用：边不相交的路径
  • 6.7.2　应用：可满足性
• 6.8　利用洛瓦兹局部引理的显式构造
• 6.9　洛瓦兹局部引理：一般情况
• 6.10　洛瓦兹算法局部引理

第7章　马尔可夫链及随机游动

• 7.1　马尔可夫链：定义及表示
  • 7.1.1　应用：2可满足性的随机化算法
  • 7.1.2　应用：3可满足性的随机化算法
• 7.2　状态分类
• 7.3　平稳分布
• 7.4　无向图上的随机游动
• 7.5　Parrondo悖论

---

第8章　连续分布与泊松过程

• 8.1　连续随机变量
  • 8.1.1　R中的概率分布
  • 8.1.2　联合分布与条件概率
• 8.2　均匀分布
• 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.3　M/M/∞排队中的顾客数

第9章　正态分布

• 9.1　正态分布
  • 9.1.1　标准正态分布
  • 9.1.2　一般单变量正态分布
  • 9.1.3　矩母函数
• 9.2　二项分布的极限
• 9.3　中心极限定理
• 9.4　多维正态分布
• 9.5　应用：生成正态分布的随机值
• 9.6　最大似然点估计
• 9.7　应用：针对混合高斯分布的EM算法

第10章　熵、随机性和信息

• 10.1　熵函数
• 10.2　熵和二项式系数
• 10.3　熵：随机性的测度
• 10.4　压缩
• 10.5　编码：香农定理

第11章　蒙特卡罗方法

• 11.1　蒙特卡罗方法
• 11.2　应用：DNF计数问题
  • 11.2.1　朴素算法
  • 11.2.2　DNF计数问题的完全多项式随机方案
• 11.3　从近似抽样到近似计数
• 11.4　马尔可夫链蒙特卡罗方法
• 11.6　最小支撑树的探索作业

第12章　马尔可夫链的耦合

• 12.1　变异距离和混合时间
• 12.2　耦合
  • 12.2.1　例：洗牌
  • 12.2.2　例:超立方体上的随机游动
  • 12.2.3　例：固定大小的独立集合
• 12.3　应用：变异距离是不增的
• 12.4　几何收敛
• 12.5　应用：正常着色法的近似抽样
• 12.6　路径耦合

第13章　鞅

• 13.1　鞅
• 13.2　停时
• 13.3　瓦尔德等式
• 13.4　鞅的尾部不等式
• 13.5　Azuma-Hoeffding不等式的应用
  • 13.5.1　一般形式
  • 13.5.2　应用：模式匹配
  • 13.5.3　应用：球和箱子
  • 13.5.4　应用：色数

第14章　样本复杂度、VC维度以及拉德马赫复杂度

• 14.1　“学习”问题
• 14.2　VC维度
  • 14.2.1　VC维度的其他例子
  • 14.2.2　增长函数
  • 14.2.3　VC维度的合成界
  • 14.2.4　ε-网和ε-样本
• 14.3　ε-网定理
• 14.4　应用：PAC学习
• 14.5　ε-样本定理
  • 14.5.1　应用：不可知学习
  • 14.5.2　应用：数据挖掘
• 14.6　拉德马赫复杂度
  • 14.6.1　拉德马赫复杂度和样本错误
  • 14.6.2　估计拉德马赫复杂度
  • 14.6.3　应用：二值分类的不可知学习

第15章　两两独立及通用散列函数

• 15.1　两两独立
  • 15.1.1　例：两两独立的二进制数字的构造
  • 15.1.2　应用：消去最大割算法的随机性
  • 15.1.3　例：构造关于一个素数模的两两独立的值
• 15.2　两两独立变量的切比雪夫不等式
• 15.3　通用散列函数族
  • 15.3.1　例：一个2维通用散列函数族
  • 15.3.2　例：强2维通用散列函数族
  • 15.3.3　应用：完美散列
• 15.4　应用：在数据流中寻找重量级的源终点

第16章　幂律及相关的分布

• 16.1　幂律分布：基本定义和性质
• 16.2　语言中的幂律
  • 16.2.1　Zipf定律和其他例子
  • 16.2.2　语言优化
  • 16.2.3　猴子随意打字
• 16.3　偏好链接
• 16.4　幂律在算法分析中的应用
• 16.5　其他相关的分布
  • 16.5.1　对数正态分布
  • 16.5.2　具有指数截断的幂律

第17章　平衡分配和布谷鸟散列

• 17.1　两种选择的影响力
• 17.2　两种选择：下界
• 17.3　两种选择影响力的应用
  • 17.3.1　散列法
  • 17.3.2　动态资源分配
• 17.4　布谷鸟散列
• 17.5　布谷鸟散列的扩展
  • 17.5.1　带删除的布谷鸟散列
  • 17.5.2　处理故障
  • 17.5.3　更多的选择和更大的箱子

---