本书的内容安排基于作者的博士学位论文。在南京大学的博士研究生阶段，作者的研究方向是理论计算机科学，主要研究课题是随机采样算法。本书收录了作者在博士研究生期间的研究成果，同时也涵盖了此领域的若干基础知识。 采样是理论计算机科学的一个基本问题。本书既研究了采样领域的经典问题，也针对大数据背景下出现的新问题提出了新的技术和原理，给出了适用于分布式计算模型的局部采样算法、适用于动态数据的动态采样算法以及若干经典问题的近线性时间采样算法。 本书的适读人群为计算机或数学领域的高年级本科生、研究生、高校教师和科研人员。

第1部分 绪论与预备知识
第1章 绪论
1.1 研究背景
1.2 研究问题
1.3 主要成果
1.4 本书结构与章节安排
第2章 吉布斯分布与预备知识
2.1 吉布斯分布
2.1.1 概率图模型
2.1.2 自旋系统与具体模型
2.2 采样与近似计数
2.3 马尔可夫链
2.3.1 基本概念
2.3.2 马尔可夫链蒙特卡洛方法
2.3.3 混合时间分析工具
第2部分 分布式采样
第3章 分布式采样总览
3.1 分布式计算与LOCAL模型
3.2 分布式采样与分布式计数
3.3 分布式采样部分章节安排
第4章 分布式采样算法
4.1 问题定义
4.2 局部梅特罗波利斯算法
4.2.1 算法与主要结论
4.2.2 局部梅特罗波利斯算法的平稳分布
4.2.3 局部梅特罗波利斯算法的混合时间
4.3 梅特罗波利斯算法的分布式模拟
4.3.1 主要结论
4.3.2 模拟算法
4.3.3 算法分析
4.4 本章小结
第5章 分布式采样复杂性
5.1 分布式采样下界
5.2 分布式JerrumValiantVazirani（JVV）定理
5.2.1 基本定义
5.2.2 近似采样和近似推断之间的归约
5.2.3 分布式JVV采样算法
5.3 强空间混合性质与分布式采样/计数
5.4 本章小结
第3部分 动态采样
第6章 动态采样总览
6.1 研究背景
6.2 问题定义
6.3 主要结论
第7章 条件吉布斯采样技术
7.1 局部拒绝采样算法
7.2 精确吉布斯采样算法
7.3 正确性分析
7.3.1 均衡条件
7.3.2 局部拒绝采样算法均衡条件验证
7.3.3 精确吉布斯采样算法均衡条件验证
7.3.4 推广版算法
7.4 收敛性分析
7.4.1 局部拒绝采样算法收敛性分析
7.4.2 精确吉布斯采样算法收敛性分析
7.5 本章小结
第8章 动态马尔可夫链技术
8.1 动态吉布斯采样算法
8.1.1 动态自旋系统上马尔可夫链的耦合
8.1.2 动态马尔可夫链的数据结构
8.1.3 动态吉布斯采样算法分析
8.2 动态马尔可夫链在推断问题上的应用
8.2.1 支持多参数更新的动态马尔可夫链
8.2.2 算法的实现与分析
8.3 本章小结
第4部分 快速采样算法
第9章 洛瓦兹局部引理采样问题
9.1 研究背景
9.2 主要结论
9.3 基本定义与背景知识
9.4 采样算法
9.4.1 CNF公式满足解采样算法
9.4.2 状态压缩技术
9.4.3 一般约束满足问题采样算法
9.5 算法分析
9.5.1 主定理证明
9.5.2 投影策略的构造
9.5.3 InvSample子程序分析
9.5.4 混合时间分析
9.6 局部引理问题实例的近似计数
9.7 本章小结
第10章 谱独立性与混合时间
10.1 研究背景
10.2 主要结论
10.2.1 谱独立性与吉布斯采样算法混合时间
10.2.2 图染色模型上的应用
10.3 混合时间分析
10.3.1 主定理证明
10.3.2 局部随机游走的耦合
10.4 图染色模型的谱独立性
10.4.1 一般性定理的证明
10.4.2 边缘概率上界分析
10.4.3 边缘概率上界分析的紧致性
10.5 本章小结
致谢
参考文献
附录 文中部分专业名词中英翻译对照表
攻读博士学位期间的科研成果
攻读博士学位期间参与的科研课题