大偏差技術是什麼？

01-05

知乎上居然有這麼冷門的問題，本人研究過一段時間大偏差，在這裡試著回答一下，估計也不會有什麼人看..

1月20日更新

答了好久，沒人看所以一直沒更新。今天竟然看到這麼多人關注，又有了寫下去的動力。大家的
評論我看了，確實有幾個地方搞錯了。都做了修改，去掉了莫明其妙的f，用熟悉的大O表示，另外中等偏差概念有誤，重新定義，感謝指出。我的目的是盡量初等的說明問題，不去考慮開閉1集，希爾伯特空間等概念。

1月21日

moderate 翻譯成中等偏差自己想了一下還是不準確，似乎翻譯成緩慢偏差更准一下。因為是描述速率的，還在考慮中。

大偏差是概率論里比較難學的一個分支，國內估計搞得人少，不知道會不會有人看到這個回答。

由於大偏差理論涉及高等概率論，拉普拉斯變換，以及實變函數和泛函分析較為深入的內容，所以在這個小小的答題空間里將這一理論解釋清楚，是一件很難的事，下面盡量用初等數學的方法，說明什麼是大偏差，再將理論的主要內容做一簡單列舉。

首先說明什麼是偏差

我們從最簡單的隨機序列，伯努力序列講起：

伯努力序列定義為

${xi_1,xi_2,ldots,xi_n}$ , 其中每個 $xi_i$ 都是隨機變數且

$P{xi_i=1}=p;P{xi_i=0}=q=1-p$

下面考慮伯努力序列的前n項和，定義

$S_k=xi_1+cdots+xi_k; 0leq kleq n$

顯然 $S_n$ 表示前n次試驗總的成功次數。可以證明

$E{S_n/n}=p$

即成功的頻率的平均值等於成功的概率p，由於上式只是概率等式，所以一個自然考慮的量就是 $S_n/n$ 與p之間的偏差 $|S_n/n -p|$ 。偏差兩字就是這麼來的。

偏差理論，就是對上面絕對值公式進行估計。

估計的方法就是即對任意 $epsilon$ ，估計不等式 $|S_n/n-p|leq epsilon$ 成立的概率。

對於伯努力序列，只要n足夠大，偏差可以很小。即大部分實驗結果都落在

$|S_n/n-p|leq epsilon$ 成立地範圍內，屬於常見現象

大偏差理論反其道而行之，研究 $|S_n/n-p|geq epsilon$ 的概率，這屬於稀有事件，所以也可以說大偏差是研究稀有事件的理論。

1 當理論估計的是

$|S_n -np|geq O(sqrt{n})$

成立的概率時，即成功次數與np之間的差距為O( $sqrt{n}$ )量級，稱為標準偏差理論，

2 量級達到n時,研究

$|S_n-np|geq O(n)$

或更高量級成立的概率，稱為大偏差理論。

下面。我們來推導伯努力序列的大偏差公式

伯努力序列的大偏差相關公式並不是大偏差定理，也不是大偏差定律，可以簡單的看成的大偏差定理的特別簡單的例子。廢話說完。繼續更新

a 伯努力序列的大偏差公式組：

由於要估計的是概率不等式，第一個想到著名的切比雪夫不等式

$P(Xgeq epsilon)leq frac{EX^2}{epsilon^2}$

但問題是大偏差估計的是指數量級，這個不等式只是線性級別的。不要緊，將其變成指數形式

即可

$P(xgeq epsilon)=P(e^{lambda x}geq e^{lambdaepsilon})leq E{e^{lambda(x-epsilon)}}$

因為上式對任何 $lambda$ &>0都成立，所以可以改寫為：

$P(xgeq epsilon)leq inf_{lambda>0}E{e^{lambda(x-epsilon )}}$

得到上面這個有用的公式後，我們可以討論伯努力序列了，回憶一下

$X=S_n/n,S_n=xi _1+xi_2 +cdots +xi_n ,P(xi_i=1)=p_i ,P(xi_i=0)=q_i$

從而

$e^{lambda S_n }=[e^{lambda xi_1}]^n$

上式根據獨立性得到

