伯恩施坦不等式

在概率论中，伯恩施坦不等式（Bernstein inequalities）给出了随机变量的和对平均值偏离的概率。在最简单的情况下，设${\displaystyle X_{1},\cdots ,X_{n}}$是独立的伯努利随机变量，取值+1和-1的概率各是1/2，则对任意正数${\displaystyle \varepsilon }$

${\displaystyle \mathbb {P} \left(\left|{\frac {1}{n}}\sum _{i=1}^{n}{X_{i}}\right|>\varepsilon \right)\leq 2\exp {\left(-{\frac {n\varepsilon ^{2}}{2(1+\varepsilon /3)}}\right)}}$

伯恩施坦不等式由谢尔盖·伯恩施坦于1920年代证明，并于1930年代发表^[1][2][3][4]。之后，这些不等式多次被其他数学家独立地发现。因此，伯恩施坦不等式的一些特例也被称为Chernoff界，Hoeffding不等式，以及吾妻不等式。

不等式

1.设${\displaystyle X_{1},\cdots ,X_{n}}$是数学期望为0的独立的随机变量。若对所有${\displaystyle i}$，${\displaystyle |X_{i}|\leq M}$几乎必然成立，则对任意正数${\displaystyle t}$

${\displaystyle \mathbb {P} \left(\sum _{i=1}^{n}{X_{i}}>t\right)\leq \exp {\left(-{\frac {t^{2}/2}{\sum {\mathbb {E} X_{j}^{2}}+Mt/3}}\right)}}$

2.设${\displaystyle X_{1},\cdots ,X_{n}}$是独立的随机变量。若存在正实数${\displaystyle L}$，使得对任意整数${\displaystyle k>1}$，都有${\displaystyle \mathbb {E} |X_{i}^{k}|\leq {\frac {1}{2}}k!L^{k-2}\mathbb {E} X_{i}^{2}}$，则对${\displaystyle 0<t<{\frac {1}{2L}}{\sqrt {\sum {\mathbb {E} X_{j}^{2}}}}}$

${\displaystyle \mathbb {P} \left(\sum _{i=1}^{n}{X_{i}}\geq 2t{\sqrt {\sum {\mathbb {E} X_{i}^{2}}}}\right)<\exp {(-t^{2})}}$

3.设${\displaystyle X_{1},\cdots ,X_{n}}$是独立的随机变量。若对任意整数${\displaystyle k\geq 4}$，都有${\displaystyle \mathbb {E} |X_{i}^{k}|\leq {\frac {k!}{4!}}\left({\frac {L}{5}}\right)^{k-4}}$，记${\displaystyle A_{k}=\sum _{i=1}^{n}{\mathbb {E} X_{i}^{k}}}$，则对于${\displaystyle 0<t\leq {\frac {5{\sqrt {2A_{2}}}}{4L}}}$

${\displaystyle \mathbb {P} \left(\left|\sum _{j=1}^{n}{X_{j}}-{\frac {A_{3}t^{2}}{3A_{2}}}\right|\geq {\sqrt {2A_{2}}}t\left(1+{\frac {A_{4}t^{2}}{6A_{2}^{2}}}\right)\right)<2\exp {(-t^{2})}}$

4.伯恩施坦也把以上不等式推广到弱相关随机变量的情况。例如，不等式（2）可以推广成以下形式。${\displaystyle X_{1},\cdots ,X_{n}}$可以不是独立随机变量。若对任意正整数${\displaystyle i}$，

${\displaystyle \mathbb {E} (X_{i}|X_{1},\cdots ,X_{i-1})=0,}$

${\displaystyle \mathbb {E} (X_{i}^{2}|X_{1},\cdots ,X_{i-1})\leq R_{i}\mathbb {E} X_{i}^{2},}$

${\displaystyle \mathbb {E} (X_{i}^{k}|X_{1},\cdots ,X_{i-1})\leq {\frac {k!L^{k-2}}{2}}\mathbb {E} (X_{i}^{2}|X_{1},\cdots ,X_{i-1}),}$

则对于${\displaystyle 0<t<{\frac {1}{2L}}{\sqrt {\sum _{i=1}^{n}{R_{i}\mathbb {E} X_{i}^{2}}}}}$，

${\displaystyle \mathbb {P} \left(\sum _{i=1}^{n}{X_{i}}\geq 2t{\sqrt {\sum _{i=1}^{n}{R_{i}\mathbb {E} X_{i}^{2}}}}\right)<\exp {(-t^{2})}}$

另见

• 集中不等式

参考资料

1. S.N.Bernstein, "On a modification of Chebyshev’s inequality and of the error formula of Laplace" vol. 4, #5 (original publication: Ann. Sci. Inst. Sav. Ukraine, Sect. Math. 1, 1924)
2. Bernstein, S. N. (1937). "Об определенных модификациях неравенства Чебышева" [On certain modifications of Chebyshev's inequality]. Doklady Akademii Nauk SSSR. 17 (6): 275–277.
3. S.N.Bernstein, "Theory of Probability" (俄语), Moscow, 1927
4. J.V.Uspensky, "Introduction to Mathematical Probability", McGraw-Hill Book Company, 1937