集中不等式

集中不等式是数学中的一类不等式，描述了一个随机变量是否集中在某个取值附近。例如大数定律说明了一系列独立同分布随机变量的平均值在概率上趋近于它们的数学期望，这表示随着变量数目增大，平均值会集中在数学期望附近^[1]。

马尔可夫不等式

主条目：马尔可夫不等式

马尔可夫不等式给出了一个实值随机变量取值大于等于某个特定数值的概率的上限。设X是一个随机变量，a>0为正实数，那么以下不等式成立^[1]：

${\displaystyle \mathbb {P} (|X|\geq a)\leq {\frac {\mathbb {E} (|X|)}{a}}.}$ 

这个不等式可以推广。对所有的单调严格递增的非零函数${\displaystyle \Phi }$ ，都有类似的不等式^[1]：

${\displaystyle \mathbb {P} (X\geq a)=\mathbb {P} (\Phi (X)\geq \Phi (a))\leq {\frac {\mathbb {E} (\Phi (X))}{\Phi (a)}}.}$ 

切比雪夫不等式

主条目：切比雪夫不等式

马尔可夫不等式给出了随机变量处于区间${\displaystyle [a,\infty )}$ 之概率的上限估计。切比雪夫不等式则给出了随机变量集中在距离其数学期望值距离不超过a的区间上之概率的上限估计。设X是一个随机变量，a>0为正实数，那么只要对随机变量${\displaystyle Y=(X-\mathbb {E} X)^{2}}$ 应用马尔可夫不等式就可以得到：

${\displaystyle \mathbb {P} (|X-\mathbb {E} (X)|\geq a)\leq {\frac {\operatorname {Var} (X)}{a^{2}}},}$ 

其中的${\displaystyle \operatorname {Var} (X)}$ 表示变量X的方差，也就是：

${\displaystyle \operatorname {Var} (X)=\mathbb {E} [(X-\mathbb {E} (X))^{2}].}$ 

霍夫丁不等式

主条目：霍夫丁不等式

霍夫丁不等式适用于有界的随机变量。设有两两独立的一系列随机变量${\displaystyle X_{1},\dots ,X_{n}\!}$ 。假设对所有的${\displaystyle 1\leq i\leq n}$ ，${\displaystyle X_{i}}$ 都是几乎有界的变量，即满足：

${\displaystyle \mathbb {P} (X_{i}\in [a_{i},b_{i}])=1.\!}$ 

那么这n个随机变量的经验期望：

${\displaystyle {\overline {X}}={\frac {X_{1}+\cdots +X_{n}}{n}}}$ 

满足以下的不等式^[1][2]：

${\displaystyle \mathbb {P} ({\overline {X}}-\mathbb {E} [{\overline {X}}]\geq t)\leq \exp \left(-{\frac {2t^{2}n^{2}}{\sum _{i=1}^{n}(b_{i}-a_{i})^{2}}}\right),\!}$ 

${\displaystyle \mathbb {P} (|{\overline {X}}-\mathbb {E} [{\overline {X}}]|\geq t)\leq 2\exp \left(-{\frac {2t^{2}n^{2}}{\sum _{i=1}^{n}(b_{i}-a_{i})^{2}}}\right),\!}$ 

Efron–Stein不等式

Efron–Stein不等式给出了随机变量方差的一个上限估计。设有两两独立的随机变量${\displaystyle X_{1}\dots X_{n}}$ 和${\displaystyle X_{1}'\dots X_{n}'}$ ，并且对所有的${\displaystyle i}$ ，${\displaystyle X_{i}'}$ 与${\displaystyle X_{i}}$ 有着相同的分布。那么令${\displaystyle X=(X_{1},\dots ,X_{n}),X^{(i)}=(X_{1},\dots ,X_{i-1},X_{i}',X_{i+1},\dots ,X_{n})}$ ，则有

${\displaystyle \mathrm {Var} (f(X))\leq {\frac {1}{2}}\sum _{i=1}^{n}E[(f(X)-f(X^{(i)}))^{2}].}$ ^[1]

参考来源

1. Stéphane Boucheron, Gabor Lugosi, Olivier Bousquet. Concentration Inequalities (PDF). Université de Paris-Sud, Laboratoire d'Informatique. [2012年9月7日]. （原始内容 (PDF)于2020年9月28日）. （英文）
2. Wassily Hoeffding, Probability inequalities for sums of bounded random variables, Journal of the American Statistical Association 58 (301): 13–30, March 1963. (JSTOR)（英文）