在 $e^{lambda xi_1}$ 中將 $lambda$ 看作變數，記成函數形式為 $varphi (lambda)=1-p+e^lambda$

所以，對於0&

$P(xgeq a)leq inf_{lambda>0}E{e^{lambda(S_n/n-a )}}=\inf_{lambda>0}e^{-n[alambda/n -lnvarphi(lambda /n)]}=<br /> inf_{lambda>0}e^{-n[as -lnvarphi(s)]}=\<br /> e^{-nsup_{s>0} [as -lnvarphi(s)]}$

說明： $sup_{s>0} [as -lnvarphi(s)]$ 是著名的Legendre-Fenchel變換，在凸函數以及極大代數等冪等數學中發揮重要作用，描述了被變換的函數離正比例函數的最大距離。

因為 $as -lnvarphi(s)=as -ln(1-p+pe^lambda)$ 是a的函數，記

$sup_{s>0}{as-lnvarphi (s)}=H(a)$

這裡就體現出大偏差的牛逼了，經過簡單計算，H(a)可以表達如下

$H(a)=aln(frac{a}{p})+(1-a)ln(frac{1-a}{1-p})$

這正是 $xi$ 的熵的公式。

到這裡，Legendre-Fenchel變換，熵，以及概率論得到了有機的結合。這正是大偏差理論精華所在！！
所以，我們對a和p的值進行討論後可以得到如下一組不等式
$pleq aleq 1,,P(S_n/ngeq a)leq e^{-nH(a)},\ a=p+epsilon,P(S_n/n-pgeq epsilon)leq e^{-2nepsilon^2}\ aleq pleq 1,,P(S_n/nleq a)leq e^{-nH(a)},\ a=p-epsilon,P(S_n/n-pleq -epsilon)leq e^{-2nepsilon^2}\$
以上可以總結為
$P(|S_n/n-p|geq epsilon) leq 2e^{-2nepsilon^2}$

以上5個公式都叫做伯努力序列中關於大偏差概率的不等式，

說明
1 如果不進行指數化，直接用切比雪夫多項式估計，可以得到不等式
$P(|S_n/n-p|leq epsilon) geq 1-pq/nepsilon^2$
這是一個相當粗略的結果
2切比雪夫是比較粗糙的估計方法，可以用更為精細的棣美佛-拉普拉斯公式估計伯努力序列標準偏差；
$P(aleq frac{S_n-np}{sqrt{npq}}leq b)sim frac{1}{2pi}int_a^b e^{-x^2/2}dx$
這也是推導大數定律和正態分布的方法之一

3 中偏差MDP(moderate derviation principle)定義如下：

設 $mu_n$ 滿足LDP，其速度為 $gamma_n^2$ ,且

$lim_{n o infty}frac{gamma_n}{sqrt{n}}=0 ; and;lim_{n oinfty}gamma_n=infty$ 則稱 $mu_n$ 滿足MDP

b然後用列舉式的方法簡單說明大偏差理論。這樣和那些教材區別也不大，大家盡量對照第一部分來看。本文的目的是盡量用初等的語言說明大偏差的內容，所以這裡單純列舉，所有內容都可以在

參考書中找到。

先做幾點說明

1 克拉默條件是說 $P(|xi|geq x)$ 的以指數速度下降。

（待續）

c最後推薦一些教程，複雜簡單都有

1中文的可參見大偏差理論與方法，作者高付清。只看到這麼一本

不過語言無所謂，反正公式比字多。。。中英文真心差距不大

2 國外的，專門研究可參見樓下答主這本大偏差三部曲之1

這是國際通用的研究生教材，不過比較厚。

3 LARGE DEVIATIONS AND IDEMPOTENT PROBABILITY ANATOLII PUHALSKII

因為大偏差和冪等數學天然親戚關係，所以專門發展出了建立在冪等數學上的測度論進而概率，適合進一步興趣，但是很枯燥，喪心病狂的500頁。。。

4 Large Deviations for Stochastic Processes

Jin Feng

Thomas G. Kurtz

Department of Mathematics and Statistics, University of Massachusetts

大偏差三部曲之2，也有400多頁，非專業莫入

5 Large Deviations Jean-Dominique Deuschel Department of Mathematics

