大偏差有多罕見?
弱大數定律指出,獨立同分佈、方差有限的變量,其平均數依概率趨向均值。但面對有限樣本,我們常需要指定誤差發生的概率上界。切比雪夫(Chebyshev)不等式只利用方差,固定誤差下所得界按 的速度下降。若觀測值獨立且有界,指數變換能提供更強的資訊,得到隨 指數下降的界。
令 。對任何 ,只要所需期望有限,把馬爾可夫(Markov)不等式應用於正隨機變量 ,便有
每個允許的 都給出有效的界;選擇 是方法的一部分。獨立性令期望分解為各變量指數矩的乘積。控制每個因子後,才得到樣本數增加帶來的改善。
有界變量的指數矩引理
定理 20.1.1
(Hoeffding 引理)
若實隨機變量 幾乎必然滿足 ,其中 ,則對每個實數 ,
若 ,中心化變量為零,同一公式的右邊為 。
證明
(對數矩生成函數的曲率)
設 及 。由於 有界,我們可對期望在所有實數 下微分。在密度為 的傾斜概率測度之下,微分得到 及 。傾斜後 仍落在長度為 的區間。
對任何落在 的隨機變量 ,由 得 ,因此
所以 。又 ,從 到 積分兩次便得 。若 ,可對 和 應用同一論證。取指數即得結論。
證明透視
區間長度為何要平方
證明從不直接估計 ,而是轉到 ,控制它的曲率。 有界這一點用了兩次:它容許對所有實數 在期望號下微分;它在指數傾斜後仍然保留,因為傾斜後的分佈有相同支撐集,所以 仍落在長度為 的區間。中心化只用了一次,給出 ;連同 ,它去掉了泰勒(Taylor)估計中的常數項和一次項。
關鍵一步是把 看成傾斜測度下的方差,並以同一常數 控制所有這些方差。積分兩次後,正是這個一致上界變成 。只控制 的方差,只能控制 ,對遠離零的 毫無資訊。因此區間長度的平方,是作為限於該長度區間的變量所能有的最大方差而出現的。
定理 20.1.2
(和的 Hoeffding 不等式)
設 獨立,且幾乎必然有 。令 。若 、,則
因此雙尾概率不超過 。若 ,和幾乎必然為常數,兩個偏差事件的概率均為零。
證明
(最優化二次指數)
由獨立性和引理,對每個 ,上尾概率不超過 。此二次式在 達到最小值,得到所述指數。對 應用同一論證可得下尾界,再用聯集界處理雙尾。
若獨立變量都在 內,代入 得
它們不必同分佈:這裏的中心是各自期望的平均。若觀測值獨立同分佈,中心便是共同均值 。
常見錯誤
(單尾不等於雙尾)
上界 只控制一條尾。像 這樣的事件是兩條尾的聯集,聯集界把兩個估計相加,因子 不能省去。在下面的樣本數例子中,若省去它, 會變成 ,所需樣本數會被低估為 ,而非 。
例題 20.1.3
(有限樣本的精度保證)
假設 是 內獨立同分佈的測量,未知均值為 。要保證 的上述上界不超過 ,只需
因此 足夠。這是針對最壞情況的充分樣本數,不是說實際誤差概率等於 ,也不表示某個特定分佈不能使用較少觀測值。
例題 20.1.4
(同一保證下的 Chebyshev 與 Hoeffding)
沿用上例的設定。由引理證明中的區間方差上界,落在 的變量方差至多為 。因此 Chebyshev 不等式給出
只有 時它才不超過 ,約為 Hoeffding 所需 的九倍。樣本很小時,兩個界都可能沒有資訊。 時,Chebyshev 給出 ,Hoeffding 給出 ;後者大於一,因此甚麼也沒有說。只有當 大到足以令指數項抵銷因子 時,指數界才有用。
保留伯努利分佈的資訊
只使用範圍的界忽略了成功概率;保留它可以得到更精確的指數。
定理 20.1.5
(伯努利(Bernoulli)和的 Chernoff 界)
設 獨立同分佈且服從伯努利(Bernoulli),其中 ,則 計算成功次數。令
若 ,則 ;若 ,則 。
證明
(最優化指數參數)
對 及 ,Markov 不等式與獨立性給出
右邊的對數除以 後,其導數為 。唯一零點滿足 ,此時 。代入得
若 ,對失敗次數 應用上尾情況:它服從成功概率為 的二項分佈,事件 即 ,其中 ,且 。
門檻 不必是整數;事件的意思是 。端點 及 可直接處理:其概率分別是 和 。以上是不等式而非尾概率的精確值; 是兩個概率的函數,一般不對稱,故不是距離。
常見錯誤
(Chernoff 指數只適用於越過均值的一側)
上尾界要求 。由於對每個 都有 ,把它用在均值錯誤的一側,會得到虛假地小的數。取 、,若選 ,則 ,;但 接近一:正確的下尾界給出 ,因此 。
例題 20.1.6
(偏置硬幣)
取 、、,Chernoff 界為
只利用範圍的單尾 Hoeffding 界用 ,結果為 。此例中的 Chernoff 界較精確,但兩者都不是二項分佈尾概率的精確值。
反例模式
相同的觀測值未必獨立
令 ,其中 服從伯努利。每個 均在 內,但 ,因此對每個 都有 。若錯誤代入獨立變量的界,隨 增加最終會得到小於 的數值。有界和同分佈不能取代獨立性。
練習
快速檢查
(獨立變量幾乎必然滿足 。求 的雙尾上界。)
解答 · 答案
共同區間長度為 ,所以上界是 。事件中的均值是各個均值的平均,毋須同分佈。
快速檢查
(獨立的 分別幾乎必然在 和 。求 的上界。)
解答 · 答案
、,故界為 。
快速檢查
(若 ,用伯努利 Chernoff 計算求 的精確形式上界。)
解答 · 答案
取 、,得到 。由於 ,此界適用於 。
快速檢查
(一個獨立同分佈樣本在 內。對 ,找出 ,使 以至少 的概率包含均值。說明哪個對象是隨機的。)
解答 · 答案
令 ,得 。區間隨樣本改變,而總體均值是固定的。覆蓋結論來自雙尾不等式;觀察到某個區間後,不能說固定均值以概率 落在該特定區間內。