美文网首页
Hoeffding 不等式

Hoeffding 不等式

作者: 热爱生活的大川 | 来源:发表于2020-09-10 15:46 被阅读0次

基础准备

1.定比分点公式

点P为AB上一点，则
\overrightarrow{OP} = \frac{BP}{AB}\overrightarrow{OA} + \frac{AP}{AB}\overrightarrow{OB}
设\lambda = \frac{ AP }{ AB }，则
p = \frac{a+\lambda b}{1+\lambda}

证明：
\begin{aligned} \overrightarrow{OP} &= \overrightarrow{OA} + \overrightarrow{AP} \\ &= \overrightarrow{OA} + \frac{AP}{AB}\overrightarrow{AB} \\ &= \overrightarrow{OA} - \frac{AP}{AB}\overrightarrow{OA} + \frac{AP}{AB}\overrightarrow{OB} \\ &= \frac{BP}{AB}\overrightarrow{OA} + \frac{AP}{AB}\overrightarrow{OB} \end{aligned}

2.凸函数性质

设x \in [a,b]，f(x)为凸函数，则
f(x) \leq \frac{b-x}{b-a}f(a) + \frac{x-a}{b-a}f(b)

3.markov不等式

P(x \geq a) \leq \frac{E(X)}{a}

证明：
\begin{aligned} E(X) &= \int_{-\infty}^{+\infty} xf(x)dx \\ & \geq \int_{a}^{+\infty} xf(x)dx \\ & \geq a\int_{a}^{+\infty} f(x)dx \\ & \geq aP(x \geq a) \end{aligned}

Hoeffding 不等式

取随机变量Z_1,Z_2,...,Z_m，令\overline{Z}=\frac{1}{m}\sum_{i=1}^{m}Z_i。若满足

  1. Z_1,Z_2,...,Z_m独立同分布
  2. E(\overline{Z})=\mu
  3. P[a \leq Z_i \leq b]=1，\forall{i} \in 1...m

则有
P(|\frac{1}{m}\sum_{1}^{m}Z_i-\mu| \geq \epsilon) \leq 2e^{\frac{-2m \epsilon^2}{(b-a)^2}}

其描述了随机变量算数均值\overline{Z}与其期望E(\overline{Z})之间的概率逼近关系。

1.Hoeffding 引理

lemma：设X \in [a,b]是一个随机变量，若E(X)=0，则对\forall \lambda，有
E(e^{\lambda X}) \leq e^{\frac{\lambda^2(b-a)^2}{8}}

证明：

1.化简不等式
由凸函数性质
e^{\lambda X} \leq \frac{b-X}{b-a}e^{\lambda a} + \frac{X-a}{b-a}e^{\lambda b}
两边取期望
E(e^{\lambda X}) \leq \frac{b-E(X)}{b-a}e^{\lambda a} + \frac{E(X)-a}{b-a}e^{\lambda b}
化简
E(e^{\lambda X}) \leq \frac{b}{b-a}e^{\lambda a} + \frac{-a}{b-a}e^{\lambda b}
从而只需证明
\frac{ b }{ b-a }e^{\lambda a} + \frac{ -a }{ b-a }e^{\lambda b} \leq e^{\frac{ \lambda^2(b-a)^2 }{ 8 }}
整理得
e^{\lambda a}(\frac{b}{b-a}-\frac{a}{b-a}e^{\lambda (b-a)}) \leq e^{\frac{\lambda^2(b-a)^2}{8}}
尽量去掉指数，即
\lambda a + \ln(\frac{ b }{ b-a }-\frac{ a }{ b-a }e^{ \lambda (b-a) }) \leq \frac{ \lambda^2(b-a)^2 }{8}
令h=\lambda (b-a)，p=\frac{a}{b-a}，继续整理得
hp + \ln(1+p-pe^h) \leq \frac{h^2}{8}

