查看“集中不等式”的源代码

'''集中不等式'''是[[数学]]中的一类不等式，描述了一个[[随机变量]]是否集中在某个取值附近。例如[[大数定律]]说明了一系列[[統計獨立性#獨立隨機變數|独立]]同[[概率分布|分布]]随机变量的[[平均值]]在[[概率]]上趋近于它们的[[数学期望]]，这表示随着变量数目增大，平均值会集中在数学期望附近{{r|sgo}}。

==马尔可夫不等式==
{{main|马尔可夫不等式}}
马尔可夫不等式给出了一个实值随机变量取值大于等于某个特定数值的概率的上限。设X是一个随机变量，a>0为正实数，那么以下不等式成立{{r|sgo}}：
: <math>\mathbb{P}(|X| \geq a) \leq \frac{\mathbb{E}(|X|)}{a}.</math>
这个不等式可以推广。对所有的单调严格递增的非零函数<math>\Phi</math>，都有类似的不等式{{r|sgo}}：
:<math>\mathbb{P}(X \geq a) = \mathbb{P}(\Phi (X) \geq \Phi (a)) \leq \frac{\mathbb{E}(\Phi(X))}{\Phi (a)}.</math>

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

其中的<math>\operatorname{Var}(X)</math>表示变量X的[[方差]]，也就是：
:<math> \operatorname{Var}(X) = \mathbb{E}[(X - \mathbb{E}(X) )^2]. </math>

==霍夫丁不等式==
{{main|霍夫丁不等式}}
霍夫丁不等式适用于有界的随机变量。设有两两独立的一系列随机变量<math>X_1, \dots, X_n \!</math>。假设对所有的<math>1 \leq i \leq n</math>，<math>X_i</math>都是[[几乎处处|几乎]]有界的变量，即满足：
:<math>\mathbb{P}(X_i \in [a_i, b_i]) = 1. \!</math>

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

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

满足以下的不等式{{r|sgo}}<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>

==Efron–Stein不等式==

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

: <math>
\mathrm{Var}(f(X)) \leq \frac{1}{2} \sum_{i=1}^{n} E[(f(X)-f(X^{(i)}))^2].
</math>{{r|sgo}}

==参考来源==
{{reflist|refs=
<ref name="sgo">{{cite web | url=http://www.is.tuebingen.mpg.de/fileadmin/user_upload/files/publications/pdf2820.pdf | title=Concentration Inequalities | publisher=Université de Paris-Sud, Laboratoire d'Informatique | author = Stéphane Boucheron, Gabor Lugosi, Olivier Bousquet | accessdate=2012年9月7日}}{{en}}</ref> 
}}

[[Category:不等式]]