霍夫丁不等式

霍夫丁不等式（英语：Hoeffding's inequality）适用于有界的随机变量。设有两两独立的一系列随机变量${\displaystyle X_{1},\dots ,X_{n}\!}$。假设对所有的${\displaystyle 1\leq i\leq n}$，${\displaystyle X_{i}}$都是几乎有界的变量，即满足：

${\displaystyle \mathbb {P} (X_{i}\in [a_{i},b_{i}])=1.\!}$

那么这n个随机变量的经验期望：

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

满足以下的不等式^[1]：

${\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),\!}$