Hoeffding’s Inequality

霍夫丁不等式 ($\mathbb P(\Big|v -\mu\Big|\ge \epsilon ) \le 2e^{-2n\epsilon^2}$ ) 的意义:

  • 当n 很大时,抽样的期望$v$可以逼近样本本身的期望值$\mu$(一般是未知),例如:

    注意这里只是概率上说明$v$ 和$\mu$的误差关系,真实情况$v$ 的取值是随意的。所以霍夫丁不等式只是告诉我们在一定误差范围内,取得我们想要的$\mu$的估计值$v$的概率可能性,而不是一定。(关于误差的介绍以后会相继推出)

常用的不等式证明

$\sigma$和$\mu$是样本本身的方差和均值,$X$是随机变量,$\epsilon$是任意整数。

$\mathbb E (x) = \int_{-\infty}^{\infty}(x-\mu)f(x)dx =\mu$

$\mathbb D (x) = \int_{-\infty}^{\infty}(x-\mu)^2f(x)dx = \sigma^2$

  • 切比雪夫不等式为: $ \Large \mathbb P [|X-\mu|\ge\epsilon] \le \Large \frac{\sigma^2}{\epsilon^2}$

  • $ \Large P [|X-\mu|\ge\epsilon] =\Large \int_{|X-\mu|\ge\epsilon}f(X)dX\le\int_{|X-\mu|\ge\epsilon}\frac{|X-\mu|^2}{\epsilon^2}f(X)dX \ \Large \le\frac{1}{\epsilon^2}\int_{-\infty}^{\infty}(X-\mu)^2f(X)dX=\frac{\sigma^2}{\epsilon^2}$

引理 1

同理可以证明马尔科夫不等式,$t$为非负随机变量:

$\Large P [t\ge\alpha] =\Large \int_{t\ge\alpha}f(t)dt\le\int_{t\ge\alpha}\frac{t}{\alpha}f(t)dt\le\frac{1}{\alpha}\int_{0}^{\infty}f(t)dt=\frac{E(t)}{\alpha}$

即: $\Large P [t\ge\alpha] \le \frac{E(t)}{\alpha}$

引理$2^{[1]}$

可以看到这个结论和我们需要证明的结论形式非常类似,但是相对于原来的命题,这个结论更加“对称”一些,这是因为$-1,+1$以及$\frac 1 2+a,\frac 1 2-a$都比较对称,后面证明中可以看到,这样的对称性可以使得证明更加方便,下面来证明这个结论。

证明:首先计算$\mathbb E[X_i],\mathbb E[\overline X]$

所以原不等式可以转化为

以及有如下等价关系

这里$s$是任意正数,接下来使用引理1

我们现在对$\frac{\mathbb E[e^{s\sum_{i=1}^nX_i}]}{e^{sn(t+2a )}}$进行处理,注意$X_1,…,X_n$独立同分布

接下来我们处理$\frac{\mathbb E[e^{sX_1}]}{e^{2as }}$,利用$\mathbb P(X_i=1)=\frac 1 2+a,\mathbb P(X_i=-1)=\frac 1 2-a$

记$m=\frac12(e^s+e^{-s}),n=e^{s}-e^{-s}$,所以上式可以改写为

对其取对数可得

研究$f(a)$的极值只要研究$g(a)$的极值即可

所以当$a=\frac{n-2ms}{2ns}$时,$g(a)$取极大值,并且$a\le \frac{n-2ms}{2ns}$时单调递增,$a>\frac{n-2ms}{2ns}$时单调递减,但是注意这里的$a\in [0,\frac 1 2]$,所以还要看$\frac{n-2ms}{2ns}$与$[0,\frac 12 ]$的关系,我们先判断$\frac{n-2ms}{2ns}$是否大于$0$,因为$s>0$,所以分母$2ns=2s(e^s-e^{-s})>0$,只要考虑分子即可

所以$\frac{n-2ms}{2ns}<0$,从而$g(a)$在$[0,\frac 1 2]$上单调递减,因此

所以现在只要处理$\frac12(e^s+e^{-s})$即可,对$e^s,e^{-s}$分别使用泰勒展开

对$(2k)!$稍作变形

将这个式子带入原式可得

把以上几点结合起来可以得到

由于$s$为任意大于$0$的数,取$s=t$,从而

所以结论得证。这里再补充一点,我们还有以下对称的结论

这是因为

因为$\mathbb P(X_i=1)=\frac 1 2+a,\mathbb P(X_i=-1)=\frac 1 2-a$,所以$-X_i$也是形式一致的随机变量,由引理2可知

把以上两者结合有以下推论

最后就利用上述引理2及其推论证明Hoeffding不等式

Hoeffding不等式的证明

Hoeffding不等式中的随机变量$X_1,…,X_n$满足$\mathbb P(X_i=1)=p,\mathbb P(X_i=0)=1-p$,对其稍作变形,转化为引理2的形式

从而

所以

由引理2的推论可知可知

从而

从而结论得证。

参考:

[1] 霍夫丁不等式证明