ml-Hoeffding's Inequality

Hoeffding’s Inequality

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

• 当n 很大时，抽样的期望$v$可以逼近样本本身的期望值$\mu$（一般是未知），例如：

  $$n=1000,\mathrm{误}\mathrm{差}ϵ=0.05，\mu -0.05\le v\le \mu +0.05,\mathbb{P}(|v-\mu |\ge ϵ)\le 2e^{-2\ast 1000\ast {0.05}^2}=0.013$$

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

常用的不等式证明

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

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

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

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

• $P[|X-\mu |\ge ϵ]={\int }_{|X-\mu |\ge ϵ}f(X)dX\le {\int }_{|X-\mu |\ge ϵ}\frac{|X-\mu {|}^2}{{ϵ}^2}f(X)dX\le \frac{1}{{ϵ}^2}{\int }_{-\mathrm{\infty }}^{\mathrm{\infty }}(X-\mu {)}^{2}f(X)dX=\frac{{\sigma }^2}{{ϵ}^2}$

引理 1

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

$P[t\ge \alpha ]={\int }_{t\ge \alpha }f(t)dt\le {\int }_{t\ge \alpha }\frac{t}{\alpha }f(t)dt\le \frac{1}{\alpha }{\int }_0^{\mathrm{\infty }}f(t)dt=\frac{E(t)}{\alpha }$

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

引理$2^{[1]}$

$$\begin{gathered} X_1,...,X_n\mathrm{是}\mathrm{独}\mathrm{立}\mathrm{同}\mathrm{分}\mathrm{布}\mathrm{的}\mathrm{随}\mathrm{机}\mathrm{变}\mathrm{量},\mathbb{P}(X_i=1)=\frac{1}{2}+a,\mathbb{P}(X_i=-1)=\frac{1}{2}-a \\ \mathrm{那}\mathrm{么}\mathbb{P}(\bar{X}-\mathbb{E}[\bar{X}]\ge t)\le e^{-\frac{n{t}^2}{2}} \end{gathered}$$

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

证明：首先计算$\mathbb{E}[X_i],\mathbb{E}[\bar{X}]$

$$\begin{gathered} \mathbb{E}[X_i]=(\frac{1}{2}+a)\times 1+(\frac{1}{2}-a)\times (-1)=2a \\ \mathbb{E}[\bar{X}]=\mathbb{E}[X_i]=2a \end{gathered}$$

所以原不等式可以转化为

$$\mathbb{P}(\bar{X}-2a\ge t)\le e^{-\frac{n{t}^2}{2}}$$

以及有如下等价关系

$$\begin{gathered} \mathbb{P}(\bar{X}-2a\ge t)\le e^{-\frac{n{t}^2}{2}}\iff \\ \mathbb{P}(\sum _{i=1}^n{X}_i\ge n(t+2a))\le e^{-\frac{n{t}^2}{2}}\iff \\ \mathbb{P}(e^{s\sum _{i=1}^n{X}_i}\ge e^{sn(t+2a)})\le e^{-\frac{n{t}^2}{2}}(s>0) \end{gathered}$$

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

$$\mathbb{P}(e^{s\sum _{i=1}^n{X}_i}\ge e^{sn(t+2a)})\le \frac{\mathbb{E}[e^{s\sum _{i=1}^n{X}_i}]}{e^{sn(t+2a)}}$$

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

$$\frac{\mathbb{E}[e^{s\sum _{i=1}^n{X}_i}]}{e^{sn(t+2a)}}=\frac{1}{e^{snt}}\times \frac{(\mathbb{E}[e^{s{X}_1}]{)}^n}{e^{2asn}}=\frac{1}{e^{snt}}\times (\frac{\mathbb{E}[e^{s{X}_1}]}{e^{2as}}{)}^n$$

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

$$\frac{\mathbb{E}[e^{s{X}_1}]}{e^{2as}}=\frac{e^s(\frac{1}{2}+a)+e^{-s}(\frac{1}{2}-a)}{e^{2as}}=\frac{\frac{1}{2}(e^s+e^{-s})+a(e^s-e^{-s})}{e^{2as}}$$

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

$$f(a)=\frac{m+na}{e^{2as}}$$

对其取对数可得

$$g(a)=\text{ln}f(a)=\text{ln}(m+na)-2as$$

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

$$\begin{gathered} g^{{}^{\prime }}(a)=\frac{n}{m+na}-2s=0 \\ a=\frac{n-2ms}{2ns} \\ {g}^{{}^{″}}(a)=-\frac{n^2}{m+na}<0 \end{gathered}$$

所以当$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{1}{2}]$的关系，我们先判断$\frac{n-2ms}{2ns}$是否大于$0$，因为$s>0$，所以分母$2ns=2s(e^s-e^{-s})>0$，只要考虑分子即可

$$\begin{gathered} h(s)=n-2ms=e^s-e^{-s}-s(e^s+e^{-s}) \\ {h}^{{}^{\prime }}(s)=e^s+e^{-s}-(e^s+e^{-s})-s(e^s-e^{-s})=-s(e^s-e^{-s})<0 \\ h(s)=n-2ms<h(0)=0 \end{gathered}$$

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

