形式陈述

若独立随机变量 $X_i\in [a_i,b_i]$，并令 $S_n=\sum _{i=1}^n{X}_i$，则对 $t>0$

$$\text{Pr}(S_n-\mathbb{E}{S}_n\ge t)\le \exp (-\frac{2t^2}{\sum _i(b_i-a_i{)}^2}).$$

下尾同理，合并得到双侧界。证明使用指数 Markov 不等式和 Hoeffding 引理。

直觉

有界性限制每个样本的最大冲击，独立性让指数矩分解，因而尾概率获得指数衰减。

例子与边界

对独立 Bernoulli 样本均值，

$$\text{Pr}(|\overline{X}-\mathbb{E}\overline{X}|\ge \epsilon )\le 2e^{-2n{\epsilon }^2}.$$

变量相关或无界时不能直接使用；有方差信息时 Bernstein 类界可能更紧。

推论与应用

它支撑有限样本统计、机器学习泛化、在线算法和随机化算法中的高概率保证。

参考资料

• Wassily Hoeffding, Probability Inequalities for Sums of Bounded Random Variables (1963), original theorem.
• Joseph K. Blitzstein, Jessica Hwang, Introduction to Probability / Harvard Stat 110 (2019/2026 site), concentration inequalities.