動機
獨立指示變量之和記錄了重複隨機試驗中的成功次數。其期望值給出了一個有用的中心位置,但本身並不能說明較大偏離出現的可能性有多小。馬爾可夫(Markov)不等式利用期望值為非負隨機變量設界;直接把它用於成功次數,得到的結果往往很弱。這裏的關鍵想法是對和的指數函數應用馬爾可夫不等式。獨立性隨後把乘積的期望化為期望的乘積,從而得到隨指數下降的尾界。
即使各指示變量的成功概率互不相同,這些界仍然有用。它們是上界,而不是精確概率,並且獨立性假設在其中起著實質作用。我們先推導精確的表達式,再給出便於使用的簡化形式和具體的樣本量估計。
定義
設 X 1 , … , X n X_1,\dots,X_n X 1 , … , X n 為獨立的伯努利(Bernoulli)變量,其中 Pr ( X i = 1 ) = p i \Pr(X_i=1)=p_i Pr ( X i = 1 ) = p i ,Pr ( X i = 0 ) = 1 − p i \Pr(X_i=0)=1-p_i Pr ( X i = 0 ) = 1 − p i 。令 X = ∑ i X i X=\sum\limits_i X_i X = i ∑ X i ,μ = E [ X ] = ∑ i p i \mu=\mathbb E[X]=\sum\limits_i p_i μ = E [ X ] = i ∑ p i 。這些變量不必同分佈。對於 δ > 0 \delta>0 δ > 0 ,乘性上尾 是事件 X ≥ ( 1 + δ ) μ X\ge(1+\delta)\mu X ≥ ( 1 + δ ) μ ;對於 0 < δ < 1 0<\delta<1 0 < δ < 1 ,乘性下尾 是事件 X ≤ ( 1 − δ ) μ X\le(1-\delta)\mu X ≤ ( 1 − δ ) μ 。儘管 X X X 取整數值,這些閾值仍是實數;不等式按通常的含義理解。
對於 λ ∈ R \lambda\in\mathbb R λ ∈ R ,矩母函數表達式為 E [ e λ X ] \mathbb E[e^{\lambda X}] E [ e λ X ] 。由於 0 ≤ X ≤ n 0\le X\le n 0 ≤ X ≤ n ,這裏所有的期望都是有限的。結果在 μ > 0 \mu>0 μ > 0 時才有意義;若 μ = 0 \mu=0 μ = 0 ,則所有 p i = 0 p_i=0 p i = 0 ,X = 0 X=0 X = 0 幾乎必然成立,因此乘性偏離需要另行詮釋。
定理
對於均值之和為 μ > 0 \mu>0 μ > 0 的獨立伯努利變量,以及 δ > 0 \delta>0 δ > 0 ,
Pr ( X ≥ ( 1 + δ ) μ ) ≤ ( e δ ( 1 + δ ) 1 + δ ) μ . \Pr(X\ge(1+\delta)\mu)\le\left(\frac{e^\delta}{(1+\delta)^{1+\delta}}\right)^\mu. Pr ( X ≥ ( 1 + δ ) μ ) ≤ ( ( 1 + δ ) 1 + δ e δ ) μ . 對於 0 < δ < 1 0<\delta<1 0 < δ < 1 ,
Pr ( X ≤ ( 1 − δ ) μ ) ≤ ( e − δ ( 1 − δ ) 1 − δ ) μ . \Pr(X\le(1-\delta)\mu)\le\left(\frac{e^{-\delta}}{(1-\delta)^{1-\delta}}\right)^\mu. Pr ( X ≤ ( 1 − δ ) μ ) ≤ ( ( 1 − δ ) 1 − δ e − δ ) μ .
在相同假設下,對於 0 < δ ≤ 1 0<\delta\le1 0 < δ ≤ 1 ,
Pr ( X ≥ ( 1 + δ ) μ ) ≤ e − μ δ 2 / 3 , Pr ( X ≤ ( 1 − δ ) μ ) ≤ e − μ δ 2 / 2 . \Pr(X\ge(1+\delta)\mu)\le e^{-\mu\delta^2/3},\qquad
\Pr(X\le(1-\delta)\mu)\le e^{-\mu\delta^2/2}. Pr ( X ≥ ( 1 + δ ) μ ) ≤ e − μ δ 2 /3 , Pr ( X ≤ ( 1 − δ ) μ ) ≤ e − μ δ 2 /2 . 因此,對於 0 < δ < 1 0<\delta<1 0 < δ < 1 ,有 Pr ( ∣ X − μ ∣ ≥ δ μ ) ≤ 2 e − μ δ 2 / 3 \Pr(|X-\mu|\ge\delta\mu)\le2e^{-\mu\delta^2/3} Pr ( ∣ X − μ ∣ ≥ δ μ ) ≤ 2 e − μ δ 2 /3 。
證明思路或證明
對任意實數 λ \lambda λ ,由獨立性及 1 + y ≤ e y 1+y\le e^y 1 + y ≤ e y 得
E [ e λ X ] = ∏ i ( 1 − p i + p i e λ ) ≤ exp ( μ ( e λ − 1 ) ) . \mathbb E[e^{\lambda X}]=\prod_i(1-p_i+p_i e^\lambda)
\le\exp\bigl(\mu(e^\lambda-1)\bigr). E [ e λ X ] = i ∏ ( 1 − p i + p i e λ ) ≤ exp ( μ ( e λ − 1 ) ) . 對於 λ > 0 \lambda>0 λ > 0 ,對 e λ X e^{\lambda X} e λ X 應用馬爾可夫不等式,得
Pr ( X ≥ ( 1 + δ ) μ ) ≤ exp ( μ ( e λ − 1 ) − λ ( 1 + δ ) μ ) . \Pr(X\ge(1+\delta)\mu)\le
\exp\bigl(\mu(e^\lambda-1)-\lambda(1+\delta)\mu\bigr). Pr ( X ≥ ( 1 + δ ) μ ) ≤ exp ( μ ( e λ − 1 ) − λ ( 1 + δ ) μ ) . 取 λ = ln ( 1 + δ ) \lambda=\ln(1+\delta) λ = ln ( 1 + δ ) ,即得上尾表達式。這一選擇使上面的指數界最小,因為其指數部分的導數為 μ ( e λ − ( 1 + δ ) ) \mu(e^\lambda-(1+\delta)) μ ( e λ − ( 1 + δ )) ,且二階導數為正。
對於下尾,取 λ < 0 \lambda<0 λ < 0 。取指數會反轉事件的方向:X ≤ ( 1 − δ ) μ X\le(1-\delta)\mu X ≤ ( 1 − δ ) μ 蘊含 e λ X ≥ e λ ( 1 − δ ) μ e^{\lambda X}\ge e^{\lambda(1-\delta)\mu} e λ X ≥ e λ ( 1 − δ ) μ 。再次應用馬爾可夫不等式,得到形式相同、但 λ \lambda λ 為負的表達式。取 λ = ln ( 1 − δ ) \lambda=\ln(1-\delta) λ = ln ( 1 − δ ) ,即得所述的下界。這一反轉至關重要;若在此步使用正的指數,所界定的將是錯誤的事件。
對於簡化的上界,令 h ( δ ) = ( 1 + δ ) ln ( 1 + δ ) − δ − δ 2 / 3 h(\delta)=(1+\delta)\ln(1+\delta)-\delta-\delta^2/3 h ( δ ) = ( 1 + δ ) ln ( 1 + δ ) − δ − δ 2 /3 。則 h ( 0 ) = h ′ ( 0 ) = 0 h(0)=h'(0)=0 h ( 0 ) = h ′ ( 0 ) = 0 ,而 h ′ ′ ( δ ) = 1 / ( 1 + δ ) − 2 / 3 ≥ − 1 / 6 h''(\delta)=1/(1+\delta)-2/3\ge-1/6 h ′′ ( δ ) = 1/ ( 1 + δ ) − 2/3 ≥ − 1/6 並非處處非負,所以僅憑這一觀察不足以證明結論。換一種方式:h ′ ( δ ) = ln ( 1 + δ ) − 2 δ / 3 h'(\delta)=\ln(1+\delta)-2\delta/3 h ′ ( δ ) = ln ( 1 + δ ) − 2 δ /3 在 [ 0 , 1 ] [0,1] [ 0 , 1 ] 上是凹函數,在 0 0 0 處為零,在 1 1 1 處為正(因為 ln 2 > 2 / 3 \ln2>2/3 ln 2 > 2/3 )。凹函數位於其弦的上方,所以 h ′ h' h ′ 在整個區間上 ≥ 0 \ge0 ≥ 0 ,從而 h ≥ 0 h\ge0 h ≥ 0 。為說明 ln 2 > 2 / 3 \ln2>2/3 ln 2 > 2/3 ,在 [ 0 , 1 ] [0,1] [ 0 , 1 ] 上對逐點恆等式 1 / ( 1 + x ) − ( 8 / 9 − 4 x / 9 ) = ( 2 x − 1 ) 2 / [ 9 ( 1 + x ) ] 1/(1+x)-(8/9-4x/9)=(2x-1)^2/[9(1+x)] 1/ ( 1 + x ) − ( 8/9 − 4 x /9 ) = ( 2 x − 1 ) 2 / [ 9 ( 1 + x )] 積分;右邊非負,且除一點外為正,而線性項的積分為 2 / 3 2/3 2/3 。
對於下界,令 g ( δ ) = δ + ( 1 − δ ) ln ( 1 − δ ) − δ 2 / 2 g(\delta)=\delta+(1-\delta)\ln(1-\delta)-\delta^2/2 g ( δ ) = δ + ( 1 − δ ) ln ( 1 − δ ) − δ 2 /2 。此時 g ( 0 ) = g ′ ( 0 ) = 0 g(0)=g'(0)=0 g ( 0 ) = g ′ ( 0 ) = 0 ,且當 0 ≤ δ < 1 0\le\delta<1 0 ≤ δ < 1 時 g ′ ′ ( δ ) = δ / ( 1 − δ ) ≥ 0 g''(\delta)=\delta/(1-\delta)\ge0 g ′′ ( δ ) = δ / ( 1 − δ ) ≥ 0 。因此 g ≥ 0 g\ge0 g ≥ 0 ,由此得到下尾的二次型估計。在端點 δ = 1 \delta=1 δ = 1 ,由獨立性可得 Pr ( X = 0 ) = ∏ i ( 1 − p i ) ≤ e − μ ≤ e − μ / 2 \Pr(X=0)=\prod\limits_i(1-p_i)\le e^{-\mu}\le e^{-\mu/2} Pr ( X = 0 ) = i ∏ ( 1 − p i ) ≤ e − μ ≤ e − μ /2 ,從而完成所述下尾範圍的證明。最後,對上尾事件與下尾事件應用聯集界;這兩個事件之間無需獨立。
證明透視
獨立性在何處起作用 各假設用在哪裏:獨立性恰好只用一次,就是把 E [ e λ X ] \mathbb E[e^{\lambda X}] E [ e λ X ] 寫成乘積 ∏ i ( 1 − p i + p i e λ ) \prod\limits_i(1-p_i+p_ie^\lambda) i ∏ ( 1 − p i + p i e λ ) ;馬爾可夫不等式只需要非負性。關鍵一步是取指數,它把和變成積,並把參數 λ \lambda λ 留作事後再優化的自由量。不等式 1 + y ≤ e y 1+y\le e^y 1 + y ≤ e y 再把每個因子化為 e p i ( e λ − 1 ) e^{p_i(e^\lambda-1)} e p i ( e λ − 1 ) ,於是只剩下 μ \mu μ 。對下尾,取負的 λ \lambda λ 使事件的包含方向反轉。簡化形式靠 [ 0 , 1 ] [0,1] [ 0 , 1 ] 上的微積分比較收尾,所以只在該範圍內陳述。沒有獨立性,分解便不成立,後面「各變量全相同」的反例說明了這一點。
例題詳解
將一枚均勻硬幣擲 100 100 100 次,令 X X X 為正面的次數。則 μ = 50 \mu=50 μ = 50 。取 δ = 0.4 \delta=0.4 δ = 0.4 ,得 Pr ( X ≥ 70 ) ≤ e − 50 ( 0.4 ) 2 / 3 = e − 8 / 3 ≈ 0.0695 \Pr(X\ge70)\le e^{-50(0.4)^2/3}=e^{-8/3}\approx0.0695 Pr ( X ≥ 70 ) ≤ e − 50 ( 0.4 ) 2 /3 = e − 8/3 ≈ 0.0695 。更精細的表達式為 ( e 0.4 / 1.4 1.4 ) 50 ≈ 0.029 (e^{0.4}/1.4^{1.4})^{50}\approx0.029 ( e 0.4 /1. 4 1.4 ) 50 ≈ 0.029 。這兩個數都不是二項分佈的精確概率。
設 200 200 200 次獨立試驗的成功概率均為 0.3 0.3 0.3 ,故 μ = 60 \mu=60 μ = 60 。取 δ = 1 / 2 \delta=1/2 δ = 1/2 ,成功次數至多為 30 30 30 的概率被界定為 e − 60 / 8 = e − 7.5 < 0.00056 e^{-60/8}=e^{-7.5}<0.00056 e − 60/8 = e − 7.5 < 0.00056 。這是對成功次數不足的機會的保證,而不是斷言恰好總有 60 60 60 次成功。
設獨立的伯努利樣本具有共同的未知成功概率 p > 0 p>0 p > 0 ,並以 p ^ = X / n \widehat p=X/n p = X / n 估計它。若已知下界 p ≥ p 0 > 0 p\ge p_0>0 p ≥ p 0 > 0 ,則對於 0 < ε < 1 0<\varepsilon<1 0 < ε < 1 ,由定理得
Pr ( ∣ p ^ − p ∣ ≥ ε p ) ≤ 2 e − n p 0 ε 2 / 3 . \Pr(|\widehat p-p|\ge\varepsilon p)\le2e^{-np_0\varepsilon^2/3}. Pr ( ∣ p − p ∣ ≥ εp ) ≤ 2 e − n p 0 ε 2 /3 . 要使它至多為 α ∈ ( 0 , 1 ) \alpha\in(0,1) α ∈ ( 0 , 1 ) ,只需取 n ≥ 3 ln ( 2 / α ) / ( p 0 ε 2 ) n\ge3\ln(2/\alpha)/(p_0\varepsilon^2) n ≥ 3 ln ( 2/ α ) / ( p 0 ε 2 ) 並向上取整為整數。要事先選定這一相對誤差的樣本量,就需要下界 p 0 p_0 p 0 。
常見錯誤
反例模式
均值相同並不能取代獨立性 設 Y Y Y 為均勻伯努利變量,並取每個 X i = Y X_i=Y X i = Y 。則 μ = n / 2 \mu=n/2 μ = n /2 ,但 Pr ( X = n ) = 1 / 2 \Pr(X=n)=1/2 Pr ( X = n ) = 1/2 。獨立變量情形下 δ = 1 \delta=1 δ = 1 的上界卻隨 n n n 以指數速度趨於零。因此,僅有相同的邊際分佈是不夠的;這裏所有變量是完全相依的。
不要不經換算就把絕對誤差代入相對誤差的界。事件 ∣ X − μ ∣ ≥ a |X-\mu|\ge a ∣ X − μ ∣ ≥ a 只有在 μ > 0 \mu>0 μ > 0 時才對應於 δ = a / μ \delta=a/\mu δ = a / μ ,而上面便於使用的二次型上界還額外假設 δ ≤ 1 \delta\le1 δ ≤ 1 。對於更大的偏離,應使用第一個定理,或另行證明在自己所述範圍內成立的界。大於一的界是有效的,但沒有資訊量;它總可以與平凡的上界一結合使用。
選擇指數參數
證明中的參數並不是隨機試驗本身的性質。它是我們手頭的一個可調旋鈕,因為馬爾可夫不等式對每個正閾值、每個非負隨機變量都成立。對於上尾,我們可以取任意正的 λ \lambda λ ,推出一個有效的界,然後選取使右邊最小的那個。使其最小的取值取決於偏離的閾值。如果選了一個方便但並非最優的參數,結果仍然有效,只是可能較弱。
概念視角 分析
把這個界看成速率函數的指數 對 x = ( 1 + δ ) μ x=(1+\delta)\mu x = ( 1 + δ ) μ ,在 λ > 0 \lambda>0 λ > 0 上最好的界是 exp ( − sup λ [ λ x − μ ( e λ − 1 ) ] ) \exp(-\sup\limits_\lambda[\lambda x-\mu(e^\lambda-1)]) exp ( − λ sup [ λ x − μ ( e λ − 1 )]) 。這個上確界是 μ ( e λ − 1 ) \mu(e^\lambda-1) μ ( e λ − 1 ) 的勒讓德(Legendre)變換,等於 μ [ ( 1 + δ ) ln ( 1 + δ ) − δ ] \mu[(1+\delta)\ln(1+\delta)-\delta] μ [( 1 + δ ) ln ( 1 + δ ) − δ ] 。所以第一個定理說的是:尾概率至多為 e − I ( x ) e^{-I(x)} e − I ( x ) ,其中 I I I 是均值為 μ \mu μ 的泊松(Poisson)變量的速率函數。
對於下尾,指數的方向同樣重要。當 λ \lambda λ 為負時,X X X 增大會使 e λ X e^{\lambda X} e λ X 減小。於是 X X X 的一個較小值被轉化為非負變量的一個較大值,而這正是馬爾可夫不等式所能控制的事件。兩個論證使用的矩界相同,但指數函數的符號與單調性區分了這兩個事件。在應用馬爾可夫不等式之前先寫下事件的包含關係,是防止符號錯誤的可靠辦法。
乘積估計利用了均值,卻丟棄了其他資訊。具體而言,1 − p i + p i e λ ≤ e p i ( e λ − 1 ) 1-p_i+p_i e^\lambda\le e^{p_i(e^\lambda-1)} 1 − p i + p i e λ ≤ e p i ( e λ − 1 ) 可能相當鬆,把這些不等式相乘後只保留了 p i p_i p i 之和。若精確的概率已知,可以保留乘積,並對其馬爾可夫界做數值優化。對於概率相等的情形,精確分佈是二項分佈,也可以改為對相應的二項概率求和。這些簡單的界之所以有價值,是因為它們給出了無需這些精確計算的通用保證。
設 100 100 100 個計數器中,每一個都是均值為 60 60 60 的獨立指示變量之和。獨立性只要求在每個計數器內部成立,不同的計數器可以共享隨機性。對每個計數器,其降到至多 30 30 30 的下尾概率至多為 e − 7.5 e^{-7.5} e − 7.5 。因此,至少有一個計數器降到這麼低的概率至多為 100 e − 7.5 ≈ 0.0553 100e^{-7.5}\approx0.0553 100 e − 7.5 ≈ 0.0553 。即使各計數器之間共享隨機性,聯集界仍然有效。而在沒有證明失敗事件相互獨立的情況下,把各自的失敗概率相乘是不正確的。
乘性估計與加性估計的比較
配套的集中不等式筆記證明了獨立伯努利變量的加性 Hoeffding 不等式,並用它來放大多數表決。它對向上偏離 a a a 的界為 e − 2 a 2 / n e^{-2a^2/n} e − 2 a 2 / n ;而這裏的乘性界則隨均值而變化。兩者在各自所述的假設下都成立,但在沒有比較實際指數之前,不應宣稱其中某一個普遍更好。當成功很稀少時,μ \mu μ 可以遠小於 n n n ,乘性估計便能反映這種稀疏性。
例如,設 n = 1000 n=1000 n = 1000 個獨立指示變量的成功概率均為 0.01 0.01 0.01 ,故 μ = 10 \mu=10 μ = 10 。要界定至少 20 20 20 次成功的概率,取 δ = 1 \delta=1 δ = 1 。二次型乘性估計給出 e − 10 / 3 ≈ 0.0357 e^{-10/3}\approx0.0357 e − 10/3 ≈ 0.0357 ;取 a = 10 a=10 a = 10 的加性 Hoeffding 估計給出 e − 0.2 ≈ 0.819 e^{-0.2}\approx0.819 e − 0.2 ≈ 0.819 。更精細的乘性公式給出 ( e / 4 ) 10 ≈ 0.0210 (e/4)^{10}\approx0.0210 ( e /4 ) 10 ≈ 0.0210 。三者都是同一事件的上界,人們可以自由使用其中最小的有效界。對於這個概率相等的例子,如有需要,精確概率可以由二項分佈計算得到。
不同的分母解釋了這一差別。Hoeffding 的界只用到有界獨立變量的個數和加性位移。乘性論證則利用成功概率之和來界定矩母函數。較小的均值提供了額外的資訊,但這一優勢取決於事件和參數。在另一些參數範圍內,Hoeffding 的界可能更精細。比較數值估計是一個數學步驟;不核對其假設和尺度就選用某個有名字的不等式,是不夠的。
與均值無關的閾值
有時設計目標給出的是絕對閾值 t t t ,而我們只知道均值的一個上界 m ≥ μ m\ge\mu m ≥ μ 。若 t > m > 0 t>m>0 t > m > 0 ,上尾的證明仍能給出有用的保證,而無需假裝 m m m 就是真正的均值。對每個 λ > 0 \lambda>0 λ > 0 ,
Pr ( X ≥ t ) ≤ exp ( μ ( e λ − 1 ) − λ t ) ≤ exp ( m ( e λ − 1 ) − λ t ) , \Pr(X\ge t)\le\exp\bigl(\mu(e^\lambda-1)-\lambda t\bigr)
\le\exp\bigl(m(e^\lambda-1)-\lambda t\bigr), Pr ( X ≥ t ) ≤ exp ( μ ( e λ − 1 ) − λ t ) ≤ exp ( m ( e λ − 1 ) − λ t ) ,
這是因為 e λ − 1 > 0 e^\lambda-1>0 e λ − 1 > 0 。取 λ = ln ( t / m ) \lambda=\ln(t/m) λ = ln ( t / m ) ,得
Pr ( X ≥ t ) ≤ exp ( t − m ) ( m t ) t . \Pr(X\ge t)\le \exp(t-m)\left(\frac{m}{t}\right)^t. Pr ( X ≥ t ) ≤ exp ( t − m ) ( t m ) t .
這一計算在正確的方向上使用了上界。對於下尾,e λ − 1 e^\lambda-1 e λ − 1 的符號為負,若以同樣的方式代入 μ \mu μ 的上界,會使相關不等式反向;那裏有用的資訊是 μ \mu μ 的下界。
作為說明,設獨立指示變量的均值之和至多為 5 5 5 ,而不希望出現的閾值為 t = 15 t=15 t = 15 。則上面的結果把該事件的概率界定為 e 10 / 3 15 ≈ 0.00154 e^{10}/3^{15}\approx0.00154 e 10 / 3 15 ≈ 0.00154 。無需斷言均值等於五。若上界為零,則每個指示變量的均值都為零,和幾乎必然為零,所以正閾值的概率直接就是零。
上界閾值的論證也說明了如何安全地使用經過捨入的數值估計。經過證明的均值上界,可以透過上面的不等式代替實際均值進行上尾計算。而沒有確定方向的近似估計則不能自動代入。在程式碼中,應當記錄一個計算出的量是上界還是下界,以及其使用的嚴格條件。
相對精度與絕對精度
對於樣本比例,相對誤差與未知的 p p p 成比例。當 p p p 很小時,即使很小的絕對誤差也可能是很大的相對誤差。例題中的下界 p 0 p_0 p 0 保證了期望成功次數足夠多,使乘性估計對所有允許的 p p p 一致地具有資訊量。若沒有正的下界,則僅由 ε \varepsilon ε 和 α \alpha α 選定的任何有限樣本量,都無法對所有正的 p p p 一致地給出上面的相對保證:可以把 p p p 取得如此之小,使得觀察不到任何成功的可能性非常大。
要直接看出這一點,固定 n n n 並選取足夠小的正數 p p p 。觀察不到任何成功的概率為 ( 1 − p ) n (1-p)^n ( 1 − p ) n ,當 p ↓ 0 p\downarrow0 p ↓ 0 時它趨於一。在這個事件上 p ^ = 0 \widehat p=0 p = 0 ,其相對誤差為一。因此,對於任何 0 < ε < 1 0<\varepsilon<1 0 < ε < 1 ,該事件都違背了所要求的相對精度。這一論證並不是說在 p p p 已知,或自適應程序帶有額外假設時估計是不可能的;它說明的是對所有正概率一致成立的固定樣本量所受的限制。
絕對誤差的保證則要求對某個固定的 a > 0 a>0 a > 0 有 ∣ p ^ − p ∣ < a |\widehat p-p|<a ∣ p − p ∣ < a 。其適當的樣本複雜度可以借助無需已知 p p p 下界的其他集中界來研究。切不可悄悄地以其中一個問題取代另一個:例如,當 p = 0.5 p=0.5 p = 0.5 時 0.01 0.01 0.01 的絕對誤差很小,但當 p = 0.001 p=0.001 p = 0.001 時它卻是 p p p 的十倍。所估計的量決定了數學應當界定哪一個失敗事件。
在算法中解讀該界
概率陳述描述的是由指定算法與輸入所誘導的分佈。它並不指明哪些具體的執行會成功。若算法能夠驗證自己的輸出,驗證失敗時也許可以重試;此時必須分析重試的成本與獨立性。若無法進行這樣的驗證,尾部估計仍然界定了答案不準確的概率,但並不能使算法事後辨認出該答案。
區分尾界與對期望的保證也很有用。均值為 60 60 60 並不排除結果為 30 30 30 ,而出現這種結果的概率極小,也不意味著它不可能發生。當設計要求失敗概率至多為 α \alpha α 時,計算必須表明數值上界不大於 α \alpha α 。例如,若界為 0.0553 0.0553 0.0553 ,那麼即使精確概率恰好更小,它也不能證明 0.05 0.05 0.05 的目標。可以增加試驗次數,使用更精細的表達式,或者在模型允許時計算精確概率。
所述的上尾與下尾不等式在閾值處包含等號。對於整數值的計數,實數閾值如 27.4 27.4 27.4 在上尾事件中可實現為 X ≥ 28 X\ge28 X ≥ 28 ,在下尾事件中可實現為 X ≤ 27 X\le27 X ≤ 27 。概率不等式按所寫的形式仍然有效;若把閾值向錯誤的方向取整,就改變了事件,並可能得出無效的數值結論。明確指出這一整數事件,對於對照分析界檢查程式碼尤其有用。
可選 獨立性究竟用在哪裏? 證明只透過指數矩的一個不等式用到獨立性。
通往推廣的路徑
獨立性究竟用在哪裏? 證明只透過指數矩的一個不等式用到獨立性。
獨立性只用了一次,就是把 E [ e λ X ] \mathbb E[e^{\lambda X}] E [ e λ X ] 寫成 ∏ i E [ e λ X i ] \prod\limits_i\mathbb E[e^{\lambda X_i}] i ∏ E [ e λ X i ] 。若對相關符號的 λ \lambda λ 有 E [ e λ X ] ≤ ∏ i ( 1 − p i + p i e λ ) \mathbb E[e^{\lambda X}]\le\prod\limits_i(1-p_i+p_ie^\lambda) E [ e λ X ] ≤ i ∏ ( 1 − p i + p i e λ ) ,證明其餘部分原樣適用。已知某些相依的族也滿足這個不等式,例如負相關聯的指示變量,把球獨立投入箱子時「各箱是否為空」的指示變量就屬於這一類。驗證它是另一個論證,本節沒有給出。
關閉
總結
對計數取指數,使獨立性能夠分解期望,而馬爾可夫不等式再把這個期望轉化為上尾和下尾的估計。對於均值固定比例的偏離,失敗概率隨均值以指數速度下降。樣本量的應用需要獨立性,以及成功概率的一個已知正下界。
練習
快速檢查
(對於 n = 80 n=80 n = 80 次獨立的均勻硬幣擲出,用二次型界估計至少 60 60 60 次正面的機會。)
先算 μ \mu μ ,再求滿足 ( 1 + δ ) μ = 60 (1+\delta)\mu=60 ( 1 + δ ) μ = 60 的 δ \delta δ 。
解答 · 答案 此處 μ = 40 \mu=40 μ = 40 ,δ = 1 / 2 \delta=1/2 δ = 1/2 ,所以概率至多為 e − 40 / 12 = e − 10 / 3 ≈ 0.0357 e^{-40/12}=e^{-10/3}\approx0.0357 e − 40/12 = e − 10/3 ≈ 0.0357 。
快速檢查
(設 X X X 計數 100 100 100 次獨立試驗的成功次數,每次成功概率為 0.2 0.2 0.2 。界定 Pr ( X ≤ 10 ) \Pr(X\le10) Pr ( X ≤ 10 ) 。)
求滿足 ( 1 − δ ) μ = 10 (1-\delta)\mu=10 ( 1 − δ ) μ = 10 的 δ \delta δ ,再用下尾界。
解答 · 答案 此處 μ = 20 \mu=20 μ = 20 ,δ = 1 / 2 \delta=1/2 δ = 1/2 ,得 Pr ( X ≤ 10 ) ≤ e − 20 / 8 = e − 2.5 ≈ 0.0821 \Pr(X\le10)\le e^{-20/8}=e^{-2.5}\approx0.0821 Pr ( X ≤ 10 ) ≤ e − 20/8 = e − 2.5 ≈ 0.0821 。
快速檢查
(為甚麼當對所有 i i i 都有 X i = Y X_i=Y X i = Y (其中 Y Y Y 是成功概率為 1 / 2 1/2 1/2 的單個伯努利變量)時,該定理不適用?)
比較 Pr ( X 1 = 1 , X 2 = 1 ) \Pr(X_1=1,X_2=1) Pr ( X 1 = 1 , X 2 = 1 ) 與邊際概率之積。
解答 · 答案 這些變量並不獨立:例如 Pr ( X 1 = 1 , X 2 = 1 ) = 1 / 2 \Pr(X_1=1,X_2=1)=1/2 Pr ( X 1 = 1 , X 2 = 1 ) = 1/2 ,而它們邊際概率的乘積為 1 / 4 1/4 1/4 。因此,指數期望所需的分解是無效的。
快速檢查
(對於相對誤差 ε = 1 / 2 \varepsilon=1/2 ε = 1/2 、已知 p ≥ 0.1 p\ge0.1 p ≥ 0.1 及失敗目標 α = 0.05 \alpha=0.05 α = 0.05 ,由上面給出的公式給出一個充分的整數樣本量。)
計算 3 ln ( 2 / α ) / ( p 0 ε 2 ) 3\ln(2/\alpha)/(p_0\varepsilon^2) 3 ln ( 2/ α ) / ( p 0 ε 2 ) 並向上取整。
解答 · 答案 公式給出 n ≥ 3 ln 40 / ( 0.1 ⋅ 0.25 ) ≈ 442.665 n\ge3\ln40/(0.1\cdot0.25)\approx442.665 n ≥ 3 ln 40/ ( 0.1 ⋅ 0.25 ) ≈ 442.665 ,所以 n = 443 n=443 n = 443 已經足夠。這一結果是上界保證,並不聲稱它是可能的最小樣本量。