不等式(二)-Hoeffding不等式

接著上一節(jié)的那些不等式們(一)-Markov與Chebyshev不等式
本節(jié)將學(xué)習(xí)Hoeffding不等式。

Hoeffding不等式

作用與Chebyshev不等式類似，但區(qū)間更緊致(增加了獨立性約束)

Hoeffding不等式
設(shè)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}

證明過程如下：
\begin{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} E\Bigg(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相互獨立，期望的性質(zhì)) \end{eqnarray}

對于凸函數(shù)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不等式
設(shè)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^2
P(\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\epsilon^2}
同理可得P(\overline{X} - p < -\epsilon) \leq e^{-2n\epsilon^2}
因此
P(|\overline{X} - p| > \epsilon) \leq 2e^{-2n\epsilon^2}

不同于其他的不等式是在收斂的情況下等式成立，Hoeffding不等式對于任意n都成立。

Hoeffding不等式應(yīng)用

Reference

  1. 《All of Statistics: A Concise Course in Statistical Inference》by Wasserman, Larry
  2. 不等式 by 中科院 卿來云老師課件
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容