2.采用导数极值的方法证明
构造函数
f(h) = hp + \ln(1+p-pe^h) - \frac{h^2}{8}
其中f(0) = 0
求导
f'(h) = p + \frac{-pe^h}{1+p-pe^h}-\frac{h}{4}
f'(0) = 0
f''(h) = \frac{-pe^h(1+p)}{(1+p-pe^h)^2}-\frac{1}{4}
f''(0) = 0
令m=1+p，n=-pe^h，则有
\begin{aligned} f''(h) &= \frac{nm}{(m+n)^2}-\frac{1}{4} \\ &= \frac{1}{\frac{m}{n}+\frac{n}{m}+2}-\frac{1}{4} \\ & \leq \frac{1}{2\sqrt{\frac{1}{\frac{m}{n}*\frac{n}{m}}}+2}-\frac{1}{4} \\ & \leq 0 \end{aligned}
当h \geq 0时，有f'(h) \leq f'(0) = 0，进而有f(h) \leq f(0) = 0；
当h < 0时，有f'(h) \geq f'(0) = 0，进而有f(h) \leq f(0) = 0。
得证。

2.Hoeffding 不等式的证明

令X_i=Z_i-\mu，满足Hoeffding引理条件E(X_i)=0。

先证

P(\frac{1}{ m }\sum_{1}^{m}Z_i-\mu \geq \epsilon) \leq e^{\frac{ -2m\epsilon^2 }{ (b-a)^2 }}
对\forall{\lambda}
\begin{aligned} P(\frac{1}{m}\sum_{1}^{m}Z_i-\mu \geq \epsilon) &= P(\overline{X} \geq \epsilon) \\ &= P(e^{\lambda\overline{X}} \geq e^{\lambda\epsilon}) \\ &\leq \frac{1}{e^{\lambda\epsilon}}\prod_{i=1}^{m}E(e^{\frac{\lambda}{m}X_i}) \\ &\leq \frac{1}{e^{\lambda\epsilon}}e^{\frac{\lambda^2(b-a)^2}{8m}} \\ &= e^{\frac{\lambda^2(b-a)^2}{8m}-\lambda\epsilon} \end{aligned}
对其中的\lambda二次函数取最值，即令\lambda=\frac{4m\epsilon}{(b-a)^2}，可得证。

再证

P(\frac{1}{m}\sum_{1}^{m}Z_i-\mu \leq -\epsilon) \leq e^{\frac{-2m\epsilon^2}{(b-a)^2}}
同理，对\forall{\lambda}
\begin{aligned} P(\frac{1}{m}\sum_{1}^{m}Z_i-\mu \leq -\epsilon) &= P(-\overline{X} \geq \epsilon) \\ &= P(e^{-\lambda\overline{X}} \geq e^{\lambda\epsilon}) \\ &\leq \frac{1}{e^{\lambda\epsilon}}\prod_{i=1}^{m}E(e^{-\frac{\lambda}{m}X_i}) \\ &\leq \frac{1}{e^{\lambda\epsilon}}e^{\frac{\lambda^2(b-a)^2}{8m}} \\ &= e^{\frac{\lambda^2(b-a)^2}{8m}-\lambda\epsilon} \\ &\leq e^{\frac{-2m\epsilon^2}{(b-a)^2}} \end{aligned}

于是，最终可证得
P(|\frac{1}{m}\sum_{1}^{m}Z_i-\mu| \geq \epsilon) \leq 2e^{\frac{-2m \epsilon^2}{(b-a)^2}}
。

相关文章

网友评论

      本文标题：Hoeffding 不等式

      本文链接：https://www.haomeiwen.com/subject/svdpektx.html

      延伸阅读

      深度阅读

      • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

      栏目导航

      热点阅读

      关于我们|服务条款|联系我们|Hoeffding 不等式|投稿指南|网站地图|RSS订阅|排版工具|手机版

      提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

      Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

      备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

      本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

      所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！