查看“︁霍夫丁不等式”︁的源代码

{{NoteTA |G1=Math}}
在[[概率论]]中，'''霍夫丁不等式（{{lang-en|Hoeffding's inequality}}）'''适用于有界的随机变量，提供了有界独立随机变量之和偏离其期望值超过一定数量的概率的上限，即<math>\max \mathbb{P}(\overline{X} - \mathbb{E}[\overline{X}] \geq t )</math>。霍夫丁不等式在1963年由[[瓦西里·霍夫丁]]（Wassily Hoeffding）证明。

Hoeffding不等式是[[吾妻不等式]]和McDiarmid不等式的一个特例。它类似于切尔诺夫界，但往往不那么尖锐，特别是当随机变量的方差很小时。  它与[[伯恩施坦不等式|伯恩斯坦不等式]]相似，但无法与之相比。

== 阐述 ==
设有两两独立的一系列随机变量 <math>X_1, \dots, X_n \!</math> 。假设对所有的 <math>1 \leq i \leq n</math>，<math>X_i</math> 变量[[几乎必然]]满足 <math>a_i\leqslant X_i \leqslant b_i ,</math>  即 <math>\mathbb{P}(X_i \in [a_i, b_i]) \approx 1. \!</math>   
考虑这些随机变量的总和，<math>S_n = \sum_{i=1}^{n} X_i = X_1 + X_2 + X_3 + \cdots + X_{n-1} + X_n .</math> 然后霍夫丁不等式指出，对于所有 <math>t>0 </math> 有：

* <math>\mathbb{P}(S_n - \mathbb{E}[S_n]\geqslant t) \leqslant  \exp\left ( - \frac{2t^2}{\textstyle \sum_{i=1}^n (b_i-a_i)^2\displaystyle} \right ) </math>  
* <math>\mathbb{P}(|S_n - \mathbb{E}[S_n]|\geqslant t) \leqslant 2 \exp\left ( - \frac{2t^2}{\textstyle \sum_{i=1}^n (b_i-a_i)^2\displaystyle} \right )</math>

这里 <math>\mathbb{E}[S_n] </math> 是 <math>S_n </math> 的[[期望值|期望]]。

