霍夫丁不等式

在機率論中，霍夫丁不等式（英語：Hoeffding's inequality）適用於有界的隨機變數，提供了有界獨立隨機變數之和偏離其期望值超過一定數量的機率的上限，即${\displaystyle \max \mathbb {P} ({\overline {X}}-\mathbb {E} [{\overline {X}}]\geq t)}$。霍夫丁不等式在1963年由瓦西里·霍夫丁（Wassily Hoeffding）證明。

霍夫丁不等式是吾妻不等式和麥克迪亞米德不等式（英語：McDiarmid's inequality）的一個特例。它類似於切爾諾夫界，但往往不那麼尖銳，特別是當隨機變數的變異數很小時。它與伯恩斯坦不等式相似，但無法與之相比。

闡述

設有兩兩獨立的一系列隨機變數 ${\displaystyle X_{1},\dots ,X_{n}\!}$ 。假設對所有的 ${\displaystyle 1\leq i\leq n}$，${\displaystyle X_{i}}$ 變量幾乎必然滿足 ${\displaystyle a_{i}\leqslant X_{i}\leqslant b_{i},}$ 即 ${\displaystyle \mathbb {P} (X_{i}\in [a_{i},b_{i}])\approx 1.\!}$ 考慮這些隨機變數的總和，${\displaystyle S_{n}=\sum _{i=1}^{n}X_{i}=X_{1}+X_{2}+X_{3}+\cdots +X_{n-1}+X_{n}.}$ 然後霍夫丁不等式指出，對於所有 ${\displaystyle t>0}$ 有：

• ${\displaystyle \mathbb {P} (S_{n}-\mathbb {E} [S_{n}]\geqslant t)\leqslant \exp \left(-{\frac {2t^{2}}{\textstyle \sum _{i=1}^{n}(b_{i}-a_{i})^{2}\displaystyle }}\right)}$
• ${\displaystyle \mathbb {P} (|S_{n}-\mathbb {E} [S_{n}]|\geqslant t)\leqslant 2\exp \left(-{\frac {2t^{2}}{\textstyle \sum _{i=1}^{n}(b_{i}-a_{i})^{2}\displaystyle }}\right)}$

這裡 ${\displaystyle \mathbb {E} [S_{n}]}$ 是 ${\displaystyle S_{n}}$ 的期望值。

值得注意的是，若 ${\displaystyle X_{i}}$ 為抽樣獲得，該不等式仍成立；但在這種情況下，隨機變數不再是獨立的。這一說法的證據可以在 Hoeffding ^[1]的論文中找到。對於抽樣的稍微更好的上界，可參見Serfling（1974）^[2]的論文。

另一種形式

設有兩兩獨立的一系列隨機變數，那麼這n個隨機變數的經驗期望值：

${\displaystyle {\overline {X}}={\frac {X_{1}+\cdots +X_{n}}{n}}}$

滿足以下的不等式^[3]：

${\displaystyle \mathbb {P} ({\overline {X}}-\mathbb {E} [{\overline {X}}]\geq t)\leq \exp \left(-{\frac {2t^{2}n^{2}}{\sum _{i=1}^{n}(b_{i}-a_{i})^{2}}}\right),\!}$

${\displaystyle \mathbb {P} (|{\overline {X}}-\mathbb {E} [{\overline {X}}]|\geq t)\leq 2\exp \left(-{\frac {2t^{2}n^{2}}{\sum _{i=1}^{n}(b_{i}-a_{i})^{2}}}\right),\!}$

特別地

假定對於所有的 ${\displaystyle i}$ 都有 ${\displaystyle a_{i}=0,b_{i}=1}$ 。當 ${\displaystyle X_{i}}$ 是獨立的伯努利隨機變數時，儘管它們不必服從相同分布，我們可以得到如下更為簡潔的不等式：

${\displaystyle \mathbb {P} (S_{n}-\mathbb {E} [S_{n}]\geqslant t)\leqslant \exp(-{\frac {2t^{2}}{n}}).}$