大偏差三部曲之3.頁數最少，329頁。我就是用這本，主要是論文要用，不得已而已。

以上書都可以全面了解大偏差，如果你的目的只是興趣或了解，請看下面列表

1 Some Applications and Methods of Large Deviations in Finance and Insurance

Huyên Pham

金融中的應用，一點都不複雜，而且照著著實際講，很好理解，入門必備

2 An Introduction to Large Deviations for Teletraffic Engineers

入門書，非常簡單，敘述過程和我差不多，先初等推導，有了認識後列舉高等結論

3Large deviations theory: a basic tutorial. R. Toral

只有7頁！非常簡明的說明，需要一點基礎，也就是一點點。

4 Elements of Statistical Mechanics and Large Deviation Theory

40頁。比較流行的讀物。和熵的關係講得多一些。

5The large deviation approach to statistical mechanics

Hugo Touchette

又是力學，why，LDP最早就是在統計力學中用的，作者是3部曲第三部作者

6 Large Deviation Principles

Spring 2010

Scott Robertson

37 頁。很經典，而起是2010年的。內容也較新所有這些參考資料，網上可以直接下載！google書名即可
最後是施利亞耶夫的概率論，大偏差的內容散見於各章，本答案主要推導來自該書。

預定的內容都寫完了，如果以後再有什麼心得，也會繼續更新。不過近期是沒時間繼續學大偏差了。

主要的參考文獻是 Amir Dembo, Ofer Zeitouni 的 Large Deviations Techniques and Applications和Richard Ellis 的 Entropy, Large Deviations, and Statistical Mechanics。兩本書都有世界圖書出版公司的影印版，不過共同特點是風格比較純數，上手略困難。

1 大偏差的引入

考慮一個簡單的遊戲：擲一枚均勻的硬幣，正面朝上乙給甲一塊錢，反面朝上甲給乙一塊錢。設n次之後，甲的收益為 $S_n$ . 甲每次的收益期望為0，即 $mathbb{E}(S_n/n)=0$ .

由弱大數律（Law of large numbers）可知，對於0的任何一個小鄰域 $(-epsilon,+epsilon)$ ，當n越來越大，每次收益期望越有可能落入這個區間， $lim_{n oinfty}mathbb{P}(|S_n/n|<epsilon)= 1$ .

現在我們反過來考慮上述事件的補，即每次收益期望遠離0. 不妨考慮極端事件： $S_n/n=1$ ,甲每次都能贏。顯然這個事件的概率是 $2^{-n}$ ，以指數速度下降。數學形式是 $frac{1}{n}logmathbb{P}(S_n/n=1)=-log2$ .

由中心極限定理（Central limit theorem）可知， $S_n/sqrt{n}$ 依分布收斂於一個正態分布。粗略來說 $S_n$ 大概是 $sqrt{n}$ 量級。而大偏差理論（Large deviations theory）研究的是 $S_n$ 處在n量級的概率（大偏差）如何以指數速度下降。

2 大偏差函數

對於上面的擲硬幣模型，定義大偏差函數

$I(z)=frac{1+z}{2}log(1+z)+frac{1-z}{2}log(1-z)$ ，如果 $-1le zle1$ .如果 $|z|>1$ ，規定 $I(z)=infty$ . 規定 $0log0=0$ .

這個函數長這樣

在 $pm 1$ 處取到最大值 $log 2$ ，在0處取到最小值0.

這個函數描述了事件 $S_n/napprox z$ 在n增大時的指數衰減速度，比如 $-frac{1}{n}logmathbb{P}(S_n/napprox1) o log2=I(1)$

$-frac{1}{n}logmathbb{P}(S_n/napprox0) o 0=I(0)$

可以看出，|z|越大， $S_n/napprox z$ 的概率下降得越快。考慮 $S_n/n$ 落在區間[0.3,0.7]的概率。如果你學過一點Laplace積分的近似理論的話，就會知道 $S_n/n$ 落在0.7附近的概率，相比於落在0.3附近的概率，是下降得指數快的，所以對於落在區間[0.3,0.7]的概率來說，0.7附近的貢獻越來越小，最終整個區間的概率可以被0.3附近概率代替。所以 $-frac{1}{n}logmathbb{P}(0.3le S_n/nle0.7) o I(0.3)$

