第一章 概率论基本知识 1
1.1 预备知识 1
1.1.1 概率空间 1
1.1.2 随机变量 3
1.1.3 矩、特征函数与分布 4
1.1.4 随机变量在概率空间上的实现问题 9
1.2 随机变量序列的各种收敛性 11
1.2.1 依概率收敛 11
1.2.2 a.s.收敛 11
1.2.3 平均收敛 13
1.2.4 依分布收敛 17
1.2.5 各种收敛性之间的关系 18
1.2.6 连续性定理 18
1.3 经典极限理论中的有关结果 19
1.3.1 大数律 19
1.3.2 中心极限定理 23
1.3.3 渐近正态的收敛速度估计 26
1.4 鞅 29
1.4.1 条件数学期望 29
1.4.2 鞅与相关的概念 30
1.4.3 鞅足标的随机化 34
1.4.4 基本不等式 40
1.4.5 下鞅和鞅收敛的基本定理 45
1.4.6 鞅的大数律和中心极限定理 51
1.5 三大积分变换 57
1.5.1 Fourier积分公式 58
1.5.2 Fourier变换、Laplace变换与它们的逆变换 60
1.5.3 Mellin变换 61
第二章 随机结构 68
2.1 图论中的基本概念 68
2.1.1 图的概念与表示 68
2.1.2 树的概念 73
2.2 随机图论 74
2.2.1 经典随机图论 74
2.2.2 随机网络 76
2.2.3 随机树 78
2.3 两类典型的随机递归结构 78
2.3.1 组合随机递归结构 78
2.3.2 连续参数随机递归结构 80
2.4 与数据搜索有关的随机递归结构举例 82
2.4.1 Quickselect 82
2.4.2 聚类合并（Mergesort） 83
2.4.3 索回树（Tries） 83
2.5 随机m叉搜索树 85
2.5.1 随机m叉搜索树的概念 85
2.5.2 随机二叉搜索树的子树 86
2.5.3 随机二叉搜索树上的顶点数目 87
2.5.4 随机二叉搜索树上随机顶点的深度 88
2.6 均匀递归树 89
2.6.1 均匀递归树的概念 89
2.6.2 均匀递归树的分支数目 91
2.6.3 均匀递归树上顶点n的深度 94
2.6.4 均匀递归树中的路径总长 96
2.6.5 均匀递归树最大分支 98
第三章 概率距离 100
3.1 概率距离的一般性理论 100
3.1.1 从函数空间中的距离谈起 100
3.1.2 一般度量空间中的概率距离 103
3.1.3 复杂距离与简单距离 108
?4.6 极限方程退化的情形 183
4.6.1 问题的由来 183
4.6.2 单一分支退化情形，渐近正态 184
4.6.3 一些应用 191
4.6.4 多分支退化情形 194
4.7 连续参数情形 199
4.7.1 参数连续情形下的一般性压缩定理 200
4.7.2 连续参数下的中心极限定理 203
4.7.3 周期变化情形下的有关结果 206
4.8 关于分割树上顶点数目的讨论 211
4.8.1 N（x）的期望与方差 211
4.8.2 N（x）的中心极限定理 226
4.8.3 适用于本节结论的一些例子 229
4.8.4 不适用于本节结论的一些例子 233
第五章 Pólya罐模型 235
5.1 模型简介 235
5.2 只含两种颜色球的Pólya罐 236
5.2.1 Pólya－Eggenberger罐 236
5.2.2 Bernard Friedman罐 238
5.2.3 Bagchi－Pal罐 239
5.2.4 Ehrenfest罐 244
5.3 Pólya过程 244
5.3.1 Poisson化 244
5.3.2 反Poisson化 253
5.4 极限性质 258
5.5 广义Pólya罐模型 268
5.6 在随机树中的应用 275
5.6.1 随机二叉搜索树 275
5.6.2 m叉搜索树 277
5.6.3 均匀递归树 280
第六章 生成函数 287
6.1 单变量生成函数 287
6.1.1 普通单变量生成函数的定义与性质 287
6.1.2 指数型生成函数的定义与性质 291
6.1.3 单变量生成函数的应用举例：Catalan数 292
6.1.4 生成函数的系数 295
6.2 双变量生成函数 298
6.2.1 应用示例：有显式情形 299
6.2.2 应用示例：无显式情形 306
6.3 概率生成函数 309
6.3.1 概率生成函数的定义与性质 309
6.3.2 概率生成函数的应用举例 311
6.4 生成函数在随机结构中的若干应用 315
6.4.1 均匀递归树的最大分支和最小分支 315
6.4.2 m叉随机搜索树上的不成功搜索 327
第七章 经典方法在随机结构研究中的若干应用 338
7.1 组合概率方法：关于均匀递归树上的分支数目研究 338
7.1.1 ζn，1的分布律和极限分布 338
7.1.2 一般情形 340
7.1.3 ζn，m的联合分布 343
7.1.4 ζn，m联合分布的极限分布 345
7.2 组合概率方法：关于Yule树的研究 348
7.3 独立和方法：关于均匀递归树上的顶点间距离研究 352
7.3.1 关于均匀递归树上顶点间距离研究的背景介绍 352
7.3.2 均匀递归树上顶点间距离的大数律 353
7.3.3 均匀递归树上顶点间距离的中心极限定理 354
7.4 矩方法 361
7.5 鞅方法 368
7.5.1 均匀递归树的路径总长 368
7.5.2 Barabási-Albert随机树的最大顶点度数 370
7.6 Stein方法 375
7.6.1 正态逼近 375
7.6.2 Poisson逼近 380
参考文献 385
索引 392