劉應興的部落格

統計上一個廣為人知的不等式；柴必雪夫 (Chebyshev) 不等式，說：遠離數值資料中心（平均值） k 倍標準差之外的資料，占總資料數不超過 1/k^2；以機率來表示，

P[|X-E[X]| > a] ≦ E[(X-E[X])^2]/a^2

式中 a = k √ E[(X-E[X])^2] 則右邊是 1/k^2。此不等式暗指：以平均數代表一個資料分布的中心是有道理的，因為離此中心太遠的資料「並不多」。

此不等式若論及創始者，應稱 Bienaymé–Chebyshev 不等式，因為最早提出並給予證明的是 Pafnuty Chebyshev 的朋友兼同事  Irénée-Jules Bienaymé，後者在 1853 年首先給了證明；1867 年Chebyshev 才發表了他的證明；1884 其學生 Andrey Markov 給予另一個證明。不過，事實上，Johann Carl Friedrich Gauss 早在 1821 就提出一個單峰連續型分布的雙尾機率不等式

P[|X-m| > a] ≦  (4/9)τ^2/a^2,    當  a > 2τ/√3;
                    ≦  1-(1/√3)a/τ},      當  0 < a ≦ 2τ/√3.

其中 m 是 X 的眾數，τ^2 = E[(X-m)^2]。

證明 Chebyshev 不等式很簡單，

E[(X-E[X])^2] = ∫ (X-E[X])^2 dP ≧ ∫_[|X-E[X]| > a] (X-E[X])^2 dP
                      ≧ a^2 ∫_[|X-E[X]| > a]  dP = a^2 P[|X-E[X]| > a]

這證明方法和 Markov 不等式相同：

E[|X|] = ∫ |X| dP ≧ ∫_[|X| > a] |X| dP ≧ a ∫_[|X| > a] dP = a P[|X| > a]
故 P[|X| > a] ≦ E[|X|]/a

由於 Chebyshev 不等式等於是 Markov 不等式的變形，因此也被歸為 Markov 不等式；也有人把後者稱為 Chebyshev 第一不等式，而普通的 Chebyshev 不等式則犒之為 Chebyshev 第二不等式。

有時候我們需要的是 P[X > a] 的上限，其中 a > μ = E[X]。由於 Chebyshev 不等式對任意分布均適用，因此對於單尾機率，我們也只能說

P[X-μ > a] ≦ P[|X-μ| > a] ≦ E[(X-μ)^2]/a^2 = σ^2/a^2

其中 a > 0，挨言之，單尾事件 [X-μ > a] 與雙尾事件 [|X-μ| > a] 共用一個機率上限 σ^2/a^2,除非 X 的分布對稱於 μ，此時

P[X-μ > a] ＝(1/2) P[|X-μ| > a] ≦ (1/2) E[(X-μ)^2]/a^2 = (1/2) σ^2/a^2

不過，從 Markov 不等式來想，取 t ≧ 0，

P[X-μ > a] = P[X-μ+t > a+t ] ≦ P[(X-μ+t)^2 > (a+t)^2]
                ≦ (σ^2 + t^2)/(a+t)^2

上列不等式右邊在 t = σ^2/a 時得最小值 σ^2/(a^2+σ^2)，這個不等式同樣適用於任何（存在二階動差的）分布，但其機率上限明顯比原來的 Chebyshev 不等式上限 σ^2/a^2 小一些，這就是單邊 Chebyshev 不等式，也稱 Cantelli 不等式，或 Chebyshev-Cantelli 不等式，是 Francesco Paolo Cantelli 於 1910 提出。

Chebyshev 不等式的問題可以看成是在限制條件

∫ f_i dP = λ_i, i = 1, ..., k

之下求 ∫ g dP 之極值的問題，其中 P 可為任意機率測度，諸 f_i 及 g 均為可測實數值函數。若沒有任何限制，只要求 P 是可測空間 (Ω, F) 上的機率測度，則目標積分式最大值是

v* = max{g(ω): ω in Ω},= g(ω*),   P{ω*} = 1,

