霍夫丁不等式及其他相关不等式证明
发布日期:2021-09-30 09:33:31 浏览次数:5 分类:技术文章

本文共 5622 字,大约阅读时间需要 18 分钟。

霍夫丁不等式及其他相关不等式证明


周志华老师的书和台大的基石课程都用到了霍夫丁不等式,其常见形式如下: 随 机 变 量 x i , x i ∈ { 0 , 1 } , x ‾ = 1 n ( x 1 + x 2 + ⋅ ⋅ ⋅ + x n ) 随机变量x_i,x_i\in \{0,1\}, \overline x=\frac1n(x_1+x_2+···+x_n) xi,xi{

0,1},x=n1(x1+x2++xn)
则 有 P ( ( x ‾ − E [ x ‾ ] ) ≥ t ) ≤ e − 2 n t 2 则有P((\overline x-E[\overline x])\geq t)\leq e^{-2nt^2} P((xE[x])t)e2nt2

含义: 给出二项分布均值偏离期望的概率上限.(上限与偏离值和次数有关)置信区间.


先证霍夫丁不等式的一般形式

霍夫丁一般形式

若: x i 相 互 独 立 , 且 x i ∈ [ a i , b i ] , S n = x 1 + x 2 + ⋅ ⋅ ⋅ + x n x_i相互独立,且x_i\in [a_i,b_i],S_n=x_1+x_2+···+x_n xi,xi[ai,bi],Sn=x1+x2++xn

则有: P ( S n − E [ S n ] ≥ t ) ≤ e x p ( − 2 t 2 ∑ 1 n ( b i − a i ) 2 ) P(S_n-E[S_n]\geq t)\leq exp(-\frac {2t^2}{\sum_{1}^n{(b_i-a_i)^2}}) P(SnE[Sn]t)exp(1n(biai)22t2)

证明过程要用到霍夫丁引理和马尔科夫不等式

马尔科夫不等式

马尔科夫不等式非常好证明,其形式如下

若 a > 0 , x 为 非 负 随 机 变 量 , 则 P ( x ≥ a ) ≤ E [ x ] a 若a>0,x为非负随机变量,则P(x\geq a)\leq \frac {E[x ]}{a} a>0,x,P(xa)aE[x]

证明:

得证.
(1)式中 x ≥ a , 缩 放 成 a ; x ≥ 0 , 缩 放 成 0 x\geq a,缩放成a;x\geq0,缩放成0 xa,a;x0,0

证法2:可以用指示变量证明

马尔科夫不等式的意义:

给出非负随机变量大于某正数的概率的上界;

**实际应用:**不超过1/5的人口会有超过五倍人均收入的收入.

霍夫丁引理

若 E [ x ] = 0 且 x ∈ [ a , b ] , 则 对 于 任 意 的 λ ∈ R , 都 有 E [ e λ x ] ≤ e x p { λ 2 ( b − a ) 2 8 } 若E[x]=0且x\in [a,b],则对于任意的\lambda\in R,都有E[e^{\lambda x}]\leq exp\{\frac{\lambda ^2(b-a)^2}8\} E[x]=0x[a,b],λR,E[eλx]exp{

8λ2(ba)2}

证明:

凸函数性质: ( a , f ( a ) ) , ( b , f ( b ) ) 线 段 在 f ( x ) 图 像 上 面 (a,f(a)),(b,f(b))线段在f(x)图像上面 (a,f(a)),(b,f(b))线f(x)
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-h0kmL6M5-1578399020302)(https://ooo.0o0.ooo/2016/10/11/57fce0ba65cf2.png)]
因为 e λ x e^{\lambda x} eλx 是一个凸函数(下凸)
所以 e λ x ≤ b − x b − a e λ a + x − a b − a e λ b e^{\lambda x} \leq\frac{b-x}{b-a}e^{\lambda a}+ \frac {x-a}{b-a}e^{\lambda b} eλxbabxeλa+baxaeλb
所以 E [ e λ x ] ≤ b − E [ x ] b − a e λ a + E [ x ] − a b − a e λ 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λx]babE[x]eλa+baE[x]aeλb
h = λ ( b − a ) , P = − a b − a , L ( h ) = − h P + l n ( 1 − P + P e h ) h=\lambda (b-a),P=-\frac a{b-a},L(h)=-hP+ln(1-P+Pe^h) h=λ(ba),P=baa,L(h)=hP+ln(1P+Peh)
带入上面的表达式的右边可以得到:
E [ e λ x ] ≤ e L ( h ) E[e^{\lambda x}] \leq e^{L(h)} E[eλx]eL(h)
查看 L ( h ) L(h) L(h),
L ( 0 ) = 0 , L ′ ( 0 ) = 0 , L ′ ′ ( h ) ≤ 1 4 ( 还 没 证 明 ) L(0)=0,L'(0)=0,L''(h)\leq\frac 14(还没证明) L(0)=0,L(0)=0,L(h)41()
由泰勒展开的二阶形式得:
(二阶项作为余项,所以不用 L ′ ′ ( 0 ) L''(0) L(0))
存 在 v ∈ ( 0 , h ) , 使 得 存在v\in(0,h),使得 v(0,h),使
L ( h ) = 1 2 ! L ′ ′ ( v ) ∗ v 2 ≤ 1 8 h 2 = 1 8 λ 2 ( b − a ) 2 L(h)=\frac1{2!}L''(v)*v^2\leq\frac18h^2=\frac18\lambda^2(b-a)^2 L(h)=2!1L(v)v281h2=81λ2(ba)2
所以 E [ e λ x ] ≤ e x p { λ 2 ( b − a ) 2 8 } E[e^{\lambda x}]\leq exp\{\frac{\lambda ^2(b-a)^2}8\} E[eλx]exp{
8λ2(ba)2}
得证.