值得注意的是，若 <math>X_i </math> 为抽样获得，该不等式仍成立；但在这种情况下，随机变量不再是独立的。这一说法的证据可以在 Hoeffding <ref>{{Cite journal |last=Hoeffding |first=Wassily |date=1963-03 |title=Probability Inequalities for Sums of Bounded Random Variables |url=http://www.tandfonline.com/doi/abs/10.1080/01621459.1963.10500830 |journal=Journal of the American Statistical Association |language=en |volume=58 |issue=301 |doi=10.1080/01621459.1963.10500830 |issn=0162-1459 |access-date=2023-07-29 |archive-date=2023-06-19 |archive-url=https://web.archive.org/web/20230619192722/https://www.tandfonline.com/doi/abs/10.1080/01621459.1963.10500830 |dead-url=no }}</ref>的论文中找到。对于抽样的稍微更好的上界，可参见Serfling（1974）<ref>{{Cite journal |last=Serfling |first=R. J. |date=1974-01 |title=Probability Inequalities for the Sum in Sampling without Replacement |url=https://projecteuclid.org/journals/annals-of-statistics/volume-2/issue-1/Probability-Inequalities-for-the-Sum-in-Sampling-without-Replacement/10.1214/aos/1176342611.full |journal=The Annals of Statistics |volume=2 |issue=1 |doi=10.1214/aos/1176342611 |issn=0090-5364 |access-date=2023-07-29 |archive-date=2023-07-29 |archive-url=https://web.archive.org/web/20230729101931/https://projecteuclid.org/journals/annals-of-statistics/volume-2/issue-1/Probability-Inequalities-for-the-Sum-in-Sampling-without-Replacement/10.1214/aos/1176342611.full |dead-url=no }}</ref>的论文。

=== 另一种形式 ===
设有两两独立的一系列随机变量 <math>X_1, \dots, X_n \!</math> 。<ref>{{Cite journal |date=2022-03-08 |title=集中不等式 |url=https://zh.wikipedia.org/w/index.php?title=%E9%9B%86%E4%B8%AD%E4%B8%8D%E7%AD%89%E5%BC%8F&oldid=70525422 |journal=维基百科，自由的百科全书 |language=zh}}</ref>那么这n个随机变量的经验期望：

:<math>\overline{X} = \frac{X_1 + \cdots + X_n}{n} </math>

满足以下的不等式<ref>Wassily Hoeffding, Probability inequalities for sums of bounded random variables, ''Journal of the American Statistical Association'' '''58''' (301): 13–30, March 1963. ([http://links.jstor.org/sici?sici=0162-1459%28196303%2958%3A301%3C13%3APIFSOB%3E2.0.CO%3B2-D JSTOR]){{en}}
</ref>：

:<math>\mathbb{P}(\overline{X} - \mathbb{E}[\overline{X}] \geq t) \leq \exp \left( - \frac{2t^2n^2}{\sum_{i=1}^n (b_i - a_i)^2} \right),\!</math>
:<math>\mathbb{P}(|\overline{X} - \mathbb{E}[\overline{X}]| \geq t) \leq 2\exp \left( - \frac{2t^2n^2}{\sum_{i=1}^n (b_i - a_i)^2} \right),\!</math>

== 特别地 ==
假定对于所有的 <math>i </math> 都有 <math>a_i = 0, b_i = 1 </math> 。当 <math>X_i </math> 是独立的[[伯努利随机变量]]时，尽管它们不必服从相同分布，我们可以得到如下更为简洁的不等式：

<math>\mathbb{P}( S_n -  \mathbb{E}[S_n] \geqslant t) \leqslant \exp(-\frac{2t^2}{n} ). </math> 

上式对于所有的 <math>t \geqslant 0 </math> 成立。这样我们就得到了[[增强版的切尔诺夫界]]。它更为通用，因为它允许取值介于 0 和 1 之间的随机变量，但效果较差，因为当随机变量方差较小时，[[切尔诺夫界]]给出了更好的尾边界。

== [[亚高斯随机变量]]的一般情况 ==
霍夫丁不等式的证明可以推广到任何次高斯分布。

回想一下，随机变量 <math>X </math> 服从[[亚高斯分布]]，是否存在 <math>c > 0 </math> 使得，<math>\mathbb{P}(\left\vert X \right\vert \geqslant t ) 
\leqslant 2e^{-ct^2} </math> 成立。

对于任意有界变量 <math>X, 
 </math>  <math>t > T </math>（ <math>T </math> 足够大），有 <math>\mathbb{P}(|X| \geqslant t) = 0 \leqslant 2e^{-ct^2} </math> 。对于任意的 <math>t \leqslant T </math> 有 <math>2e^{ -cT^2} \leqslant 2e^{ -ct^2 }  </math> ，取 <math>c = \frac{\ln 2}{T^2}  </math> 则有 <math>\mathbb{P}(|X| \geqslant t) \leqslant 1 \leqslant 2e^{ -cT^2} \leqslant 2e^{ -ct^2},  </math> 所以每个有界变量都是亚高斯变量。

对于随机变量 <math>X </math>，下式范数是有限的，当且仅当 <math>X </math> 是亚高斯：

<math>\lVert X \rVert_{\psi_2} \overset{\underset{\mathrm{def}}{}}{=}\inf\{c \geq 0: \mathbb{E}[e^{\frac{X^2}{c^2}}] \}. </math>  

然后设 <math>X_1,\cdots,X_n  </math> 为[[零均值]]独立亚高斯随机变量，'''霍夫丁不等式'''的一般版本指出：

<math>\mathbb{P}(
        |\sum_{i=1}^n X_i| \geqslant t
)

\leqslant 2 \exp(- \frac{ct^2}{\textstyle \sum_{i=1}^n 
\displaystyle\lVert X_i \rVert ^2_{\psi_2}}),  </math> 其中 <math>c > 0  </math> 且为绝对常数<ref>{{Cite book|chapter=|publisher=Cambridge University Press|date=2018|isbn=978-1-108-41519-4|first=Roman|last=Vershynin|title=High-dimensional probability: an introduction with applications in data science|url=https://archive.org/details/highdimensionalp0000vers}}</ref>。

== 证明 ==
霍夫丁界的证明与切尔诺夫界等集中不等式类似<ref>{{Cite book|chapter=|url=https://en.wikipedia.org/wiki/Special:BookSources/978-0-19-953525-5|publisher=Oxford university press|date=2013|location=Oxford|isbn=978-0-19-953525-5|first=Stéphane|last=Boucheron|first2=Gábor|last2=Lugosi|first3=Pascal|last3=Massart|title=Concentration inequalities: a nonasymptotic theory of independence|access-date=2023-07-29|archive-date=2022-07-30|archive-url=https://web.archive.org/web/20220730183550/https://en.wikipedia.org/wiki/Special:BookSources/978-0-19-953525-5|dead-url=no}}</ref>。主要区别在于使用[[霍夫丁引理]]：

假设 <math>X </math> 是一个真正的随机变量，那么[[几乎必然]] <math>X \in \left[a,b\right] </math> 。然后<math>\mathbb{E} \left [e^{s\left (X- \mathbb{E} 
\left [X \right ]\right )} \right ]\leqslant \exp\left(\tfrac{1}{8} s^2 (b-a)^2\right). </math> 

使用这个引理，我们可以证明霍夫丁不等式。如定理陈述，假设 <math>X_1,\cdots,X_n  </math> 为 <math>n </math> 个独立随机变量，<math>X_i \in \left[a_i,b_i \right], </math> <math>s.t. \ i \in N_{+} </math>几乎必然 。设 <math>S_n = X_1 + \cdots + X_n.  </math>  那么对于 <math>s > 0 </math> 且 <math>t>0 </math> , 联立[[馬爾可夫不等式|马尔可夫不等式]]和 <math>X_i </math> 的独立性可得：

<math>\begin{align}
\operatorname{P}\left(S_n-\mathrm{E}\left [S_n \right ]\geq t \right) 
&= \operatorname{P} \left (\exp(s(S_n-\mathrm{E}\left [S_n \right ])) \geq \exp(st) \right)\\
&\leq \exp(-st)\mathrm{E} \left [\exp(s(S_n-\mathrm{E}\left [S_n \right ])) \right ]\\
&= \exp(-st) \prod_{i=1}^n\mathrm{E} \left [\exp(s(X_i-\mathrm{E}\left [X_i\right])) \right ]\\
&\leq \exp(-st) \prod_{i=1}^n \exp\Big(\frac{s^2 (b_i-a_i)^2}{8}\Big)\\
&= \exp\left(-st+\tfrac{1}{8} s^2 \sum_{i=1}^n(b_i-a_i)^2\right) \  
\end{align}   </math>   

此上界对于 <math>s </math> 的值是最佳的，最小值在指数 <math>O(e^n) </math> 范围内。这可以通过优化二次曲线轻松完成，给出 <math>s=\frac{4t}{\sum_{i=1}^n(b_i-a_i)^2}. </math> 

为这个值 <math>s </math> 编写上面的界限，我们得到所需的界限：<math>\operatorname{P} \left(S_n-\mathrm{E}\left [S_n \right ]\geq t \right)\leq \exp\left(-\frac{2t^2}{\sum_{i=1}^n(b_i-a_i)^2}\right). </math> 

== 用法 ==
霍夫丁不等式可用于推导置信区间。我们考虑一枚硬币，它以概率 <math>p </math> 显示正面，以概率 <math>1-p </math> 显示反面。我们抛硬币 <math>n </math> 次，生成 <math>n </math> 个样本  <math>X_1, \cdots, X_n </math>（即[[独立同分布]][[伯努利随机变量]]）。硬币正面朝上的预期次数是 <math>p\cdot n </math> 。此外，硬币正面至少出现k次的概率可以通过以下表达式精确量化：

<math>\operatorname{\mathbb{P}}( H(n) \geqslant k)= \sum_{i=k}^n \binom{n}{i} p^i (1-p)^{n-i}, </math> 其中 <math>H(n) </math> 是 <math>n </math> 次抛硬币的正面数量。当 <math>k=(p+\varepsilon)n </math> 表示某个 <math>\varepsilon > 0 </math> 时，霍夫丁不等式将这个概率限制为一个在 <math>\varepsilon^2n </math> 中呈指数小的项：

<math>\operatorname{\mathbb{P}}( H(n) - pn >\varepsilon n)\leqslant \exp\left(-2\varepsilon^2 n\right). </math> 

由于这个界限在均值的两侧都成立，霍夫丁不等式意味着我们看到的头部数量集中在其均值周围，尾部呈指数级小。

<math>\operatorname{\mathbb{P}}(| H(n) - pn | >\varepsilon n)\leqslant 2\exp\left(-2\varepsilon^2 n\right). </math>

<math>\overline{X} = \frac{1}{n}H(n) </math> 作为“观察到的”平均值，该概率可以解释为一个置信区间的显著性水平 <math>\alpha </math>（出错的概率），这个置信区间是中心为 <math>p </math> 的 <math>\varepsilon  </math> [[邻域]]：

<math>\alpha=\operatorname{\mathbb{P}}(\ \overline{X} \notin [p-\varepsilon, p+\varepsilon]) \leqslant 2e^{-2\varepsilon^2n}
. </math> 解出 <math>n </math> : <math>n\geqslant \frac{\log(\frac{2}{\alpha }) }{2\varepsilon^2}. </math> <ref>{{Cite journal |date=2023-07-02 |title=Hoeffding's inequality |url=https://en.wikipedia.org/w/index.php?title=Hoeffding%27s_inequality&oldid=1163033253 |journal=Wikipedia |language=en}}</ref>  因此，我们至少需要 <math> \frac{\log(\frac{2}{\alpha }) }{2\varepsilon^2} </math> 份样本才能获得 (1- α)-置信区间 <math>\textstyle p \pm \varepsilon </math> 。因此，获取置信区间的成本在置信水平方面是次线性的，在精度方面是二次的。请注意，有更有效的方法来估计置信区间。

== 参见 ==

* [[集中不等式]]
* 霍夫丁引理
* [[伯恩施坦不等式|伯恩斯坦不等式]]

==参考文献==
{{reflist}}

[[Category:概率不等式]]