上式對於所有的 ${\displaystyle t\geqslant 0}$ 成立。這樣我們就得到了增強版的切爾諾夫界。它更為通用，因為它允許取值介於 0 和 1 之間的隨機變數，但效果較差，因為當隨機變數變異數較小時，切爾諾夫界給出了更好的尾邊界。

次高斯隨機變數的一般情況

霍夫丁不等式的證明可以推廣到任何次高斯分布。

回想一下，隨機變數 ${\displaystyle X}$ 服從次高斯分布（英語：sub-Gaussian distribution），是否存在 ${\displaystyle c>0}$ 使得，${\displaystyle \mathbb {P} (\left\vert X\right\vert \geqslant t)\leqslant 2e^{-ct^{2}}}$ 成立。

對於任意有界變量 ${\displaystyle X,}$ ${\displaystyle t>T}$（ ${\displaystyle T}$ 足夠大），有 ${\displaystyle \mathbb {P} (|X|\geqslant t)=0\leqslant 2e^{-ct^{2}}}$ 。對於任意的 ${\displaystyle t\leqslant T}$ 有 ${\displaystyle 2e^{-cT^{2}}\leqslant 2e^{-ct^{2}}}$ ，取 ${\displaystyle c={\frac {\ln 2}{T^{2}}}}$ 則有 ${\displaystyle \mathbb {P} (|X|\geqslant t)\leqslant 1\leqslant 2e^{-cT^{2}}\leqslant 2e^{-ct^{2}},}$ 所以每個有界變量都是亞高斯變量。

對於隨機變數 ${\displaystyle X}$，下式範數是有限的，若且唯若 ${\displaystyle X}$ 是亞高斯：

${\displaystyle \lVert X\rVert _{\psi _{2}}{\overset {\underset {\mathrm {def} }{}}{=}}\inf\{c\geq 0:\mathbb {E} [e^{\frac {X^{2}}{c^{2}}}]\}.}$

然後設 ${\displaystyle X_{1},\cdots ,X_{n}}$ 為零均值獨立亞高斯隨機變數，霍夫丁不等式的一般版本指出：

${\displaystyle \mathbb {P} (|\sum _{i=1}^{n}X_{i}|\geqslant t)\leqslant 2\exp(-{\frac {ct^{2}}{\textstyle \sum _{i=1}^{n}\displaystyle \lVert X_{i}\rVert _{\psi _{2}}^{2}}}),}$ 其中 ${\displaystyle c>0}$ 且為絕對常數^[4]。

證明

霍夫丁界的證明與切爾諾夫界等集中不等式類似^[5]。主要區別在於使用霍夫丁引理：

假設 ${\displaystyle X}$ 是一個真正的隨機變數，那麼幾乎必然 ${\displaystyle X\in \left[a,b\right]}$ 。然後${\displaystyle \mathbb {E} \left[e^{s\left(X-\mathbb {E} \left[X\right]\right)}\right]\leqslant \exp \left({\tfrac {1}{8}}s^{2}(b-a)^{2}\right).}$

使用這個引理，我們可以證明霍夫丁不等式。如定理陳述，假設 ${\displaystyle X_{1},\cdots ,X_{n}}$ 為 ${\displaystyle n}$ 個獨立隨機變數，${\displaystyle X_{i}\in \left[a_{i},b_{i}\right],}$ ${\displaystyle s.t.\ i\in N_{+}}$幾乎必然 。設 ${\displaystyle S_{n}=X_{1}+\cdots +X_{n}.}$ 那麼對於 ${\displaystyle s>0}$ 且 ${\displaystyle t>0}$ , 聯立馬可夫不等式和 ${\displaystyle X_{i}}$ 的獨立性可得：

${\displaystyle {\begin{aligned}\operatorname {P} \left(S_{n}-\mathrm {E} \left[S_{n}\right]\geq t\right)&=\operatorname {P} \left(\exp(s(S_{n}-\mathrm {E} \left[S_{n}\right]))\geq \exp(st)\right)\\&\leq \exp(-st)\mathrm {E} \left[\exp(s(S_{n}-\mathrm {E} \left[S_{n}\right]))\right]\\&=\exp(-st)\prod _{i=1}^{n}\mathrm {E} \left[\exp(s(X_{i}-\mathrm {E} \left[X_{i}\right]))\right]\\&\leq \exp(-st)\prod _{i=1}^{n}\exp {\Big (}{\frac {s^{2}(b_{i}-a_{i})^{2}}{8}}{\Big )}\\&=\exp \left(-st+{\tfrac {1}{8}}s^{2}\sum _{i=1}^{n}(b_{i}-a_{i})^{2}\right)\ \end{aligned}}}$

