Chernoff 界與指數尾部

柴比雪夫誠實，但偷懶

上一篇指南裡，柴比雪夫不等式給了你對偏離的第一個真正抓手：落在離均值 k 個標準差以外的機率至多是 1/k^2。這個界很珍貴，因為它幾乎什麼都不要求——只要變異數有限。但看看 1/k^2 衰減得多慢。在 k = 5 時它仍允許 4% 的機率；在 k = 10 時，1% 的機率。對許多真實問題來說，這鬆得可笑。如果你擲一枚公正硬幣一千次，得到 750 個或更多正面的機率並不是 4%——它是天文數字般的微小。柴比雪夫就是看不出它有多小。

為什麼柴比雪夫在這裡這麼鬆？因為它只知道關於你的變數的兩個數字：它的均值與變異數。它用了二階動差，僅此而已。但許多獨立貢獻之和，所攜帶的結構遠比它的變異數所揭露的更多——而這些額外的結構藏在高階動差裡。要觸及它，我們需要一個能一次聆聽*所有*動差的工具。你在較早的階段已經遇過這樣一個工具：動差母函數。

那一個聰明的動作：對指數套用馬可夫

整個想法在這裡，而它真的就只是一個動作。第 1 篇指南的馬可夫不等式說，對一個非負變數 Y 和任意門檻 c > 0，P(Y >= c) <= E[Y] / c。Chernoff 的訣竅是聰明地挑選 Y。我們不是把馬可夫套用到 X 本身，也不是套用到 X^2（後者其實偷偷給出柴比雪夫），而是套用到 e^(tX)，其中 t > 0 是一個我們可以轉動的旋鈕。

為什麼這合法？因為指數函數是嚴格遞增的。所以事件「X >= a」與「e^(tX) >= e^(ta)」是*完全相同的事件*——對一個不等式兩邊都套用遞增函數，絕不會改變哪些結果滿足它。如今 e^(tX) 是一個非負變數，馬可夫便可直接套用：P(X >= a) = P(e^(tX) >= e^(ta)) <= E[e^(tX)] / e^(ta)。而分子 E[e^(tX)] 恰恰就是動差母函數 M(t)。於是我們得到了 P(X >= a) <= e^(-ta) M(t)。

Markov on e^(tX), for any t > 0:

    P(X >= a) = P( e^(tX) >= e^(ta) )
             <= E[e^(tX)] / e^(ta)
             =  e^(-ta) * M(t)

This is TRUE for EVERY t > 0,
so pick the t that makes the right side smallest.

最佳化之前的 Chernoff 不等式：對每個 t > 0 都成立的一個真界。

接著轉旋鈕：對 t 最小化

現在來到把一個真界變成*銳利*界的部分。不等式 P(X >= a) <= e^(-ta) M(t) 對每個 t > 0 都成立。我們並不被綁在任何特定的 t 上——我們可以挑選任何一個喜歡的，包括讓右邊盡可能最小的那一個。所以 Chernoff 界就是這個最佳化後的陳述：P(X >= a) <= 對 t > 0 取 [ e^(-ta) M(t) ] 的最小值。我們把函數 e^(-ta) M(t) 壓到它的最低點，再回報那個值。不同的 t 值給出不同的有效界；我們只保留最好的那個。

對於為什麼存在一個最佳的 t，有很好的直覺。把 t 取得太小，因子 e^(-ta) 幾乎不縮小——你浪費了那個指數折扣。把 t 取得太大，M(t) = E[e^(tX)] 就會爆掉，因為指數會殘酷地放大 X 的大值。在兩者之間某處坐著一個甜蜜點，而最佳化找到的正是這個平衡。對它求導再令導數為零，是慣常的途徑；你已有的微積分就夠用了。

鎖定目標事件，例如 X >= a，其中 a 在均值之上（否則這個界就退化成 1，毫無用處）。
寫下「對指數套用馬可夫」的界 P(X >= a) <= e^(-ta) M(t)，對每個 t > 0 都成立。
為你的變數計算或查出 M(t) = E[e^(tX)]；它必須在 t 接近 0 處存在。
對 t > 0 最小化 e^(-ta) M(t)——取對數、求導、令其為零，解出 t。
把那個最佳的 t 代回去，得到最終的指數尾部界。

為什麼總和讓它爆發成指數衰減

到目前為止，這是適用於任何單一變數的方法。Chernoff 之所以出名——它之所以把柴比雪夫碾壓——出現在 X 是獨立片段之和時，X = X_1 + ... + X_n。回想變換那一階的獨立變數之和的 MGF：總和的 MGF 是各別 MGF 的*乘積*，M(t) = M_1(t) * M_2(t) * ... * M_n(t)。獨立性把一個總和那雜亂的分布，變成了簡單因子們乾淨的乘積。

當每個片段都相同時，那個乘積就變成單一 MGF 的 n 次方，[m(t)]^n。把它代入 e^(-ta) M(t)，整個右邊就是某個東西的 n 次方。最佳化之後，這個界呈現 e^(-n * c) 的形狀，其中 c 是某個正常數，取決於 a 落在均值之外多遠。這就是妙處所在：尾部機率隨 n 呈指數收縮，而非像 1/n。每多一個獨立觀測，就把你的界乘上一個固定的縮小因子，所以信心以複利的速度堆疊起來。

把它具體化。擲一枚公正硬幣 n 次，令 X 數正面，均值為 n/2。Chernoff 機器大致給出 P(X >= 3n/4) <= e^(-n/8)。對 n = 100，這約為 e^(-12.5)，不到百萬分之四。同樣餵入 n = 100 的柴比雪夫，對同一個事件卻只能保證約 1/25 = 4%。這兩個界根本不在同一個宇宙——而且這道鴻溝只會隨 n 增大而擴大。這種指數級的銳利，正是為什麼集中性論證倚賴 Chernoff 而非柴比雪夫。

誠實的細則

Chernoff 是一種方法，不是單一公式。「Chernoff 界」不是你背下來的某一條方程式；它是那個配方——對 e^(tX) 套用馬可夫，再對 t 最小化。那些著名的具名結果，不過是把這個配方套用到整潔的情形。下一篇指南的霍夫丁不等式，就是把 Chernoff 套用到有界變數；伯恩斯坦不等式則是當你還知道變異數很小時的 Chernoff。它們共用同一具引擎；只是輸入不同。

這裡有個真實的陷阱，與限制 MGF 的那個陷阱相同。整個方法需要 E[e^(tX)] 在 t 接近 0 時為有限——MGF 必須真的存在。對輕尾變數（有界、高斯、卜瓦松）它確實存在，於是 Chernoff 歌聲嘹亮。但重尾變數，像冪律尾的帕雷托或柯西，其 MGF 對每個 t > 0 都是無限大。對它們而言，e^(-ta) M(t) 不過是無限大乘上某個東西——一個毫無用處的界。那時你必須退回馬可夫或柴比雪夫，它們只需要動差存在，而不需要 MGF。尾部至少衰減得與高斯一樣快的變數，有個值得認識的名字——次高斯——它們正是 Chernoff 與霍夫丁所棲身的、性質良好的那一類。