即最大值發生於 P 為單點機率時，而機率集中處是 g 函數最大值所在。當有限制條件 ∫ f_i( dP = λ_i, 時，即是對可選擇的 P 有了相應的限制。令 P 是所有滿足條件的機率分布 P 構成的集合，則 P 是一個凸集合，意指苦 P, Q 是 P 的任意兩元素，0 < α < 1, 則 αP + (1-α)Q 也在 P 中。另方面，目標積分對 P 而言是線性的。在凸集合上求線性函數的極值，必然發生在頂點：

若 S 是一凸集合，函數 T(u), u in S 是線性的，則 T(u) 的極值發生在 S 的「頂點」。

注意我們的限制條件 ∫ f_i( dP = λ_i, 也都是在 P 上的線性限制式。就像在 R^n 中的線性規劃問題，目標函數和陋制條件都是線性的，結果最適解就存在於由限制條件所構成的凸多面體諸頂點之中。在除了要求 P 是機率測度之外別無限制時，P 的頂點都是單點分布，P{ω} = 1 for some ω in Ω，所以我們可以在單點分布中尋找使 ∫ g dP = g(ω) 最大的 ω；當多了額外限制時，一個限制條件使得 P 的頂點由兩點分布構成

P = α <ω> + (1-α) <ω'>,    0 < α < 1

式中符號 <ω> 表示 P{ω} = 1 的機率分布。以 Markov 不等式為例，Ω　取 R, 隨機變數 X(ω) = ω, 則相當於我們要解

Maximize ∫ I_[|X| ≧ a] dP,
 such that  ∫ |X| dP = ν

結果可我其解為

P = p <0> + (1-p) <a>
 p = 1 - ν/a

或即 P[|X| = 0] = ν/a = 1 - P[|X| = a]。對於 Chebyshev 不等式，則是

Maximize ∫ I_[|X－μ| ≧ a] dP,
 such that  ∫ X dP = μ
                 ∫ X^2 dP = μ^2 + σ^2

不失一般性可設 μ = 0，考慮三點分布 P = p <ω> + q <ω'> + (1-p-q) <ω">。代入條件得

p = (σ^2 + ω' ω")/[(ω-ω')(ω-ω")]
q = (σ^2 + ω ω")/[(ω'-ω)(ω'-ω")]
r = 1-p-q = (σ^2 + ω ω')/[(ω"-ω)(ω"-ω')]

假設 ω < ω' < ω"，則應有 σ^2 + ω ω" < 0,，所以 ω ω" < 0 且其絕對值超過 σ^2；另一方面 σ^2 + ω ω' 及 σ^2 + ω' ω" 都是正值，ω' 比較接近 0。分析 ω, ω', ω" 對 p, q, r 的作用（偏導數），得：

p 極大化： P = σ^2/(a^2 + σ^2) <-a> + a^2/(a^2 + σ^2) <σ^2/a>;
r 極大化： P = a^2/(a^2 + σ^2) <-σ^2/a> + σ^2/(a^2 + σ^2) <a>;
q 極小化： P = σ^2/(2a) <-a> + (1-σ^2/a^2) <0> + σ^2/(2a) <a>

其中 q 極小化即 p+r 之極大化，即 P[|X-μ| ≧ a] 之最大可能值，即 Chebyshev 不等式兩尾機率之上限；而 p 或 r 個別之極大化分別是單尾 P[X ≦ μ-a] 與 P[X ≧ μ+a] 之最大可能值，即單邊 Chebyshev 不等式之上限。注意上列 q 極小化需要 a > σ。

我們可把單峰分布 P 表示為一些均勻分布的混合 (mixture)，不失一般性，假設眾數 m 為 0，U(b) 為區間 [b, 0] 或 [0, b] 上的均勻分布，Q 是 R 上任一機率分布，則

P = ∫_R U(b) dQ{b}  (Lebesgue 積分）

是一個單峰分布；反過來說，一個單峰分布 P 可以表示為諸 U(b) 分布混合而成，即：存在 Q 使 P 可如上表示。因此，所有單峰分布的集合 P 可以寫成

P = {P: 存在 Q in Q 使 P = ∫_R U(b) dQ{b}}

式中 Q 是在 R 上的任意分布，因此 P 的頂點就是某個 U(b)。設 X 是服從某個 U(b)，則

P[|X| > a] = 1 - a/|b|   當 a ≦ |b|

而對 U(b) 分布而言，τ^2 = E[|X|}^2] = b^2/3, 所以

P[|X| > a] = 1 - a/(√3 τ),  當 0 < a ≦ √3 τ

但既有 τ^2 = E[|X|}^2] 的設定，也就是說 P 需要滿足此一條件，則 Q 應考慮兩點分布，即 P 是兩個均勻分布的混合

