伯恩施坦不等式

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

$\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年代发表。之后，这些不等式多次被其他数学家独立地发现。因此，伯恩施坦不等式的一些特例也被称为Chernoff界，Hoeffding不等式，以及吾妻不等式。

不等式

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

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

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

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

$\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）可以推广成以下形式。$X_{1},\cdots ,X_{n}$可以不是独立随机变量。若对任意正整数$i$，

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

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

$\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}),$

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

$\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})}$

另见

• 集中不等式