實際上， $S_n/n$ 處於某個Borel集（比如開集、閉集）的概率由這個集合上大偏差函數I的最小值（下確界）確定。

3 （好的）大偏差理論的嚴格表述

由於這是個科普文章，我只表述比較簡潔的（好的）大偏差原理。

考慮 $mathbb{R}$ 或者 $mathbb{R}^n$ 上的一列概率分布 $mu_n$ ，一個（好的）大偏差函數I(z)，以及 $mathbb{R}$ 或者 $mathbb{R}^n$ 中的任意Borel集 $Gamma$ （可以只考慮開集或閉集），有

$lim_{n oinfty}frac{1}{n}logmu_n(Gamma)=-inf_{zinGamma}I(z)$

則稱概率分布序列 ${mu_n}$ 滿足關於大偏差函數I(z)的大偏差律。（狹義的）好的大偏差函數應當連續非負，只在一個點（大數律所指的那個點）取到極小值0. 一般的（不好的）大偏差函數不連續，會導致上面的極限不存在，但上下極限存在，其上下界是上式的右端的 $Gamma$ 被 $Gamma$ 的內部和閉包替換。

對於上面的擲硬幣模型， $mu_n$ 是 $S_n/n$ 在[-1,1]上的分布， $Gamma$ 可以取區間[0.3,0.7]. 那麼 $mu_n(Gamma)$ 就是

$mathbb{P}(0.3le S_n/nle0.7)$ 。

所以 $-frac{1}{n}logmathbb{P}(0.3le S_n/nle0.7) o inf_{zin [0.3,0.7]} I(z)=I(0.3)$

對於獨立同分布( i.i.d.)，在 $mathbb{R}$ 或者 $mathbb{R}^n$ 中取值，取值可能有限的序列， $S_n/n$ 都滿足大偏差律。證明就是簡單地做一下組合數的估計。

以下就不打算以科普為目的了，主要是讀書筆記和個人的想法。

4 大偏差與大數律和中心極限定理的關係

當上面的集合 $Gamma$ 不包含I(z)的極小值點的時候，落在其中的概率以指數速度下降趨於0，那麼其補集的概率趨於1. 這正是弱大數律。由於事件 $R_N=$ ${sup_{n<N}S_n/n>mu+epsilon}$ ( $mu$ 是期望， $epsilon$ 是任意正數)的概率隨N指數下降，所以所有 $R_N$ 的和有限。由第一Borel-Cantelli lemma (Borel)，上述事件無窮次發生（亦即強大數律不成立）的概率為零。這樣就證明了強大數律。

