接着上一节的那些不等式们(一)-Markov与Chebyshev不等式
本节将学习Hoeffding不等式。

Hoeffding不等式

作用与Chebyshev不等式类似，但区间更紧致(增加了独立性约束)

Hoeffding不等式
设 $Y_1,...Y_n$ 相互独立，且 $E(Y_i) = 0$ ，且 $a_i \leq Y_i \leq b_i$ ，令 $\epsilon > 0$ ，则对任意 $t>0$ ，
$P(\sum_{i=1}^{n}Y_i \geq \epsilon) \leq e^{-t\epsilon} \prod_{i=1}^{n}e^{t^2(b_i-a_i)^2/8}$

证明过程如下：
$\begin{eqnarray} P \Bigg( \sum_{i=1}^{n}Y_i \geq \epsilon \Bigg) &=& P \Bigg( t \sum_{i=1}^{n}Y_i \geq t \epsilon \Bigg ) \\ &=& P \Bigg(e^{t \sum \limits_{i=1}^{n}Y_i} \geq e^{t \epsilon} \Bigg) \\ & \leq & e^{-t \epsilon} E\Bigg(e^{t \sum \limits_{i=1}^{n}Y_i} \Bigg) \qquad (Markov 不等式) \\ &=& e^{-t \epsilon} \prod_{i=1}^{n} E \Bigg( e^{t Y_i} \Bigg) \qquad (Y_1,...Y_n相互独立，期望的性质) \end{eqnarray}$

对于凸函数 $f(x) = e^x$ ，对于任意 $\alpha \in [0, 1]$ ，和 $x \in [a, b]$ 都满足
$f(x) \leq \alpha f(a) + (1 - \alpha)f(b)$
如图所示：

因为 $a_i \leq Y_i \leq b_i$ ，即 $Y_i \in [a_i, b_i]$ ，令 $\alpha = \frac{b_i-Y_i }{b_i - a_i} \in [0, 1]$ ，则

$e^{tY_i} \leq \frac{(b_i - Y_i)}{(b_i - a_i)} e^{ta_i} + \frac{(Y_i - a_i)}{(b_i - a_i)} e^{tb_i}$

又因为 $E(Y_i) = 0$ ，对两边同时取期望，

$E(e^{tY_i}) \leq \frac{b_i - E(Y_i)}{(b_i - a_i)} e^{ta_i} + \frac{E(Y_i) - a_i}{(b_i - a_i)} e^{tb_i} = \frac{b_i}{(b_i - a_i)} e^{ta_i} - \frac{a_i}{(b_i - a_i)} e^{tb_i}$
记 $u = t(b_i - a_i)$ ，和 $\gamma = -a_i/b_i - a_i$ ，可以将上式右边写作 $e^{ -\gamma u + log(1 - \gamma + \gamma e^u)}$

记为 $e^{g(u)}$ ，我们对 $g(u)$ 作泰勒展开
$g(u) = \frac{g(0)}{0!}(u-0)^0 + \frac{g^{'}(0)}{1!}(u-0)^1 + \frac{g^{''}(0)}{2!}(u-0)^2 + o(u^2)$

易得 $g(0) = g^{'}(0) = 0$ ，而
$g^{''}(u) = \frac{\gamma(1-\gamma)e^u}{(1- \gamma + \gamma e^u)^2}$

得到 $g^{''}(0) = \gamma(1-\gamma) \leq 1/4$ ，带入泰勒展开式，得到
$g(u) = \frac{g^{''}(0)}{2!}(u-0)^2 + o(u^2) \leq \frac{1/4}{2!}(u-0)^2 = \frac{u^2}{8} = \frac{1}{8}t^2(b_i - a_i)^{2}$

因此，
$E(e^{tY_i}) \leq e^{g(u)} \leq e^{t^2(b_i - a_i)^{2}/8}$
不等式得证。

Hoeffding不等式
设 $Y_1,...Y_n$ 相互独立，且 $E(Y_i) = 0$ ，且 $a_i \leq Y_i \leq b_i$ ，令 $\epsilon > 0$ ，则对任意 $t>0$ ，
$P(\sum_{i=1}^{n}Y_i \geq \epsilon) \leq e^{-t\epsilon} \prod_{i=1}^{n}e^{t^2(b_i-a_i)^2/8}$
令 $X_1,...X_n \backsim Bernoulli(p)$ ，则对任意 $\epsilon > 0$ ，有
$P(|\overline{X} - p| > \epsilon) \leq 2e^{-2n\epsilon^2} \qquad (2)$
其中 $\overline{X_n} = \frac{1}{n}\sum_{i=1}^{n}X_i$

对于(2)式证明如下：
令 $Y_i = \frac{1}{n}(X_i - p)$ ，有 $E(Y_i) = 0$ ，且有
$\sum_{i=1}^{n} Y_i = \frac{1}{n} \sum_{i=1}^{n} (X_i - p) = \frac{1}{n}\sum_{i=1}^{n} X_i - p = \overline{X_n} - p$

又有 $a \leq Y_i \leq b$ ，因为 $X_1,...X_n \backsim Bernoulli(p)$ ，所以 $X_i$ 的取值只能是 $0$ ， $1$ ，因此 $a = - p/n$ ， $b = (1-p)/n$ ，那么 $(b-a)^2 = 1/n^2$
$P(\overline{X} - p > \epsilon) = p(\sum_{i=1}^{n} Y_i > \epsilon) \leq e^{-t\epsilon}e^{t^2/(8n)} \qquad (t>0)$

取 $t = 4n\epsilon$ ，我们得到 $P(\overline{X} - p > \epsilon) \leq e^{-2n\epsilon^2}$
同理可得 $P(\overline{X} - p < -\epsilon) \leq e^{-2n\epsilon^2}$
因此
$P(|\overline{X} - p| > \epsilon) \leq 2e^{-2n\epsilon^2}$