本文共 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((x−E[x])≥t)≤e−2nt2含义: 给出二项分布均值偏离期望的概率上限.(上限与偏离值和次数有关)置信区间.
先证霍夫丁不等式的一般形式
霍夫丁一般形式
若: 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(Sn−E[Sn]≥t)≤exp(−∑1n(bi−ai)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(x≥a)≤aE[x]证明:
得证. (1)式中 x ≥ a , 缩 放 成 a ; x ≥ 0 , 缩 放 成 0 x\geq a,缩放成a;x\geq0,缩放成0 x≥a,缩放成a;x≥0,缩放成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]=0且x∈[a,b],则对于任意的λ∈R,都有E[eλx]≤exp{ 8λ2(b−a)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λx≤b−ab−xeλa+b−ax−aeλ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]≤b−ab−E[x]eλa+b−aE[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=λ(b−a),P=−b−aa,L(h)=−hP+ln(1−P+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)∗v2≤81h2=81λ2(b−a)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(b−a)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(Sn−E[Sn]≥t)≤exp(−∑1n(bi−ai)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 用nxi代xi,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(x−E[x]≥t)≤exp(∑i=1nn21−2t2)=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) 令x的偏离值t=ϵ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(x−pn≥ϵn)≤exp(−∑1n(bi−ai)22t2)=exp(−∑1n(1−0)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(x−pn≥ϵ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(x−pn≤−ϵ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(|x−pn|≤ϵn)≤1−2exp(−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+ϵ)])≤1−2exp(−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+ϵ])≤1−2exp(−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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!