$$\begin{gathered} g(a)\le g(0) \\ f(a)\le f(0)=m=\frac{1}{2}(e^s+e^{-s}) \end{gathered}$$

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

$$\begin{gathered} e^s=\sum _{i=0}^{+\mathrm{\infty }}\frac{s^i}{i!},e^{-s}=\sum _{i=0}^{+\mathrm{\infty }}\frac{(-s{)}^i}{i!} \\ \frac{1}{2}(e^s+e^{-s})=\frac{1}{2}\sum _{i=0}^{+\mathrm{\infty }}\frac{(1+(-1{)}^i)}{i!}{s}^i=\sum _{k=0}^{+\mathrm{\infty }}\frac{s^{2k}}{(2k)!} \end{gathered}$$

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

$$(2k)!=1\times 2\times ...\times k\times (k+1)\times ...\times 2k\ge k!\times \underset{k\mathrm{个}2}{\underbrace{2\times ...\times 2}}=2^{k}k!$$

将这个式子带入原式可得

$$\frac{1}{2}(e^s+e^{-s})=\sum _{k=0}^{+\mathrm{\infty }}\frac{s^{2k}}{(2k)!}\le \sum _{k=0}^{+\mathrm{\infty }}\frac{(s^2{)}^k}{k!2^k}=\sum _{k=0}^{+\mathrm{\infty }}\frac{(\frac{s^2}{2}{)}^k}{k!}=e^{\frac{s^2}{2}}$$

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

$$\begin{gathered} \frac{\mathbb{E}[e^{s{X}_1}]}{e^{2as}}\le e^{\frac{s^2}{2}} \\ \frac{\mathbb{E}[e^{s\sum _{i=1}^n{X}_i}]}{e^{sn(t+2a)}}=\frac{1}{e^{snt}}\times (\frac{\mathbb{E}[e^{s{X}_1}]}{e^{2as}}{)}^n\le \frac{1}{e^{snt}}\times e^{\frac{n{s}^2}{2}}=(e^{\frac{s^2}{2}-st}{)}^n \end{gathered}$$

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

$$\begin{gathered} \frac{\mathbb{E}[e^{s\sum _{i=1}^n{X}_i}]}{e^{sn(t+2a)}}\le (e^{-\frac{t^2}{2}}{)}^n=e^{\frac{-n{t}^2}{2}} \\ \mathbb{P}(\bar{X}-\mathbb{E}[\bar{X}]\ge t)=\mathbb{P}(e^{s\sum _{i=1}^n{X}_i}\ge e^{sn(t+2a)})\le \frac{\mathbb{E}[e^{s\sum _{i=1}^n{X}_i}]}{e^{sn(t+2a)}}\le e^{-\frac{n{t}^2}{2}} \end{gathered}$$

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

$$\mathbb{P}(\bar{X}-\mathbb{E}[\bar{X}]\le -t)\le e^{-\frac{n{t}^2}{2}}$$

这是因为

$$\mathbb{P}(\bar{X}-\mathbb{E}[\bar{X}]\le -t)=\mathbb{P}(-\bar{X}-\mathbb{E}[-\bar{X}]\ge t)$$

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

$$\mathbb{P}(\bar{X}-E[\bar{X}]\le -t)=\mathbb{P}(-\bar{X}-E[-\bar{X}]\ge t)\le e^{-\frac{n{t}^2}{2}}$$

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

$$\mathbb{P}(|\bar{X}-\mathbb{E}[\bar{X}]|\ge t)=\mathbb{P}(\bar{X}-\mathbb{E}[\bar{X}]\le -t)+\mathbb{P}(\bar{X}-\mathbb{E}[\bar{X}]\ge t)\le 2e^{-\frac{n{t}^2}{2}}$$

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

Hoeffding不等式的证明

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

$$\begin{gathered} Y_i=2X_i-1 \\ \mathbb{P}(Y_i=1)=p,\mathbb{P}(Y_i=-1)=1-p \end{gathered}$$

从而

$$\bar{Y}=2\bar{X}-1,\mathbb{E}[\bar{Y}]=2\mathbb{E}[\bar{X}]-1$$

所以

$$\begin{array}{rl}\mathbb{P}(|\bar{X}-\mathbb{E}[\bar{X}]|\ge t)& =\mathbb{P}(|2\bar{X}-2\mathbb{E}[\bar{X}]|\ge 2t)\\ & =\mathbb{P}(|2\bar{X}-1-(2\mathbb{E}[\bar{X}]-1)|\ge 2t)\\ & =\mathbb{P}(|\bar{Y}-\mathbb{E}[\bar{Y}]|\ge 2t)\end{array}$$

由引理2的推论可知可知

$$\mathbb{P}(|\bar{Y}-\mathbb{E}[\bar{Y}]|\ge 2t)\le 2e^{-\frac{n(2t{)}^2}{2}}=2e^{-2n{t}^2}$$

从而

$$\mathbb{P}(|\bar{X}-\mathbb{E}[\bar{X}]|\ge t)=\mathbb{P}(|\bar{Y}-\mathbb{E}[\bar{Y}]|\ge 2t)\le 2e^{-2n{t}^2}$$

从而结论得证。

参考：

[1] 霍夫丁不等式证明