不等式（二）-Hoeffding不等式

接着上⼀节的

本节将学习Hoeffding不等式。

Hoeffding不等式

作⽤与Chebyshev不等式类似，但区间更紧致(增加了独⽴性约束)

Hoeffding不等式

设Y1,...Yn相互独⽴，且E(Yi)=0，且ai≤Yi≤bi，令ϵ>0，则对任意t>0，

P(i=1Yi≥ϵ)≤

证明过程如下：

∑

n

22

e−tϵi=1et(bi−ai)/8

∏

n

Pi=1Yi≥ϵ=Pti=1Yi≥tϵ

(∑

n

)((∑

n

n

))(Markov不等式)

=Peti=1Yi≥etϵ

∑

≤e−tϵEeti=1Yi

()∑

n

=

e−tϵi=1E

∏

n

()etYi

(Y1,...Yn相互独⽴，期望的性质)

对于凸函数f(x)=ex，对于任意α∈[0,1]，和x∈[a,b]都满⾜

f(x)≤αf(a)+(1−α)f(b)

如图所⽰：

bi−Yi

因为ai≤Yi≤bi，即Yi∈[ai,bi]，令α=

bi−ai

∈[0,1]，则

(bi−Yi)etYi≤

(Yi−ai)

(bi−ai)ta(bi−ai)tb

ei+ei

⼜因为E(Yi)=0，对两边同时取期望，

bi−E(Yi)

E(etYi)≤

(bi−ai)

etai+

E(Yi)−ai(bi−ai)

etbi=

bi

ai

(bi−ai)ta(bi−ai)tb

ei−ei

记u=t(bi−ai)，和γ=−ai/bi−ai，可以将上式右边写作

u

e−γu+log(1−γ+γe)

记为eg(u)，我们对g(u)作泰勒展开g(0)g(0)

g(u)=0!(u−0)0+1!(u−0)1+g″易得g(0) = g^{'}(0) = 0，⽽

g^{''}(u) = \\frac{\\gamma(1-\\gamma)e^u}{(1- \\gamma + \\gamma e^u)^2}得到g^{''}(0) = \\gamma(1-\\gamma) \\leq 1/4，带⼊泰勒展开式，得到

g(u) = \\frac{g^{''}(0)}{2!}(u-0)^2 + o(u^2) \\leq \\frac{1/4}{2!}(u-0)^2 = \\frac{u^2}{8} = \\frac{1}{8}t^2(b_i - a_i)^{2}

′

因此，

E(e^{tY_i}) \\leq e^{g(u)} \\leq e^{t^2(b_i - a_i)^{2}/8}不等式得证。

Hoeffding不等式

设Y_1,...Y_n相互独⽴，且E(Y_i) = 0，且a_i \\leq Y_i \\leq b_i，令\\epsilon > 0，则对任意t>0，P(\\sum_{i=1}^{n}Y_i \\geq \\epsilon) \\leq e^{-t\\epsilon} \\prod_{i=1}^{n}e^{t^2(b_i-a_i)^2/8}令X_1,...X_n \\backsim Bernoulli(p)，则对任意\\epsilon > 0，有P(|\\overline{X} - p| > \\epsilon) \\leq 2e^{-2n\\epsilon^2} \\qquad (2)其中 \\overline{X_n} = \\frac{1}{n}\\sum_{i=1}^{n}X_i对于(2)式证明如下：

令Y_i = \\frac{1}{n}(X_i - p)，有E(Y_i) = 0，且有

\\sum_{i=1}^{n} Y_i = \\frac{1}{n} \\sum_{i=1}^{n} (X_i - p) = \\frac{1}{n}\\sum_{i=1}^{n} X_i - p = \\overline{X_n} - p

⼜有a \\leq Y_i \\leq b，因为X_1,...X_n \\backsim Bernoulli(p)，所以X_i的取值只能是0，1，因此a = - p/n，b = (1-p)/n，那么(b-a)^2 = 1/n^2P(\\overline{X} - p > \\epsilon) = p(\\sum_{i=1}^{n} Y_i > \\epsilon) \\leq e^{-t\\epsilon}e^{t^2/(8n)} \\qquad (t>0)

取t = 4n\\epsilon，我们得到$$P(\\overline{X} - p > \\epsilon) \\leq e{-2n\\epsilon2} 同理可得P(\\overline{X} - p < -\\epsilon) \\leq e{-2n\\epsilon2}$$因此

P(|\\overline{X} - p| > \\epsilon) \\leq 2e^{-2n\\epsilon^2}

不同于其他的不等式是在收敛的情况下等式成⽴，Hoeffding不等式对于任意n都成⽴。

Hoeffding不等式应⽤Reference

Loading [MathJax]/jax/element/mml/optable/GeneralPunctuation.js

1. 《All of Statistics: A Concise Course in Statistical Inference》by Wasserman, Larry2.