本書為國內關于隨機結構極限理論方面的首本著作，將在簡略介紹概率論與經典極限理論基本內容的基礎上，介紹一些典型的隨機結構以及概率距離理論，并逐一剖析在隨機結構研究中最為廣泛使用的壓縮法，它們都是現行隨機結構研究領域中最為重要的方法，作者結合近年來國內外最新的研究成果和文獻，形象生動地講述了這些方法的具體應用技巧，盡量使讀者能夠很快地熟悉并掌握這些方法。
通常將極限理論、隨機過程和隨機分析稱為概率論的三大分支。
極限理論的基礎理論框架最早形成于20世紀40、50年代。此前只有關于極限定理的一些零星結果，無窮可分分布理論的形成是極限理論理論體系框架建成的標志，其主要結果是在Ko1mogorov的公理化體系形成之后的二三十年問形成的。Gne-denko和Ko1mogorov的專著《相互獨立隨機變量之和的極限定理》是經典極限理論發(fā)展歷程中具有里程碑意義的代表作。
經典極限理論的研究對象是隨機變量序列的部分和sn的各種極限性狀。在那里，大數律、中心極限定理和重對數律都是關于sn的，并且最早幾乎都是關于獨立隨機變量序列的部分和的，后來由于實際的需求，各種相依序列也逐漸應運而生。鞅序列概念的產生，拓寬了經典極限理論的研究內容，也為概率論向數學其他分支的滲透提供了工具。
近代的極限理論則著眼于全面考察隨機變量序列的部分和序列sn的極限性狀，典型的研究內容是關于s1，s2，…，sn所形成的部分和過程向布朗運動的強、弱收斂性。更進一步的內容則是關于各種隨機過程，包括鞅過程中的極限定理的研究。其基本標志是：盡管所研究的課題具有不同的背景需求，但是所用的工具卻基本上屬于概率論自身的范疇，包括測度論和積分論。
計算機科學技術的迅速發(fā)展，不但為社會經濟和科學技術的發(fā)展提供了有力的工具和廣闊的平臺，也為現代自然科學的發(fā)展帶來了機遇，同時也提出了新的挑戰(zhàn)。計算機科學的進步，離不開算法理論的發(fā)展，算法理論的發(fā)展催生了隨機圖論這一新興學科。隨機圖論迅速地突破了原有的經典框架，衍生出隨機網絡和隨機樹兩大新生分支。
序
第一章 概率論基本知識
1.1 預備知識
1.1.1 概率空間
1.1.2 隨機變量
1.1.3 矩、特征函數與分布
1.1.4 隨機變量在概率空間上的實現問題
1.2 隨機變量序列的各種收斂性
1.2.1 依概率收斂
1.2.2 a.s.收斂
1.2.3 平均收斂
1.2.4 依分布收斂
1.2.5 各種收斂性之間的關系
1.2.6 連續(xù)性定理
1.3 經典極限理論中的有關結果
1.3.1 大數律
1.3.2 中心極限定理
1.3.3 漸近正態(tài)的收斂速度估計
1.4 鞅
1.4.1 條件數學期望
1.4.2 鞅與相關的概念
1.4.3 鞅足標的隨機化
1.4.4 基本不等式
1.4.5 下鞅和鞅收斂的基本定理
1.4.6 鞅的大數律和中心極限定理
1.5 三大積分變換
1.5.1 Foreier積分公式
1.5.2 Fourier變換、Laplace變換與它們的逆變換
1.5.3 Mellin變換
第二章 隨機結構
2.1 圖論中的基本概念
2.1.1 圖的概念與表示
2.1.2 樹的概念
2.2 隨機圖論
2.2.1 經典隨機圖論
2.2.2 隨機網絡
2.2.3 隨機樹
2.3 兩類典型的隨機遞歸結構
2.3.1 組合隨機遞歸結構
2.3.2 連續(xù)參數隨機遞歸結構
2.4 與數據搜索有關的隨機遞歸結構舉例
2.4.1 Quickselect
2.4.2 聚類合并（Mergesort）
2.4.3 索回樹（Tries）
2.5 隨機m叉搜索樹
2.5.1 隨機m叉搜索樹的概念
2.5.2 隨機二叉搜索樹的子樹
2.5.3 隨機二叉搜索樹上的頂點數目
2.5.4 隨機二叉搜索樹上隨機頂點的深度
2.6 均勻遞歸樹
2.6.1 均勻遞歸樹的概念
2.6.2 均勻遞歸樹的分支數目
2.6.3 均勻遞歸樹上頂點n的深度
2.6.4 均勻遞歸樹中的路徑總長
2.6.5 均勻遞歸樹最大分支
第三章 概率距離
3.1 概率距離的一般性理論
3.1.1 從函數空間中的距離談起
3.1.2 一般度量空間中的概率距離
3.1.3 復雜距離與簡單距離
3.1.4 復雜距離的最小化
3.1.5 理想距離
3.2 lr距離
3.2.1 lr距離的定義
3.2.2 lr距離的性質
3.2.3 lr距離的收斂性
3.3 Zolotarev距離
3.3.1 Zolotarev距離的定義
3.3.2 Zolotarev距離的基本性質
3.3.3 Zolotarev距離的收斂性
3.3.4 Zolotarev距離的Lp版本
3.4 距離的光滑化
3.4.1 一致密度距離的光滑化
3.4.2 全變差距離的光滑化
3.4.3 其他光滑化距離
第四章 壓縮法
4.1 壓縮法的最初形式
4.1.1 利用遞歸方程計算特征數字
4.1.2 Rosler方法的基本思想
4.1.3 不動點原理
4.1.4 收斂到不動點
4.2 正態(tài)逼近與距離選擇問題
4.2.1 關于距離的選用問題
4.2.2 正態(tài)逼近問題中的距離選擇
4.2.3 正態(tài)分布的若干刻畫定理
4.3 運用Zolotarev距離的例子與啟示
4.3.1 隨機二叉搜索樹的子樹數目
4.3.2 一些啟示
4.4 壓縮法的一般形式
4.4.1 遞歸問題的一般性提法
4.4.2 壓縮映射與不動點性質
4.4.3 收斂定理
4.4.4 K為依賴于n的隨機變量的情形
4.5 壓縮收斂定理在組合結構中的應用
4.5.1 組合結構中的壓縮收斂定理
4.5.2 轉移定理的應用：非漸近正態(tài)情形
4.5.3 中心極限定理（推論5.1）的應用
4.6 極限方程退化的情形
4.6.1 問題的由來
4.6.2 單一分支退化情形，漸近正態(tài)
4.6.3 一些應用
4.6.4 多分支退化情形
4.7 連續(xù)參數情形
4.7.1 參數連續(xù)情形下的一般性壓縮定理
4.7.2 連續(xù)參數下的中心極限定理
4.7.3 周期變化情形下的有關結果
4.8 關于分割樹上頂點數目的討論
4.8.1 N（x）的期望與方差
4.8.2 N（x）的中心極限定理
4.8.3 適用于本節(jié)結論的一些例子
4.8.4 不適用于本節(jié)結論的一些例子
第五章 Polya罐模型
5.1 模型簡介
5.2 只含兩種顏色球的Polya罐
5.2.1 Polya-Eggenberger罐
5.2.2 BernardFriedman罐
5.2.3 Bagchi-Pal罐
5.2.4 Ehrenfest罐
5.3 Polya過程
5.3.1 Poisson化
5.3.2 反Poisson化
5.4 極限性質
5.5 廣義Polya罐模型
5.6 在隨機樹中的應用
5.6.1 隨機二又搜索樹
5.6.2 m叉搜索樹
5.6.3 均勻遞歸樹
第六章 生成函數
6.1 單變量生成函數
6.1.1 普通單變量生成函數的定義與性質
6.1.2 指數型生成函數的定義與性質
6.1.3 單變量生成函數的應用舉例：Catalan數
6.1.4 生成函數的系數
6.2 雙變量生成函數
6.2.1 應用示例：有顯式情形
6.2.2 應用示例：無顯式情形
6.3 概率生成函數
6.3.1 概率生成函數的定義號陛質
6.3.2 概率生成函數的應用舉例
6.4 生成函數在隨機結構中的若干應用
6.4.1 均勻遞歸樹的最大分支和最小分支
6.4.2 m叉隨機搜索樹上的不成功搜索
第七章 經典方法在隨機結構研究中的若干應用
7.1 組合概率方法：關于均勻遞歸樹上的分支數目研究
7.1.1 ζn，1的分布律和極限分布
7.1.2 一般情形
7.1.3 ζn，m的聯合分布
7.1.4 ζn，m聯合分布的極限分布
7.2 組合概率方法：關于Yule樹的研究
7.3 獨立和方法：關于均勻遞歸樹上的頂點間距離研究
7.3.1 關于均勻遞歸樹上頂點間距離研究的背景介紹
7.3.2 均勻遞歸樹上頂點間距離的大數律
7.3.3 均勻遞歸樹上頂點間距離的中心極限定理
7.4 矩方法
7.5 鞅方法
7.5.1 均勻遞歸樹的路徑總長
7.5.2 Barabasi-Albert隨機樹的最大頂點度數
7.6 Stein方法
7.6.1 正態(tài)逼近
7.6.2 Poisson逼近
參考文獻
索引
書單推薦