作用: 有 E [ x ] = 0 , x ∈ [ a , b ] , 可 以 给 出 E [ e λ x ] 的 一 个 上 界 有E[x]=0,x\in [a,b],可以给出E[e^{\lambda x}]的一个上界 E[x]=0,x[a,b],E[eλx]

证明霍夫丁不等式

若: x i 相 互 独 立 , 且 x i ∈ [ a i , b i ] , S n = x 1 + x 2 + ⋅ ⋅ ⋅ + x n x_i相互独立,且x_i\in [a_i,b_i],S_n=x_1+x_2+···+x_n xi,xi[ai,bi],Sn=x1+x2++xn

则有: P ( S n − E [ S n ] ≥ t ) ≤ e x p ( − 2 t 2 ∑ 1 n ( b i − a i ) 2 ) P(S_n-E[S_n]\geq t)\leq exp(-\frac {2t^2}{\sum_{1}^n{(b_i-a_i)^2}}) P(SnE[Sn]t)exp(1n(biai)22t2)

证明:

对于s,t>0有
在这里插入图片描述

s是我们额外引入的变量,取合适的s值使(650)式最小.(得到尽可能紧致的上界)

在这里插入图片描述

由一般式得到特殊形式(常见形式)

1. 若 x i ∈ [ 0 , 1 ] , x ‾ = 1 n ( x 1 + x 2 ⋅ ⋅ ⋅ + x n ) , 若x_i\in [0,1],\overline x=\frac 1n(x_1+x_2···+x_n), xi[0,1],x=n1(x1+x2+xn),

用 x i n 代 x i , a i = 0 , b i = 1 n 用\frac {x_i}n代x_i,a_i=0,b_i=\frac 1n nxixi,ai=0,bi=n1
P ( x ‾ − E [ x ‾ ] ≥ t ) ≤ e x p ( − 2 t 2 ∑ i = 1 n 1 n 2 ) = e x p ( − 2 n t 2 ) P(\overline x-E[\overline x]\geq t)\leq exp(\frac{-2t^2}{\sum_{i=1}^{n }{\frac 1{n^2}}})=exp(-2nt^2) P(xE[x]t)exp(i=1nn212t2)=exp(2nt2)

2.二项分布 x i ∈ { 0 , 1 } , P ( x i = 1 ) = p , x = ( x 1 + ⋅ ⋅ ⋅ x n ) x_i \in \{0,1\},P(x_i=1)=p,x=(x_1+···x_n) xi{

0,1},P(xi=1)=p,x=(x1+xn)
令 x 的 偏 离 值 t = ϵ n , 也 就 是 p 的 偏 离 值 为 ϵ ( ϵ > 0 ) 令x的偏离值t=\epsilon n,也就是p的偏离值为\epsilon(\epsilon> 0) xt=ϵn,pϵ(ϵ>0),

有 h o e f f d i n g 不 等 式 知 : 有hoeffding 不等式知: hoeffding:

P ( x − p n ≥ ϵ n ) ≤ e x p ( − 2 t 2 ∑ 1 n ( b i − a i ) 2 ) = e x p ( − 2 ( ϵ n ) 2 ∑ 1 n ( 1 − 0 ) 2 ) = e x p ( − 2 n ϵ 2 ) P(x-pn\geq \epsilon n)\leq exp(-\frac {2t^2}{\sum_{1}^n{(b_i-a_i)^2}})=exp(-\frac {2(\epsilon n)^2}{\sum_{1}^n{(1-0)^2}})=exp(-2n\epsilon^2) P(xpnϵn)exp(1n(biai)22t2)=exp(1n(10)22(ϵn)2)=exp(2nϵ2)
P ( x − p n ≥ ϵ n ) ≤ e x p ( − 2 n ϵ 2 )   ( 1 ) P(x-pn\geq \epsilon n)\leq exp(-2n\epsilon^2)   (1) P(xpnϵn)exp(2nϵ2) (1)
对称写出:
P ( x − p n ≤ − ϵ n ) ≤ e x p ( − 2 n ϵ 2 )   ( 2 ) P(x-pn\leq -\epsilon n)\leq exp(-2n\epsilon^2)   (2) P(xpnϵn)exp(2nϵ2) (2)

