集中不等式 是數學 中的一類不等式，描述了一個隨機變量 是否集中在某個取值附近。例如大數定律 說明了一系列獨立 同分佈 隨機變量的平均值 在概率 上趨近於它們的數學期望 ，這表示隨着變量數目增大，平均值會集中在數學期望附近[ 1]
馬爾可夫不等式給出了一個實值隨機變量取值大於等於某個特定數值的概率的上限。設X是一個隨機變量，a>0為正實數，那麼以下不等式成立[ 1]
P
(
|
X
|
≥
a
)
≤
E
(
|
X
|
)
a
.
{\displaystyle \mathbb {P} (|X|\geq a)\leq {\frac {\mathbb {E} (|X|)}{a}}.}
這個不等式可以推廣。對所有的單調嚴格遞增的非零函數
Φ
{\displaystyle \Phi }
[ 1]
P
(
X
≥
a
)
=
P
(
Φ
(
X
)
≥
Φ
(
a
)
)
≤
E
(
Φ
(
X
)
)
Φ
(
a
)
.
{\displaystyle \mathbb {P} (X\geq a)=\mathbb {P} (\Phi (X)\geq \Phi (a))\leq {\frac {\mathbb {E} (\Phi (X))}{\Phi (a)}}.}
馬爾可夫不等式給出了隨機變量處於區間
[
a
,
∞
)
{\displaystyle [a,\infty )}
Y
=
(
X
−
E
X
)
2
{\displaystyle Y=(X-\mathbb {E} X)^{2}}
P
(
|
X
−
E
(
X
)
|
≥
a
)
≤
Var
(
X
)
a
2
,
{\displaystyle \mathbb {P} (|X-\mathbb {E} (X)|\geq a)\leq {\frac {\operatorname {Var} (X)}{a^{2}}},}
其中的
Var
(
X
)
{\displaystyle \operatorname {Var} (X)}
方差 ，也就是：
Var
(
X
)
=
E
[
(
X
−
E
(
X
)
)
2
]
.
{\displaystyle \operatorname {Var} (X)=\mathbb {E} [(X-\mathbb {E} (X))^{2}].}
霍夫丁不等式適用於有界的隨機變量。設有兩兩獨立的一系列隨機變量
X
1
,
…
,
X
n
{\displaystyle X_{1},\dots ,X_{n}\!}
1
≤
i
≤
n
{\displaystyle 1\leq i\leq n}
X
i
{\displaystyle X_{i}}
幾乎 有界的變量，即滿足：
P
(
X
i
∈
[
a
i
,
b
i
]
)
=
1.
{\displaystyle \mathbb {P} (X_{i}\in [a_{i},b_{i}])=1.\!}
那麼這n個隨機變量的經驗期望：
X
¯
=
X
1
+
⋯
+
X
n
n
{\displaystyle {\overline {X}}={\frac {X_{1}+\cdots +X_{n}}{n}}}
滿足以下的不等式[ 1] [ 2]
P
(
X
¯
−
E
[
X
¯
]
≥
t
)
≤
exp
(
−
2
t
2
n
2
∑
i
=
1
n
(
b
i
−
a
i
)
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),\!}
P
(
|
X
¯
−
E
[
X
¯
]
|
≥
t
)
≤
2
exp
(
−
2
t
2
n
2
∑
i
=
1
n
(
b
i
−
a
i
)
2
)
,
{\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不等式給出了隨機變量方差的一個上限估計。設有兩兩獨立的隨機變量
X
1
…
X
n
{\displaystyle X_{1}\dots X_{n}}
X
1
′
…
X
n
′
{\displaystyle X_{1}'\dots X_{n}'}
i
{\displaystyle i}
X
i
′
{\displaystyle X_{i}'}
X
i
{\displaystyle X_{i}}
X
=
(
X
1
,
…
,
X
n
)
,
X
(
i
)
=
(
X
1
,
…
,
X
i
−
1
,
X
i
′
,
X
i
+
1
,
…
,
X
n
)
{\displaystyle X=(X_{1},\dots ,X_{n}),X^{(i)}=(X_{1},\dots ,X_{i-1},X_{i}',X_{i+1},\dots ,X_{n})}
V
a
r
(
f
(
X
)
)
≤
1
2
∑
i
=
1
n
E
[
(
f
(
X
)
−
f
(
X
(
i
)
)
)
2
]
.
{\displaystyle \mathrm {Var} (f(X))\leq {\frac {1}{2}}\sum _{i=1}^{n}E[(f(X)-f(X^{(i)}))^{2}].}
[ 1]
^ 1.0 1.1 1.2 1.3 1.4 Stéphane Boucheron, Gabor Lugosi, Olivier Bousquet. Concentration Inequalities (PDF) . Université de Paris-Sud, Laboratoire d'Informatique. [2012年9月7日] . （原始內容存檔 (PDF) 於2020年9月28日）. （英文） ^ Wassily Hoeffding, Probability inequalities for sums of bounded random variables, Journal of the American Statistical Association 58 (301): 13–30, March 1963. (JSTOR )（英文）
![{\displaystyle \operatorname {Var} (X)=\mathbb {E} [(X-\mathbb {E} (X))^{2}].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/903a713a326dea3725798b9f1d01eb0b2f82270f)
![{\displaystyle \mathbb {P} (X_{i}\in [a_{i},b_{i}])=1.\!}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2e6f13669eacf3e303df1837041e91ce704f7345)
![{\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),\!}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2384a4ef64dbf81cdfa5fe6f517ef35494a6b022)
![{\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),\!}](https://wikimedia.org/api/rest_v1/media/math/render/svg/51f4eeb59eab8345db944e6f7a2c91fd8a6146c4)
![{\displaystyle \mathrm {Var} (f(X))\leq {\frac {1}{2}}\sum _{i=1}^{n}E[(f(X)-f(X^{(i)}))^{2}].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c25450c4c542c8a1dd444386d89095d03ae96e97)