伯恩斯坦不等式（Bernstein's inequality）
/ BERN-shtine /
伯恩斯坦不等式是變異數感知的集中界：它用獨立變數的實際變異數與其尺度的單一上界來控制其和，在小偏差時回到高斯速率、在大偏差時給出指數速率。當 Hoeffding 的變異數代理大得浪費時——變異數小的有界變數，或像高斯平方那樣的次指數變數，基於代理的界會丟掉大部分可用的集中——你就會訴諸這個不等式。
有兩種標準形式。有界形式：若 X_1、…、X_n 獨立、置中、幾乎必然 |X_i| <= b，且總變異數 sigma^2 = sum Var(X_i)，則 P(sum X_i >= t) <= exp(-t^2 / (2(sigma^2 + bt/3)))。次指數形式：若 X_i 為置中次指數、參數為 (nu_i, b)（意指 E[exp(lambda X_i)] <= exp(nu_i^2 lambda^2 / 2) 僅對 |lambda| < 1/b 成立），則 P(sum X_i >= t) <= exp(-(1/2) min(t^2 / sum nu_i^2, t / b))。兩者都展現特徵性的兩區段行為。對小的 t，分母由 sigma^2 主導，給出高斯尾 exp(-t^2 / 2 sigma^2)——正確答案，由「真」變異數而非代理縮放。對大的 t，bt/3 項（或 t/b 區段）接管，給出反映有界尺度的卜瓦松型指數尾 exp(-3t / 2b)。證明仍是 Chernoff，但動差母函數受到更細緻的界定：不把一切都塞進二次式，而是保留冪級數 e^(lambda x) = 1 + lambda x + (lambda x)^2/2 + ...，並用 lambda b 的等比級數界定高階項，這正是產生兩區段的原因。
伯恩斯坦是高維統計的主力，正因為它的小偏差區段使用變異數。當你從值域遠大於變異數的有界資料估計均值時，Bernstein 給出隨 sigma^2 而非 b^2 縮放的速率——往往是戲劇性的改進。誠實的提醒：兩區段之間的轉折點在 min 中兩項相等之處，t ~ sigma^2/b，而界在何處恰好變緊對應用很重要。Bennett 不等式嚴格比 Bernstein 更尖銳（對其速率函數做凸性界定後 Bennett 蘊含 Bernstein），而對於卜瓦松型的極端尾，Bennett 給出 Bernstein 只能近似的精確對數速率。
從 n 個 Bernoulli(p) 樣本估計機率 p ~ 0.01。每個置中指示變數有 |X_i| <= 1 但變異數 p(1-p) ~ 0.01，遠低於 1。Hoeffding 需要 n ~ log(1/delta)/t^2；Bernstein 使用 sigma^2 = p(1-p)，在小 t 區段只需 n ~ p log(1/delta)/t^2——當 p = 0.01 時減少百倍。
對於罕見事件，Bernstein 的變異數項以 1/p 的因子勝過 Hoeffding。
Bernstein 需要尺度的界（有界性，或次指數參數 b）；若除了多項式動差外沒有任何動差母函數的控制，兩區段界不一定成立。Bernstein 為 Bennett 所蘊含，且略弱於 Bennett。