霍夫丁不等式及其他相关不等式证明
周志华老师的书和台大的基石课程都用到了,霍夫丁不等式,常见形式如下:
随机变量xi,xi∈{0,1},x⎯⎯=1n(x1+x2+···+xn)
则有P((x⎯⎯−E[x⎯⎯])≥t)≤e−2nt2
含义:给出二项分布均值偏离期望的概率上限.(上限与偏离值和次数有关)
置信区间.
先证霍夫丁不等式的一般形式
霍夫丁一般形式
若:
xi相互独立,且xi∈[ai,bi],Sn=x1+x2+···+xn
则有:
P(Sn−E[Sn]≥t)≤exp(−2t2∑n1(bi−ai)2)
证明过程要用到霍夫丁引理和马尔科夫不等式
马尔科夫不等式
马尔科夫不等式非常好证明,其形式如下
若a>0,x为非负随机变量,则P(x≥a)≤E[x]a
证明:
E[x]P(x≥a)>=a∗P(x≥a)+0∗P(x<a) =a∗P(x≥a)≤E[x]a(1)(2)(3)
得证.
(1)式中
x≥a,缩放成a;x≥0,缩放成0
证法2:可以用指示变量证明
马尔科夫不等式的意义:
给出非负随机变量大于某正数的概率的上界;
实际应用:不超过1/5的人口会有超过五倍人均收入的收入.
霍夫丁引理
若E[x]=0且x∈[a,b],则对于任意的λ∈R,都有E[eλx]≤exp{λ2(b−a)28}
证明:
凸函数性质:(a,f(a)),(b,f(b))线段在f(x)图像上面
因为 eλx是一个凸函数(下凸)
所以 eλx≤b−xb−aeλa+x−ab−aeλb
所以 E[eλx]≤b−E[x]b−aeλa+E[x]−ab−aeλb
令 h=λ(b−a),P=−ab−a,L(h)=−hP+ln(1−P+Peh)
带入上面的表达式的右边可以得到:
E[eλx]≤eL(h)
查看L(h),
L(0)=0,L′(0)=0,L″(h)≤14(还没证明)
由泰勒展开的二阶形式得:
(二阶项作为余项,所以不用L″(0))
存在v∈(0,h),使得
L(h)=12!L″(v)∗v2≤18h2=18λ2(b−a)2
所以E[eλx]≤exp{λ2(b−a)28}得证.
作用:有E[x]=0,x∈[a,b],可以给出E[eλx]的一个上界
证明霍夫丁不等式
若:
xi相互独立,且xi∈[ai,bi],Sn=x1+x2+···+xn
则有:
P(Sn−E[Sn]≥t)≤exp(−2t2∑n1(bi−ai)2)
证明:
对于s,t>0有
P(Sn−E[Sn]≥t)(马尔科夫得)(霍夫丁引理)=P(es(Sn−E[Sn])≥est)≤e−stE[es(Sn−E[Sn])]=e−st∏i=1nE[es(xi−E[xi])]≤e−st∏i=1nes2(bi−ai)28=exp(−st+18s2∑i=1n(bi−ai)2)
s是我们额外引入的变量,取合适的s值使(650)式最小.(得到尽可能紧致的上界)
令g(s)=−st+18s2∑i=1n(bi−ai)2,二次函数有最小值min(g(s))=−2t2∑n1(bi−ai)2至此:P(Sn−E[Sn]≥t)≤exp(−2t2∑n1(bi−ai)2)
由一般式得到特殊形式(常见形式)
1.
若xi∈[0,1],x⎯⎯=1n(x1+x2···+xn),
用xin代xi,ai=0,bi=1n
P(x⎯⎯−E[x⎯⎯]≥t)≤exp(−2t2∑ni=11n2)=exp(−2nt2)
2.二项分布 xi∈{0,1},P(xi=1)=p,x=(x1+···xn)
令x的偏离值t=ϵn,也就是p的偏离值为ϵ(ϵ>0),
有hoeffding不等式知:
P(x−pn≥ϵn)≤exp(−2t2∑n1(bi−ai)2)=exp(−2(ϵn)2∑n1(1−0)2)=exp(−2nϵ2)
即P(x−pn≥ϵn)≤exp(−2nϵ2) (1)
对称写出:
P(x−pn≤−ϵn)≤exp(−2nϵ2) (2)
有(1)(2)得:
P(｜x−pn｜≤ϵn)≤1−2exp(−2nϵ2)
或者写成
P(x∈[n(p−ϵ),n(p+ϵ)])≤1−2exp(−2nϵ2)
若记x/n=p̃
P(p̃ ∈[p−ϵ,p+ϵ])≤1−2exp(−2nϵ2)
该公式给出置信区间.
P(|p̃ −p|>ϵ)≤2exp(−2nϵ2)
关于置信区间,一下引用自,维基百科-置信区间
在统计学中，一个概率样本的置信区间（Confidence interval）是对这个样本的某个总体参数的区间估计。置信区间展现的是，这个总体参数的真实值有一定概率落在与该测量结果有关的某对应区间。置信区间给出的是，声称总体参数的真实值在测量值的区间所具有的可信程度，即前面所要求的“一定概率”。这个概率被称为置信水平。举例来说，如果在一次大选中某人的支持率为55%，而置信水平0.95上的置信区间是（50%，60%），那么他的真实支持率落在50%和60%之区间的机率为95%，因此他的真实支持率不足50%的可能性小于2.5%（假设分布是对称的)
