概率与计算
2020-09-23 本文已影响0人
潮汐潮汐
本文首发在我的博客：《概率与计算》
这是一个挖坑贴，随机算法是大数据算法中的重要的算法，《概率与计算》是讲随机算法的书中风评比较好的，此外还有一本《数学女孩-随机算法》。这本书比较偏理论，但是有很多算法领域的例子及其对应的随机算法和概率分析，有部分习题需要编程解决。刷完这本书的工程量比较大，这里先看下这本书里都有什么内容。
《概率与计算：算法与数据分析中的随机化和概率技术》 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 应用：快速排序的期望运行时间
- 2.1 随机变量与期望
- 第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悖论
- 7.1 马尔可夫链：定义及表示
- 第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/∞排队中的顾客数
- 8.1 连续随机变量
- 第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算法
- 9.1 正态分布
- 第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 应用：在数据流中寻找重量级的源终点
- 15.1 两两独立
- 第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 更多的选择和更大的箱子
