柴諾夫界（Chernoff bound）
/ CHER-nof /
柴比雪夫告訴你偏離許多個標準差是罕見的，但只以 1/k^2 這種慢吞吞的速率。對於許多獨立的、像擲硬幣那樣的貢獻之總和，現實要戲劇化得多：大幅偏離的機率以指數方式衰減，像 e 的負次方。柴諾夫界正是捕捉這種更銳利、指數級微小衰減的技術。
訣竅是把馬可夫不等式套用到的不是 X、也不是 X^2，而是指數 e^(tX)，其中 t > 0 是一個可調參數。由於指數函數遞增，事件 X >= a 等同於 e^(tX) >= e^(ta)，於是馬可夫給出 P(X >= a) <= E[e^(tX)] / e^(ta)。量 E[e^(tX)] 就是動差母函數 M(t)。接著是神來之筆：這對每個 t > 0 都成立，所以你可以自由挑選讓右邊最小的那個 t。對 t 最小化 e^(-ta) M(t)，就把動差所允許的最緊指數界給擠了出來。
為什麼這把柴比雪夫贏得這麼徹底？對 n 個獨立項之和，總和的 MGF 是各別 MGF 的乘積，所以 M(t) 漂亮地分解，界就變成 n 的指數函數。這正是「經驗平均以至少 1 - 2 e^(-2 n epsilon^2) 的機率落在真值的 epsilon 之內」這類敘述的來源。誠實的陷阱：這個方法需要 MGF 在 0 附近存在，這對重尾變數會失效——那時你只能退回馬可夫或柴比雪夫。霍夫丁與伯恩斯坦不等式，不過是把柴諾夫的配方套用到特定、性質良好的情形而已。
擲一枚公正硬幣 n 次；令 X 為正面數，均值 n/2。柴諾夫大致給出 P(X >= 3n/4) <= e^(-n/8)。對 n = 100，約為 e^(-12.5)，不到百萬分之四——而柴比雪夫只能保證約 1/25。指數級衰減正是重點所在。
把馬可夫套用到 e^(tX)，再對 t 最佳化：總和的尾部呈指數級微小。
柴諾夫不是單一公式而是一種方法（對 MGF 用馬可夫，再對 t 最佳化）。它只在 MGF 於 0 附近存在時有效；重尾變數沒有 MGF，抵抗這個做法。