概率与计算

本文首发在我的博客：《概率与计算》

---

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

---

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

概率与计算

---

第一部分：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　更多的选择和更大的箱子