有(1)(2)得:

P ( | x − p n | ≤ ϵ n ) ≤ 1 − 2 e x p ( − 2 n ϵ 2 ) P(|x-pn|\leq \epsilon n)\leq 1-2exp(-2n\epsilon^2) P(xpnϵn)12exp(2nϵ2)
或者写成
P ( x ∈ [ n ( p − ϵ ) , n ( p + ϵ ) ] ) ≤ 1 − 2 e x p ( − 2 n ϵ 2 ) P(x\in [n(p-\epsilon),n(p+\epsilon)])\leq 1-2exp(-2n\epsilon^2) P(x[n(pϵ),n(p+ϵ)])12exp(2nϵ2)

若记 x / n = p ~ x/n=\tilde p x/n=p~

P ( p ~ ∈ [ p − ϵ , p + ϵ ] ) ≤ 1 − 2 e x p ( − 2 n ϵ 2 ) P(\tilde p\in [p-\epsilon,p+\epsilon])\leq 1-2exp(-2n\epsilon^2) P(p~[pϵ,p+ϵ])12exp(2nϵ2)

该公式给出置信区间.

P ( ∣ p ~ − p ∣ > ϵ ) ≤ 2 e x p ( − 2 n ϵ 2 ) P(|\tilde p-p|>\epsilon)\leq 2exp(-2n\epsilon^2) P(p~p>ϵ)2exp(2nϵ2)

关于置信区间,一下引用自,维基百科-置信区间

在统计学中,一个概率样本的置信区间(Confidence interval)是对这个样本的某个总体参数的区间估计。置信区间展现的是,这个总体参数的真实值有一定概率落在与该测量结果有关的某对应区间。置信区间给出的是,声称总体参数的真实值在测量值的区间所具有的可信程度,即前面所要求的“一定概率”。这个概率被称为置信水平。举例来说,如果在一次大选中某人的支持率为55%,而置信水平0.95上的置信区间是(50%,60%),那么他的真实支持率落在50%和60%之区间的机率为95%,因此他的真实支持率不足50%的可能性小于2.5%(假设分布是对称的)

转载地址:https://blog.csdn.net/h_hzhou/article/details/76448898 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:支付宝免手续费提现
下一篇:java使用第三方jar包

发表评论

最新留言

能坚持,总会有不一样的收获!
[***.219.124.196]2024年03月03日 10时49分10秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

html中列表菜单加文字请选择,html中下拉菜单 2019-04-21
读书郎平板中android,读书郎学生平板电脑怎么用 使用方法详解【图文】 2019-04-21
html5 调用摄像头 支持IE,JS调用本地摄像头拍照(兼容各大浏览器及IE8+) 2019-04-21
rust和gta5哪个吃配置_盘点4款Steam“自由度”很高的游戏,GTA5众所周知,目前最热门... 2019-04-21
es审计日志_elasticsearch 事务日志translog 2019-04-21
dw1510_超低温种子储存柜 2019-04-21
文件未找到mathpage.wll_解决MathPage.wll文件找不到的问题(找了好久的良心之作)... 2019-04-21
java 使用或覆盖了已过时的api_JAVA使用或覆盖了已过时的 API 2019-04-21
java 图片旋转保存_Java 对图片90度旋转 2019-04-21
用java实现文学研究助手_数据结构文学研究助手 C语言代码实现(带源码+解析)... 2019-04-21
java gc的几种方式_GC 的三种基本实现方式 2019-04-21
wget linux java 32_通过wget在Linux上下载Java JDK会显示在许可证页面上 2019-04-21
babylonjs 设置面板位置_babylonjs 空间坐标转为屏幕坐标 2019-04-21
oracle里面如何查询sqlid,CSS_oracle中如何查看sql, --查询表状态:  select uo.O - phpStudy... 2019-04-21
oracle 查询中用case,oracle case when 在查询时候的用法。 2019-04-21
oracle正在运行的程序包,ORACLE PL/SQL编程详解之程序包的创建与应用 2019-04-21
php局部页面滚动,在访问另一页面后保留浏览器滚动位置 - php 2019-04-21
jmeter运行linux命令行,Jmeter在linux上运行(命令行运行Jmeter) 2019-04-21
linux服务器怎么添加站点,如何增加站点或虚拟主机及文件说明 2019-04-21
linux系统输入指令,Linux系统基础 - 基本操作命令 2019-04-21