伯恩施坦不等式

在機率論中，伯恩施坦不等式（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})}$

另見

• 集中不等式