霍夫丁不等式

在概率论中，霍夫丁不等式（英语：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}}}.}$ ^[6] 因此，我们至少需要 ${\displaystyle {\frac {\log({\frac {2}{\alpha }})}{2\varepsilon ^{2}}}}$ 份样本才能获得 (1- α)-置信区间 ${\displaystyle \textstyle p\pm \varepsilon }$ 。因此，获取置信区间的成本在置信水平方面是次线性的，在精度方面是二次的。请注意，有更有效的方法来估计置信区间。

参见

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