1. 简介
在概率论中，霍夫丁不等式（Hoeffding’s Inequality）给出了有界独立随机变量之和偏离其均值超过一定数量的概率上界。霍夫不等式是切比雪夫界的推广，同时又是吾妻不等式和McDiarmid不等式（还没给出标准的中文翻译2333）。霍夫丁不等式是机器学习的基础理论。
2. 定义
假设\boldsymbol{X}_1,\boldsymbol{X}_2,\cdots,\boldsymbol{X} _N 是独立随机变量，且 \boldsymbol{X}_i \in [a_i,b_i] ,i = 1,2,\cdots，N；\bar{\boldsymbol{X}} 是\boldsymbol{X}_1,\boldsymbol{X}_2,\cdots,\boldsymbol{X}_N 的经验均值，即 \bar{\boldsymbol{X}} = \frac{1}{N} \sum_{i=1}^N \boldsymbol{X}_i，则对任意t \gt 0，以下霍夫丁不等式成立：
\begin{array}{c}
P[\bar{\boldsymbol{X}} - E(\bar{\boldsymbol{X}}) \geq t] \leq \exp{(-\frac{2N^2t^2}{\sum_{i=1}^N(b_i-a_i)^2})} \\
P[E(\bar{\boldsymbol{X}}) - \bar{\boldsymbol{X}} \geq t] \leq \exp{(-\frac{2N^2t^2}{\sum_{i=1}^N(b_i-a_i)^2})} \\
\end{array}
证明
由霍夫丁引理可得
\begin{array}{cc}
E(e^{s(\boldsymbol{X}-E(\boldsymbol{X}))}) \leq \exp{(\frac{1}{8} s^2 (b_i - a_i)^2)} & (1 \leq i \leq n)
\end{array}
令 \boldsymbol{S}_n = \boldsymbol{X}_1 + \boldsymbol{X}_2 + \cdots + \boldsymbol{X}_n，对于 \forall s,t \gt 0，可得
\begin{array}{c}
P(\boldsymbol{S}_n - E(\boldsymbol{S}_n) \geq t) = P(e^{s(S_n - E(S_n))} \geq e^{st})
\end{array}
进一步根据马尔可夫不等式和 \boldsymbol{X}_i之间的独立性可得
\begin{array}{rl}
P(e^{s(S_n - E(S_n))} \geq e^{st}) & \leq e^{-st} E(e^{s(\boldsymbol{S}_n-E(\boldsymbol{S}_n))}) \\
& = e^{-st} \prod_{i=1}^n E(e^{s(\boldsymbol{X}_i-E(\boldsymbol{X}_i))}) \\
& \leq e^{-st} \prod_{i=1}^n e^{\frac{s^2(b_i-a_i)^2}{8}} \\
& = \exp{(-st + \frac{1}{8} s^2 \sum_{i=1}^n (b_i - a_i)^2)}
\end{array}
令 2g(s) = -st + \frac{s^2}{8} \sum_{i=1}^n (b_i - a_i)^2，则 g(s) 为关于 s 的二次函数，从而易得
\begin{array}{c}
s = \frac{4t}{\sum_{i=1}^n (b_i - a_i)^2}
\end{array}
为 g(s)的最小值点。由于
\begin{array}{c}
P(e^{s(S_n - E(S_n))} \geq e^{st}) \leq \exp{(-st + \frac{1}{8} s^2 \sum_{i=1}^n (b_i - a_i)^2)}
\end{array}
对 \forall s \gt 0都成立，因此当 s 取 g(s) 的最小值点时，得到 P(e^{s(S_n - E(S_n))} \geq e^{st}) 的紧上界，即
\begin{array}{c}
P(e^{s(S_n - E(S_n))} \geq e^{st}) \leq \exp{(-\frac{2t^2}{\sum_{i=1}^n (b_i - a_i)^2})}
\end{array}
最终简单变换后可得 P[\bar{\boldsymbol{X}} - E(\bar{\boldsymbol{X}}) \geq t] \leq \exp{(-\frac{2N^2t^2}{\sum_{i=1}^N(b_i-a_i)^2})}。另一个不等式 )P[E(\bar{\boldsymbol{X}}) - \bar{\boldsymbol{X}} \geq t] \leq \exp{(-\frac{2N^2t^2}{\sum_{i=1}^N(b_i-a_i)^2})}同理可证。
附录
参考资料：
