机器学习——霍夫丁（Hoeffding）不等式证明
马尔可夫不等式
结论：
对于任意非负随机变量$X$，$\forall \epsilon>0$，有：
$\displaystyle P(X\ge\epsilon)\le\frac{E(X)}{\epsilon}$
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。切比雪夫不等式是它的特例。
证明：
$ \begin{align*} E(X) &= \int_{0}^{\infty}xf(x)dx\\ &\ge \int_{\epsilon}^{\infty}xf(x)dx\\ &\ge \int_{\epsilon}^{\infty}\epsilon f(x)dx\\ &=\epsilon P(X\ge \epsilon)\\ \end{align*}$
把$\epsilon$除过去，得证。离散情况一样。
霍夫丁不等式引理
结论：
对于随机变量$X$，$P(X\in [a,b]) = 1,E(X)=0$，有：
$E(e^{sX})\le e^{s^2(b-a)^2/8}$
证明：
因$e^{sX}$是关于$X$的凸函数，由凸函数性质：
$\displaystyle e^{sX}\le \frac{b-X}{b-a}e^{sa}+\frac{X-a}{b-a}e^{sb}$
于是对$X$取期望，有：
$ \begin{align*} \displaystyle E(e^{sX}) &\le \frac{b-E(X)}{b-a}e^{sa}+\frac{E(X)-a}{b-a}e^{sb}\\ & = \frac{b}{b-a}e^{sa}-\frac{a}{b-a}e^{sb}\\ & = \left(-\frac{a}{b-a}\right)e^{sa}\left(-\frac{b}{a}+e^{sb-sa}{}\right)\\ \end{align*}$
因为$E(X)=0$，$X\in [a,b]$，而$a,b$都为0的情况没有讨论的意义，所以有$a<0,b>0$。令$\displaystyle\theta = -\frac{a}{b-a}>0$，则上式变为：
$ \begin{align*} \displaystyle E(e^{sX}) &\le \theta e^{-s\theta (b-a)}\left(\frac{1}{\theta}-1+e^{s(b-a)}\right)\\ &=(1-\theta + \theta e^{s(b-a)})e^{-s\theta(b-a)}\\ \end{align*}$
因为
$ \begin{gather} \displaystyle 1-\theta+\theta e^u = \theta(\frac{1}{\theta}-1+e^u) = \theta(-\frac{a}{b}+e^u)>0 \label{} \end{gather} $
所以不等式可以变为：
$\displaystyle E(e^{sX})\le e^{\ln(1-\theta + \theta e^{s(b-a)})}e^{-s\theta(b-a)}$
令$u = s(b-a)$：
$E(e^{sX})\le e^{\ln(1-\theta+\theta e^u)-\theta u}$
定义$\varphi:R\to R,\varphi(u)= \ln(1-\theta+\theta e^u)-\theta u$。由$(1)$式可得这个函数是良定义的，也就是$\varphi(u)$的$\ln$并不限制$u$的取值。得：
$E(e^{sX})\le e^{\varphi(u)}$
由泰勒中值定理，$\exist\xi\in [0,u]$使
$\displaystyle\varphi(u)=\varphi(0)+u\varphi'(0)+\frac{1}{2}u^2\varphi''(\xi)$
其中：
$ \begin{equation} \begin{array}{lcl} \varphi(0) = 0 \\ \varphi'(0)= \left.\left(\frac{\theta e^u}{1-\theta+\theta e^u}-\theta\right)\right|_{u=0}=0 \\ \begin{split} \varphi''(\xi) &= \frac{\theta e^{\xi}(1-\theta+\theta e^{\xi})-\theta^2 e^{2\xi}}{(1-\theta+\theta e^{\xi})^2} \\ &=\frac{\theta e^{\xi}}{1-\theta+\theta e^{\xi}}(1-\frac{\theta e^{\xi}}{1-\theta+\theta e^{\xi}})\\ &=t(1-t)\le\frac{1}{4} \end{split} \end{array} \end {equation} $
因此有：
$\displaystyle\varphi(u)\le 0+0+\frac{1}{2}u^2\times\frac{1}{4} = \frac{1}{8}s^2(b-a)^2$
于是
$E(e^{sX})\le e^{s^2(b-a)^2/8}$
霍夫丁不等式
结论
wiki的定义：
霍夫丁不等式适用于有界的随机变量。设有两两独立的一系列随机变量$X_{1},\dots ,X_{n}$。假设对所有的$X_{i}$都是几乎有界（看成有界就好了）的变量，即满足：
$\displaystyle P(X_{i}\in [a_{i},b_{i}])=1$
那么这n个随机变量的经验期望（均值）：
$\displaystyle \overline{X} = \frac{X_1+\cdots+X_n}{n}$
满足以下不等式：
$\displaystyle P(\overline{X}-E(\overline{X})\ge t) \le \exp\left(- \frac{2t^2n^2}{\sum_{i=1}^{n}(b_i-a_i)^2}\right)$
$\displaystyle P(|\overline{X}-E(\overline{X})|\ge t) \le 2 \exp\left(- \frac{2t^2n^2}{\sum_{i=1}^{n}(b_i-a_i)^2}\right)$
证明
对于$X_1,X_2,...,X_n$，$n$个相互独立的随机变量（wiki里面说是两两独立，我感觉两两独立$X_i$乘积的期望应该不能分离成期望的乘积，这里我不太明确），$P(X_i\in [a_i,b_i])=1,1\le i\le n$，令
$\displaystyle S_n=\sum\limits_{i=1}^{n}X_i$
取$s>0,t>0$，由马尔科夫不等式得：
$\begin{align*} P(S_n-E(S_n)\ge t) &= P(e^{s(S_n-E(S_n))}\ge e^{st})\\ &\le e^{-st}E(e^{s(S_n-E(S_n))}) \\ &= e^{-st}\prod\limits_{i=1}^{n}E(e^{s(X_i-E(X_i))}) \end {align*}$
再由引理得：
$ \begin{align*} P(S_n-E(S_n)\ge t) &\le e^{-st}\prod\limits_{i=1}^{n} e^{\frac{s^2(b_i-a_i)^2}{8}}\\ &=\exp(-st+\frac{1}{8}s^2\sum\limits_{i=1}^n(b_i-a_i)^2) \end {align*}$
到这一步，不等式中还多出了一个$s$，因为$\forall s>0$，都有以上不等式成立，因此取右边关于$s$的二次函数的最小值。令
$\displaystyle g(s)=-st+\frac{1}{8}s^2\sum\limits_{i=1}^n(b_i-a_i)^2$
求$g'(s)=0$，得：
$\displaystyle s = \frac{4t}{\sum_{i=1}^{n}(b_i-a_i)^2}$
于是：
$\displaystyle P(S_n-E(S_n)\ge t) \le \exp\left(- \frac{2t^2}{\sum_{i=1}^{n}(b_i-a_i)^2}\right)$
变换成$X_i$的均值$\overline{X}$，也就是：
$\displaystyle P(\overline{X}-E(\overline{X})\ge t) \le \exp\left(- \frac{2t^2n^2}{\sum_{i=1}^{n}(b_i-a_i)^2}\right)$
取反后依然成立：
$\displaystyle P(E(\overline{X})-\overline{X}\ge t) \le \exp\left(- \frac{2t^2n^2}{\sum_{i=1}^{n}(b_i-a_i)^2}\right)$
合到一起：
$\displaystyle P(|\overline{X}-E(\overline{X})|\ge t) \le 2 \exp\left(- \frac{2t^2n^2}{\sum_{i=1}^{n}(b_i-a_i)^2}\right)$
得证。