P = p U(b) + (1-p) U(b'),   0 ≦ p ≦ 1

由於考慮的都是與眾數 m = 0 之間的離差，因此假設 m 在最左邊無妨，所以，不妨假設 0 < b < b'；又，a ＜b'，否則 P[|X| > a] = 0。

若 0 < a ≦ b, 則 P[|X| > a] = 1 - p(a/b) - (1-p) (a/b');
茄 b < a < b', 則 P[|X| > a] = (1-p) (1 - a/b').

而 p 和 b, b' 符合 p b^2 + (1-p) b'^2 = 3 τ^2。結果前者機率極大值發生在 b = b'，即單一均勻分布的情形；後者則極值發生在

P = [1 - (4/3)(τ^2/a^2)] U(0) + (4/3)(τ^2/a^2) U((3/2)a)

分布 U(0) 是退化成單點質量，P[U = 0] = 1 的「均勻」分布，U((3/2)a) 是在 [0, (3/2)a)] 的均勻分布。此時 P[|X| > a] = (4/9)(τ^2/a^2)；另外，它必須在

(4/3)(τ^2/a^2) < 1,  即  a > (2/√3) τ

才有意義.因此，證明了 Gauss 不等式。

由以上求機率極值的方法可知：不論是 Chebyshev 不等式，Markov 不等式，或 Gauss 不等式，它們都是銳利的，意即不等式所揭示的邊界可以達到；但另一方面，它們也是寬鬆的，通常很難用於估計真實機率，例如對常態分布：

    a       正確雙尾機率  Chebyshev 上限      Gauss 上限
   2σ         0.0455     1/4 = 0.26       1/9 = 0.1111
   3σ         0.0027     1/9 = 0.111     4/81 = 0.0494

即使 Gauss 不等式的雙尾機率上限，與正確機率相差也很大。因此，以機率計算的觀點，Chebyshev 不等式用途很有限。其所以如此，是因不等式適用範圍太廣，不論任何分布都適用；Gauss 不等式把適用範圍限制在單峰連續型分布，對 Chebyshev 的機率界限有顯著改善，但究機率估算用途來說，其實意義仍十分有限。事實上，Chebyshev 不等式的作用在隨機變數序列收斂問題上更有發揮餘地，例如：

設 X_n, n = 1, 2, ..., n, ... 為相互獨立同分布，具二階動差，之隨機變數序列，Sn = Σ_{k=1~n} Xk，則
　　　Y_n = (S_n)/n  →  E[X_1]  in probability

[證] 令 μ = E[X_1], σ^2 = Var(X_1)，則 Var(Y_n) = σ^2/n, 故
　　    P[|Y_n - μ| > ε] ≦ Var(Y_n)/ε^2 = σ^2/(n ε^2) → 0
　　故 Y_n 向 μ 做機率收斂。　 ▌

事實上 Chebyshev 不等式也可用於證明強大數法則，即只要 X_n 的共同均值 μ = E[X_1] 存在，則上述樣本平均數 Y_n 以機率 1 向 μ 收斂。

關於獨立隨機變數和 S_n 序列，我們可以有一個更強的結果：

[定理]  (Kolmogorov 不等式，又稱極大不等式，maximal inequality)
設 X_n, n = 1, 2, ... 相互獨立且各具期望值 0 及有限變異數，則
　　P[max_k |S_k| > a] ≦ Var(S_n)/a^2

[證] 令 E 代表事件 [max_k |S_k| > a]，又令
　　     A_k = [max_{j < k} |S_j| ≦ a,  |S_k| > a]
即 A_k 是第一個超過 a 的部分和絕對值 |S_k| 是第 k 個的事件，則顯然
　　　E = ∪_{k = 1~n} A_k
故
　   E[Sn^2] ≧ Σ_{k=1~n] ∫_{A_k} S_n^2 dP
                   ≧ Σ_{k=1~n] ∫_{A_k} [S_k^2 + 2S_k(S_n-S_k)] dP
                   = Σ_{k=1~n] ∫_{A_k} a^2 dP
                   ≧ a^2 ∫_E dP = a^2 P[max_k |S_k| > a]
▌

