伯恩施坦不等式

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

另見

• 集中不等式