概率与计算
2007
机械工业出版社
米曾马克
294
史道齐
无
本书详细地介绍了概率技术以及在概率算法与分析发展中使用过的范例。本书分两部分，第一部分介绍了随机抽样、期望、马尔可夫不等式、切比雪夫不等式、切尔诺夫界、球和箱子模型、概率技术和马尔可夫链等核心内容。第二部分主要研究连续概率、有限独立性的应用、熵、马尔可夫链蒙特卡罗方法、耦合、鞅和平衡配置等比较高深的课题。 本书适合作为高等院校计算机科学和应用数学专业高年级本科生与低年级研究生的教材，也适合作为数学工作者和科技人员的参考书。
Michael Mitzenmacher 1996年于加州大学伯克利分校获得博士学位，现为哈佛大学计算机科学教授。在1999年进入哈佛大学之前，他是Palo Alto数字系统研究实验室的研究人员。他曾获美国科学基金（NSF）CAAREER奖和Alfred P. Sloan研究基金。2002年，由于在纠错码方面的出色工作，他获得了IEEE信息论学会的“最佳论文”奖。
译者序前言第1章 事件与概率1.1 应用：验证多项式恒等式1.2 概率论公理1.3 应用：验证矩阵乘法1.4 应用：最小割随机化算法练习第2章 离散随机变量与期望2.1 随机变量与期望2.2 伯努利随机变量和二项随机变量2.3 条件期望2.4 几何分布2.5 应用：快速排序的期望运行时间练习第3章 矩与离差3.1 马尔可夫不等式3.2 随机变量的方差和矩3.3 切比雪夫不等式3.4 应用：计算中位数的随机化算法练习第4章 切尔诺夫界4.1 矩母函数4.2 切尔诺夫界的导出和应用4.3 某些特殊情况下更好的界4.4 应用：集合的均衡4.5 应用：稀疏网络中的数据包路由选择练习第5章 球、箱子和随机图5.1 例：生日悖论5.2 球和箱子模型5.3 泊松分布5.4 泊松近似5.5 应用：散列法5.6 随机图练习探索性作业第6章 概率方法6.1 基本计数论证6.2 期望论证6.3 利用条件期望消除随机化6.4 抽样和修改6.5 二阶矩方法6.6 条件期望不等式6.7 洛瓦兹局部引理6.8 利用洛瓦兹局部引理的显式构造6.9 洛瓦兹局部引理：一般情况练习第7章 马尔可夫链及随机游动7.1 马尔可夫链：定义及表示7.2 状态分类7.3 平稳分布7.4 无向图上的随机游动7.5 Parrondo悖论练习第8章 连续分布与泊松过程8.1 连续随机变量8.2 均匀分布8.3 指数分布8.4 泊松过程8.5 连续时间马尔可夫过程8.6 例：马尔可夫排队论练习第9章 熵、随机性和信息9.1 熵函数9.2 熵和二项式系数9.3 熵：随机性的测度9.4 压缩9.5 编码：香农定理练习第10章 蒙特卡罗方法10.1 蒙特卡罗方法10.2 应用：DNF计数问题10.3 从近似抽样到近似计数10.4 马尔可夫链蒙特卡罗方法练习最小支撑树的探索性作业第11章 马尔可夫链的耦合11.1 变异距离和混合时间11.2 耦合11.3 应用：变异距离是不增的11.4 几何收敛11.5 应用：正常着色法的近似抽样11.6 路径耦合练习第12章 鞅12.1 鞅12.2 停时12.3 瓦尔德方程12.4 鞅的尾部不等式12.5 Azuma?Hoeffding不等式的应用练习第13章 两两独立及通用散列函数13.1 两两独立13.2 两两独立变量的切比雪夫不等式13.3 通用散列函数族13.4 应用：在数据流中寻找重量级的源终点练习第14章 平衡配置14.1 两种选择的影响力14.2 两种选择：下界14.3 两种选择影响力的应用练习进一步阅读材料索引
无