上述證明中間的等式是因 ∫_{A_k} S_k(S_n-S_k) dP = 0，何故？
  　　 ∫_{A_k} S_k(S_n-S_k) dP = ∫ I_{A_l} S_k (S_n-S_k) dP
                 = ∫ I_{A_k} S_k (S_n-S_k) dP 
                 =  ∫ I_{A_k} S_k dP ∫ (S_n-S_k) dP
                 = 0 
以上諸等式，首先是將限制在 A_k 的積分利用指示函數擴展成在整個樣本空間 Ω 的積分。由於 A_k 以致其指示函數是 σ(X_1,...,X_k)-可測，S_k 也是，因為它們都是由 X_1,...,X_k 決定的；另一方面 S_n-S_k 是 σ(X_{k+1},...,X_n)-可測，所以 I_{A_k} S_k 與 S_n-S_k 相互獨立，對 P 的積分可以分別做。但由於諸 X_i 期望值為 0，故 S_n-S_k 期望值亦是 0。　

有上列定理，我們可以證明：若具相互獨立項的隨機級數部分和的變異數收斂，則此隨機級數以機率 1 收斂：

[定理] 設 X_1, ..., X_n, ... 為各具期望值 0 及有限變異數，相互獨立的隨機變數序列；又令 S_n = Σ_{k=1~n} X_k。若 Var(S_n) 收斂，則 S_n 以機率 1 收斂

[證] 證明定理之前，首先我們回憶一下機率 1 收斂的意義。我們說 X_n 向 X 做機率 1 收斂，意思是
        P{ ∩_k ∪_N ∩_{n≧N} [|Xn-X|<1/k]  } = 1
 上式 P{．} 符號內就是 X_n(ω) → X(ω) 的所有 ω 所形成的集合。但上式相當於
        P{ ∪_N ∩_{n≧N} [|Xn-X|<1/k]  } = 1  for all k
 而由‵機率的「連績性」，這又相當於
        P{  ∩_{n≧N} [|Xn-X|<1/k]  } → 1   當 N → ∞,  for all k
 但 ∩_{n≧N} [|Xn-X|<1/k] = [sup_{n≧N} |Xn-X| < 1/k]。所以 X_n 向 X 做機率 1 收斂相當於
        sup_{n≧N} |Xn-X| 向 0 做機率收斂。
 回到原問題，S_n 向某隨機變數做機率 1 收斂的條件是序列 { S_n } 以機率 1 符合 Cauchy 準則
       P[ S_{n+k} - Sn → 0 當 n → ∞ ] = 1,  for all k
 依前述機率 1 收斂的等價條件，即
       P[ Sup_{n > N} | S_{n+k} - Sn | > ε ] → 0 當  N → ∞
但應用 Kolmogorov（極大）不等式，
       P[ Sup_{n = N+1 ～ N+r} | S_{n+k} - Sn | > ε ]
            ≦ P[ Sup_{n= N+1～N+r} (|S_{n+k}-S_N| + |S_{n}-S_N|) > ε ]
            ≦ P[ Sup_{n= N+1～N+r} |S_{n+k}-S_N|
                           + Sup_{n= N+1～N+r} |S_n-S_N|) > ε ]
            ≦ P[Sup_{n= N+1～N+r} |S_{n+k}-S_N| > ε/2]
                           + P[Sup_{n= N+1～N+r} |S_n-S_N|) > ε/2]
            ≦ P[Sup_{n= N+1～N+k+r} |S_n-S_N| > ε/2]
                          + P[Sup_{n= N+1～N+r} |S_n-S_N|) > ε/2]
            ≦ Var(S_{N+k+r}-S_N)/(ε/2)^2 + Var(S_{N+r}-S_N)/(ε/2)^2
由於 Var(S_{N+r}-S_N) = Σ_{j=N+1～N+r} Var(X_j)，令 r → ∞，則得
     P[ Sup_{n > N} | S_{n+k} - Sn | > ε ] ≦ 8 Σ_{n>N} Var(X_n)/ε^2
但 Var(S_n) = Σ_{j=1～n} Var(X_j),收斂，故
       P[ Sup_{n > N} | S_{n+k} - Sn | > ε ] → 0,  當 N → ∞,
對任意 k 都成立。也就是說：序列 S_n 以機率 1 滿足 Cauchy 收斂條件，所以 S_n 以機率 1 收斂。　▌