此上界對於 ${\displaystyle s}$ 的值是最佳的，最小值在指數 ${\displaystyle O(e^{n})}$ 範圍內。這可以通過最佳化二次曲線輕鬆完成，給出 ${\displaystyle s={\frac {4t}{\sum _{i=1}^{n}(b_{i}-a_{i})^{2}}}.}$

為這個值 ${\displaystyle s}$ 編寫上面的界限，我們得到所需的界限：${\displaystyle \operatorname {P} \left(S_{n}-\mathrm {E} \left[S_{n}\right]\geq t\right)\leq \exp \left(-{\frac {2t^{2}}{\sum _{i=1}^{n}(b_{i}-a_{i})^{2}}}\right).}$

用法

霍夫丁不等式可用於推導信賴區間。我們考慮一枚硬幣，它以機率 ${\displaystyle p}$ 顯示正面，以機率 ${\displaystyle 1-p}$ 顯示反面。我們拋硬幣 ${\displaystyle n}$ 次，生成 ${\displaystyle n}$ 個樣本  ${\displaystyle X_{1},\cdots ,X_{n}}$（即獨立同分布伯努利隨機變數）。硬幣正面朝上的預期次數是 ${\displaystyle p\cdot n}$ 。此外，硬幣正面至少出現k次的機率可以通過以下表達式精確量化：

${\displaystyle \operatorname {\mathbb {P} } (H(n)\geqslant k)=\sum _{i=k}^{n}{\binom {n}{i}}p^{i}(1-p)^{n-i},}$ 其中 ${\displaystyle H(n)}$ 是 ${\displaystyle n}$ 次拋硬幣的正面數量。當 ${\displaystyle k=(p+\varepsilon )n}$ 表示某個 ${\displaystyle \varepsilon >0}$ 時，霍夫丁不等式將這個機率限制為一個在 ${\displaystyle \varepsilon ^{2}n}$ 中呈指數小的項：

${\displaystyle \operatorname {\mathbb {P} } (H(n)-pn>\varepsilon n)\leqslant \exp \left(-2\varepsilon ^{2}n\right).}$

由於這個界限在均值的兩側都成立，霍夫丁不等式意味著我們看到的頭部數量集中在其均值周圍，尾部呈指數級小。

${\displaystyle \operatorname {\mathbb {P} } (|H(n)-pn|>\varepsilon n)\leqslant 2\exp \left(-2\varepsilon ^{2}n\right).}$

${\displaystyle {\overline {X}}={\frac {1}{n}}H(n)}$ 作為「觀察到的」平均值，該機率可以解釋為一個信賴區間的顯著水準 ${\displaystyle \alpha }$（出錯的機率），這個信賴區間是中心為 ${\displaystyle p}$ 的 ${\displaystyle \varepsilon }$ 鄰域：

${\displaystyle \alpha =\operatorname {\mathbb {P} } (\ {\overline {X}}\notin [p-\varepsilon ,p+\varepsilon ])\leqslant 2e^{-2\varepsilon ^{2}n}.}$ 解出 ${\displaystyle n}$ : ${\displaystyle n\geqslant {\frac {\log({\frac {2}{\alpha }})}{2\varepsilon ^{2}}}.}$因此，我們至少需要 ${\displaystyle {\frac {\log({\frac {2}{\alpha }})}{2\varepsilon ^{2}}}}$ 份樣本才能獲得 (1- α)-信賴區間 ${\displaystyle \textstyle p\pm \varepsilon }$ 。因此，獲取信賴區間的成本在信心水準方面是次線性的，在精度方面是二次的。請注意，有更有效的方法來估計信賴區間。

參見

• 集中不等式
• 霍夫丁引理
• 伯恩斯坦不等式