在概率论 中,霍夫丁不等式(英语:Hoeffding's inequality ) 适用于有界的随机变量,提供了有界独立随机变量之和偏离其期望超过一定数量的概率的上限,即
max
P
(
X
¯
−
E
[
X
¯
]
≥
t
)
{\displaystyle \max \mathbb {P} ({\overline {X}}-\mathbb {E} [{\overline {X}}]\geq t)}
。霍夫丁不等式在1963年由瓦西里·霍夫丁 (Wassily Hoeffding)证明。
Hoeffding不等式是吾妻不等式 和McDiarmid不等式的一个特例。它类似于切尔诺夫界,但往往不那么尖锐,特别是当随机变量的方差很小时。 它与伯恩斯坦不等式 相似,但无法与之相比。
设有两两独立的一系列随机变量
X
1
,
…
,
X
n
{\displaystyle X_{1},\dots ,X_{n}\!}
。假设对所有的
1
≤
i
≤
n
{\displaystyle 1\leq i\leq n}
,
X
i
{\displaystyle X_{i}}
变量几乎必然 满足
a
i
⩽
X
i
⩽
b
i
,
{\displaystyle a_{i}\leqslant X_{i}\leqslant b_{i},}
即
P
(
X
i
∈
[
a
i
,
b
i
]
)
≈
1.
{\displaystyle \mathbb {P} (X_{i}\in [a_{i},b_{i}])\approx 1.\!}
考虑这些随机变量的总和,
S
n
=
∑
i
=
1
n
X
i
=
X
1
+
X
2
+
X
3
+
⋯
+
X
n
−
1
+
X
n
.
{\displaystyle S_{n}=\sum _{i=1}^{n}X_{i}=X_{1}+X_{2}+X_{3}+\cdots +X_{n-1}+X_{n}.}
然后霍夫丁不等式指出,对于所有
t
>
0
{\displaystyle t>0}
有:
P
(
S
n
−
E
[
S
n
]
⩾
t
)
⩽
exp
(
−
2
t
2
∑
i
=
1
n
(
b
i
−
a
i
)
2
)
{\displaystyle \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)}
P
(
|
S
n
−
E
[
S
n
]
|
⩾
t
)
⩽
2
exp
(
−
2
t
2
∑
i
=
1
n
(
b
i
−
a
i
)
2
)
{\displaystyle \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)}
这里
E
[
S
n
]
{\displaystyle \mathbb {E} [S_{n}]}
是
S
n
{\displaystyle S_{n}}
的期望 。
值得注意的是,若
X
i
{\displaystyle X_{i}}
为抽样获得,该不等式仍成立;但在这种情况下,随机变量不再是独立的。这一说法的证据可以在 Hoeffding [ 1] 的论文中找到。对于抽样的稍微更好的上界,可参见Serfling(1974)[ 2] 的论文。
设有两两独立的一系列随机变量
X
1
,
…
,
X
n
{\displaystyle X_{1},\dots ,X_{n}\!}
。[ 3] 那么这n个随机变量的经验期望:
X
¯
=
X
1
+
⋯
+
X
n
n
{\displaystyle {\overline {X}}={\frac {X_{1}+\cdots +X_{n}}{n}}}
满足以下的不等式[ 4] :
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),\!}
霍夫丁不等式的证明可以推广到任何次高斯分布。
回想一下,随机变量
X
{\displaystyle X}
服从亚高斯分布 ,是否存在
c
>
0
{\displaystyle c>0}
使得,
P
(
|
X
|
⩾
t
)
⩽
2
e
−
c
t
2
{\displaystyle \mathbb {P} (\left\vert X\right\vert \geqslant t)\leqslant 2e^{-ct^{2}}}
成立。
对于任意有界变量
X
,
{\displaystyle X,}
t
>
T
{\displaystyle t>T}
(
T
{\displaystyle T}
足够大),有
P
(
|
X
|
⩾
t
)
=
0
⩽
2
e
−
c
t
2
{\displaystyle \mathbb {P} (|X|\geqslant t)=0\leqslant 2e^{-ct^{2}}}
。对于任意的
t
⩽
T
{\displaystyle t\leqslant T}
有
2
e
−
c
T
2
⩽
2
e
−
c
t
2
{\displaystyle 2e^{-cT^{2}}\leqslant 2e^{-ct^{2}}}
,取
c
=
ln
2
T
2
{\displaystyle c={\frac {\ln 2}{T^{2}}}}
则有
P
(
|
X
|
⩾
t
)
⩽
1
⩽
2
e
−
c
T
2
⩽
2
e
−
c
t
2
,
{\displaystyle \mathbb {P} (|X|\geqslant t)\leqslant 1\leqslant 2e^{-cT^{2}}\leqslant 2e^{-ct^{2}},}
所以每个有界变量都是亚高斯变量。
对于随机变量
X
{\displaystyle X}
,下式范数是有限的,当且仅当
X
{\displaystyle X}
是亚高斯:
‖
X
‖
ψ
2
=
d
e
f
inf
{
c
≥
0
:
E
[
e
X
2
c
2
]
}
.
{\displaystyle \lVert X\rVert _{\psi _{2}}{\overset {\underset {\mathrm {def} }{}}{=}}\inf\{c\geq 0:\mathbb {E} [e^{\frac {X^{2}}{c^{2}}}]\}.}
然后设
X
1
,
⋯
,
X
n
{\displaystyle X_{1},\cdots ,X_{n}}
为零均值 独立亚高斯随机变量,霍夫丁不等式 的一般版本指出:
P
(
|
∑
i
=
1
n
X
i
|
⩾
t
)
⩽
2
exp
(
−
c
t
2
∑
i
=
1
n
‖
X
i
‖
ψ
2
2
)
,
{\displaystyle \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 _{\psi _{2}}^{2}}}),}
其中
c
>
0
{\displaystyle c>0}
且为绝对常数[ 5] 。
霍夫丁界的证明与切尔诺夫界等集中不等式类似[ 6] 。主要区别在于使用霍夫丁引理 :
假设
X
{\displaystyle X}
是一个真正的随机变量,那么几乎必然
X
∈
[
a
,
b
]
{\displaystyle X\in \left[a,b\right]}
。然后
E
[
e
s
(
X
−
E
[
X
]
)
]
⩽
exp
(
1
8
s
2
(
b
−
a
)
2
)
.
{\displaystyle \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).}
使用这个引理,我们可以证明霍夫丁不等式。如定理陈述,假设
X
1
,
⋯
,
X
n
{\displaystyle X_{1},\cdots ,X_{n}}
为
n
{\displaystyle n}
个独立随机变量,
X
i
∈
[
a
i
,
b
i
]
,
{\displaystyle X_{i}\in \left[a_{i},b_{i}\right],}
s
.
t
.
i
∈
N
+
{\displaystyle s.t.\ i\in N_{+}}
几乎必然 。设
S
n
=
X
1
+
⋯
+
X
n
.
{\displaystyle S_{n}=X_{1}+\cdots +X_{n}.}
那么对于
s
>
0
{\displaystyle s>0}
且
t
>
0
{\displaystyle t>0}
, 联立马尔可夫不等式 和
X
i
{\displaystyle X_{i}}
的独立性可得:
P
(
S
n
−
E
[
S
n
]
≥
t
)
=
P
(
exp
(
s
(
S
n
−
E
[
S
n
]
)
)
≥
exp
(
s
t
)
)
≤
exp
(
−
s
t
)
E
[
exp
(
s
(
S
n
−
E
[
S
n
]
)
)
]
=
exp
(
−
s
t
)
∏
i
=
1
n
E
[
exp
(
s
(
X
i
−
E
[
X
i
]
)
)
]
≤
exp
(
−
s
t
)
∏
i
=
1
n
exp
(
s
2
(
b
i
−
a
i
)
2
8
)
=
exp
(
−
s
t
+
1
8
s
2
∑
i
=
1
n
(
b
i
−
a
i
)
2
)
{\displaystyle {\begin{aligned}\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{aligned}}}
此上界对于
s
{\displaystyle s}
的值是最佳的,最小值在指数
O
(
e
n
)
{\displaystyle O(e^{n})}
范围内。这可以通过优化二次曲线轻松完成,给出
s
=
4
t
∑
i
=
1
n
(
b
i
−
a
i
)
2
.
{\displaystyle s={\frac {4t}{\sum _{i=1}^{n}(b_{i}-a_{i})^{2}}}.}
为这个值
s
{\displaystyle s}
编写上面的界限,我们得到所需的界限:
P
(
S
n
−
E
[
S
n
]
≥
t
)
≤
exp
(
−
2
t
2
∑
i
=
1
n
(
b
i
−
a
i
)
2
)
.
{\displaystyle \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).}
^ Hoeffding, Wassily. Probability Inequalities for Sums of Bounded Random Variables . Journal of the American Statistical Association. 1963-03, 58 (301) [2023-07-29 ] . ISSN 0162-1459 . doi:10.1080/01621459.1963.10500830 . (原始内容存档 于2023-06-19) (英语) .
^ Serfling, R. J. Probability Inequalities for the Sum in Sampling without Replacement . The Annals of Statistics. 1974-01, 2 (1) [2023-07-29 ] . ISSN 0090-5364 . doi:10.1214/aos/1176342611 . (原始内容存档 于2023-07-29).
^ 集中不等式 . 维基百科,自由的百科全书. 2022-03-08 (中文) .
^ Wassily Hoeffding, Probability inequalities for sums of bounded random variables, Journal of the American Statistical Association 58 (301): 13–30, March 1963. (JSTOR )(英文)
^ Vershynin, Roman. High-dimensional probability: an introduction with applications in data science . Cambridge University Press. 2018. ISBN 978-1-108-41519-4 .
^ Boucheron, Stéphane; Lugosi, Gábor; Massart, Pascal. Concentration inequalities: a nonasymptotic theory of independence . Oxford: Oxford university press. 2013 [2023-07-29 ] . ISBN 978-0-19-953525-5 . (原始内容存档 于2022-07-30).
^ Hoeffding's inequality . Wikipedia. 2023-07-02 (英语) .