接着上一节的不等式(一)-Markov与Chebyshev不等式
本节将学习Hoeffding不等式。
Hoeffding不等式
作用与Chebyshev不等式类似，但区间更紧致(增加了独立性约束)
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^{-tepsilon} prod_{i=1}^{n}e^{t^2(b_i-a_i)^2/8}
]
证明过程如下：
[egin{eqnarray}
P Bigg(
sum_{i=1}^{n}Y_i geq epsilon Bigg) &=& P Bigg( t sum_{i=1}^{n}Y_i geq t epsilon Bigg ) \
&=& P Bigg(e^{t sum limits_{i=1}^{n}Y_i} geq e^{t epsilon} Bigg) \
& leq & e^{-t epsilon} EBigg(e^{t sum limits_{i=1}^{n}Y_i} Bigg) qquad (Markov 不等式) \
&=& e^{-t epsilon} prod_{i=1}^{n} E Bigg( e^{t Y_i} Bigg) qquad (Y_1,...Y_n相互独立，期望的性质)
end{eqnarray}]
对于凸函数(f(x) = e^x)，对于任意(alpha in [0, 1])，和(x in [a, b])都满足
[f(x) leq alpha f(a) + (1 - alpha)f(b)
]
如图所示：
因为(a_i leq Y_i leq b_i)，即(Y_i in [a_i, b_i])，令(alpha = frac{b_i-Y_i }{b_i - a_i} in [0, 1])，则
$$e^{tY_i} leq frac{(b_i - Y_i)}{(b_i - a_i)} e^{ta_i} + frac{(Y_i - a_i)}{(b_i - a_i)} e^{tb_i} $$
又因为(E(Y_i) = 0)，对两边同时取期望，
[E(e^{tY_i}) leq frac{b_i - E(Y_i)}{(b_i - a_i)} e^{ta_i} + frac{E(Y_i) - a_i}{(b_i - a_i)} e^{tb_i} = frac{b_i}{(b_i - a_i)} e^{ta_i} - frac{a_i}{(b_i - a_i)} e^{tb_i}
]
记(u = t(b_i - a_i))，和(gamma = -a_i/b_i - a_i)，可以将上式右边写作$$e^{ -gamma u + log(1 - gamma + gamma e^u)}$$
记为(e^{g(u)})，我们对(g(u))作泰勒展开
[g(u) = frac{g(0)}{0!}(u-0)^0 + frac{g^{'}(0)}{1!}(u-0)^1 + frac{g^{''}(0)}{2!}(u-0)^2 + o(u^2)
]
易得(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^{-tepsilon} prod_{i=1}^{n}e^{t^2(b_i-a_i)^2/8}
]
令(X_1,...X_n acksim Bernoulli(p))，则对任意(epsilon > 0)，有
[P(|overline{X} - p| > epsilon) leq 2e^{-2nepsilon^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 acksim Bernoulli(p))，所以(X_i)的取值只能是(0)，(1)，因此(a = - p/n)，(b = (1-p)/n)，那么((b-a)^2 = 1/n^2)
[P(overline{X} - p > epsilon) = p(sum_{i=1}^{n} Y_i > epsilon) leq e^{-tepsilon}e^{t^2/(8n)} qquad (t>0)
]
取(t = 4nepsilon)，我们得到$$P(overline{X} - p > epsilon) leq e{-2nepsilon2}$$
同理可得$$P(overline{X} - p < -epsilon) leq e{-2nepsilon2}$$
因此
[P(|overline{X} - p| > epsilon) leq 2e^{-2nepsilon^2}
]
不同于其他的不等式是在收敛的情况下等式成立，Hoeffding不等式对于任意n都成立。
Hoeffding不等式应用
Reference
- 《All of Statistics: A Concise Course in Statistical Inference》by Wasserman, Larry
- 不等式 by 中科院 卿来云老师课件