現代極限理論及其在隨機結構中的應用

現代科學的發展對概率論提出了越來越高的要求。經典的極限理論以研究隨機變數序列部分和序列的極限性狀為己任，近代極限理論則主要研究部分和過程向布朗運動的強弱逼近。然而，隨著概率論與其他學科的交叉，所產生出的許多複雜的隨機結構，遠遠不是用“部分和”就可以刻畫得了的。不同的隨機結構來自於迥異的領域，相差甚遠，對其中的概率問題的研究遠非傳統方法能夠勝任。自20世紀90年代以來，隨著對複雜隨機結構中隨機變數極限性狀的研究逐步開展，湧現出許多全新的理論和方法，也深化和發展了一些原有的理論。這些理論與方法目前還只散見於各種學術刊物，雖然已有不少綜述性的文章介紹其中的一些理論與方法，但是仍然缺乏一本較為全面系統介紹它們的著作。

本書便是產生於這樣的背景之下。

本書作為國內關於隨機結構極限理論方面的首本著作，將在簡略介紹概率論與經典極限理論基本內容的基礎上，介紹一些典型的隨機結構以及概率距離理論，並逐一剖析在隨機結構研究中最為廣泛使用的壓縮法、Polya罐方法、生成函數法、矩方法、Stein方法等，它們都是現行隨機結構研究領域中最為重要的方法。作者結合近年來國內外最新的研究成果和文獻，形象生動地講述了這些方法的具體應用技巧，盡量使讀者能夠很快地熟悉並掌握這些方法。可以說，本書是開啟隨機結構研究領域大門的一把很好的鑰匙。

本書包含了隨機結構中的眾多研究方法和實例，內容系統全面，可供相關專業的教師、學生以及研究人員使用參考。

序

第一章　概率論基本知識

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連續性定理

1.3　經典極限理論中的有關結果

1.3.1大數律

1.3.2　中心極限定理

1.3.3　漸近正態的收斂速度估計

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　連續參數隨機遞歸結構

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　正態逼近與距離選擇問題

4.2.1　關於距離的選用問題

4.2.2　正態逼近問題中的距離選擇

4.2.3　正態分佈的若干刻畫定理

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　轉移定理的應用：非漸近正態情形

4.5.3　中心極限定理(推論5.1)的應用

4.6　極限方程退化的情形

4.6.1　問題的由來

4.6.2　單一分支退化情形，漸近正態

4.6.3　一些應用

4.6.4　多分支退化情形

4.7　連續參數情形

4.7.1　參數連續情形下的一般性壓縮定理

4.7.2　連續參數下的中心極限定理

4.7.3　周期變化情形下的有關結果

4.8　關於分割樹上頂點數目的討論

4.8.1　N(x)的期望與方差

4.8.2　N(x)的中心極限定理

4.8.3　適用於本節結論的一些例子

4.8.4　不適用於本節結論的一些例子

第五章　Polya罐模型

5.1　模型簡介

5.2　只含兩種顏色球的Polya罐

5.2.1　Polya-Eggenberger罐

5.2.2　Bernard Friedman罐

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　正態逼近

7.6.2　Poisson逼近

參考文獻

索引

書評：關於隨機結構中的極限理論一直以來都沒有一本著作，幾年前就想能不能有這方面的著作出來，現在終於有了。本書可以說是及時雨，填補了這方面的空白，對隨機結構中的極限理論研究是很大的貢獻。仔細閱讀本書，會發現作者為本書傾注了很大的心血。本書從最基本的知識出發，娓娓道來，帶你進入隨機結構的領域，詳細闡述了研究隨機結構尤其是研究隨機樹的最重要方法，象壓縮法，廣義Ploya罐模型，生成函數等等，這些都是研究隨機結構的新方法，在展示這些方法的時候作者還介紹這些方法的來龍去脈，讀來受益匪淺。本書行文流暢清晰，對一些概念的闡述讀來深受啟發，是一本值得珍藏而常讀的著作。