霍夫丁不等式（Hoeffding‘s inequality）

参考资料：Hoeffding's inequality | encyclopedia article by TheFreeDictionary

霍夫丁不等式（Hoeffding's inequality）描述了随机变量的和、与和的期望之差的上限；或者表述为：随机变量的均值、与均值的期望之差的上限。

假设为各自独立的随机变量，且限制在范围内，即，定义，则对任意，有

         (1)

    (2)

其中表示平均值 的期望。

上面公式推广到更一般的形式：

限制在范围内，即，则对任意，有

         (3)

       (4)

上面的公式也可表述为和的形式。

定义

         (5)

        (6)

备注：当是通过不放回取样得到的，上面的不等式也成立，但此时随机变量不再是独立的。