集中不等式

集中不等式是數學中的一類不等式，描述了一個隨機變量是否集中在某個取值附近。例如大數定律說明了一系列獨立同分佈隨機變量的平均值在概率上趨近於它們的數學期望，這表示隨着變量數目增大，平均值會集中在數學期望附近^[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)（英文）