以下假設I(z)的零點是0. 當大偏差函數I(z)二階連續可導的時候，在其零點附近做泰勒展開到二階項， $I(z)approx I$ . 所以 $S_n/n$ 落在z附近的概率大概是 $ce^{-nI$ . 而 $S_n/sqrt{n}$ 落在z附近的概率就是 $ce^{-I$ . 這就是中心極限定理。

反過來，如果序列滿足中心極限定理，把上一段的論述反過來，就知道 $S_n/n$ 以指數速度下降，即大偏差原理。

注意這兩段只是個形象的說明，不是嚴格證明。

5 不同Level的大偏差原理

考慮一列隨機變數，取值空間是 $mathbb{R}$ 或者 $mathbb{R}^n$ ，但只能取有限個值（比如骰子的六個面123456）。

Level 1的大偏差說的是 $S_n/n$ 屬於某個（不包含期望那個點的）集合的概率指數下降，我們之前一直在講這種大偏差。

Level 2的大偏差是說我們進一步考慮n次之後各種可能的取值發生的頻率。比如擲了一百次骰子，六個面的頻率分別是0.20,0.14,0.11,0.22,0.16,0.17. 這是『骰子的六個面』這個空間上的一個概率測度（經驗測度 empirical measure）。我們知道這個空間上有個不變測度（各面都是1/6），由強大數律，上述經驗測度會收斂於不變測度。這個空間上的所有概率測度是一個度量空間（距離由全變差距離定義）。Level 2的大偏差就是說經驗測度屬於某個不包含不變測度的集合的概率以指數速度下降。我們會在所有概率測度的空間上定義出大偏差函數。

Level 3 的大偏差進一步考慮每條軌道的具體性質。（Level 2 只考慮軌道的累積性質，對前有限項交換順序不影響結果。但Level 3 有影響。）對於一條軌道 $omega$ ，取其前n項，然後無限重複，補成一條周期序列 $X(n,omega)$ = $(cdots X_1(omega),X_2(omega),cdots ,X_n(omega),X_1(omega),X_2(omega),cdots ,X_n(omega),cdots)$ 。這叫做經驗過程(empirical process). 經驗過程對每個n和 $omega$ 有一個對應的（在軌道空間上的）測度

$R_n(omega,cdot)=frac{1}{n}sum_{k=0}^{n-1}delta_{T^k X(n,omega)}(cdot)$ 這個測度是嚴平穩的。

比如一條軌道 $omega_0$ 的1,2,3項是a,b,c，經驗過程 $X(3,omega_0)$ =(...abcabcabc...). 考慮一個有限柱集(finite cylinder set) A= { $omega:X_1(omega)=a,X_2(omega)=b$ }，那麼對應的測度就是 $R_3(omega_0, A)$ =

$frac{1}{3}sum_{k=0}^{2}delta_{T^k X(3,omega_0)}(A)$ = $frac{1}{3}$ .

現在考慮N個有限柱集 $Sigma_k$ ，以及軌道空間的平穩分布 $P_{ ho}$ . （ $ho$ 是狀態空間的一個概率分布， $P_{ ho}$ 是 $ho$ 對應的乘積測度）每一條軌道 $omega$ 對應了一個測度 $R_n(omega,cdot)$ ，而 $P_{ ho}$ 是軌道的測度，所以也是所有（對固定的n） $R_n$ 的測度，記作 $Q_n^{(3)}$ 。

考慮一個不包含 $P_{ ho}$ 的軌道空間的嚴平穩測度的集合，比如 $B_3={P: max |P(Sigma_k)-P_{ ho}(Sigma_k)|geepsilon}$ 。這個集合里的 $Q_n^{(3)}$ 測度是隨n指數下降的。

以上稱作Level 3 大偏差。

Level 3 大偏差我理解得不太深刻，暫時只能寫成這樣了。

6 大偏差原理擴展到非獨立同分布序列

對於不可約馬氏鏈，上述Level 1和Level 2的大偏差都成立。Level 1的大偏差是對狀態空間上的任意函數做的。

前面兩位提到的主要是基於長時間平均的大偏差，不管是獨立同分布多次重複也好，還是非獨立同分布的變數（比如馬氏過程）的長時間平均也好，還是所謂的level 2 large deviation也好，都是這一類的。大概看了一下覺得沒什麼需要補充的。當然我也不是專業搞大偏差的，需要用的時候翻翻書而已。

想補充一下的是還有一類大偏差問題是基於弱雜訊的大偏差，基本想法是有一個確定性的過程，比如說一個常微分方程和一點弱的擾動，然後這個弱的擾動在很小的概率下會讓常微分方程的軌跡產生很大的偏離，然後我們想估計產生這種很大的偏離的概率。雖然本質上講兩類問題是一樣的，沒記錯的話Zeitouni的書裡面就有一章，所謂的sample path large deviation，可以拿來應用到這種弱隨機擾動的大偏差上來。但是如果想真正做這方面問題的話，個人建議是從Freidlin-Wentzell的那本書開始學。

剛剛終於對large deviation principle 有了intuitive的理解，找個地方寫下來。

大致講的就是對decay rate的精細控制，直覺上，I(x) 就是落在x附近的概率在指數下降時的速度。剛開始最讓我不解的是inf I(x)，為什麼要取inf呢，後來理解了，因為其實最後這些rare event都會聚集在「窪點」（自造詞）上（他們怎麼發生呢？都是在窪點附近發生）。用劉慈欣《三體》中的一個句子作為註腳吧：

海乾了魚就要聚集在水窪里。

大偏差理論就是幫助人類了解世界上奇葩的事到底有多奇葩。