伯恩施坦不等式

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

$\mathbb{P}(\left|\frac{1}{n}\sum _{i=1}^n{X}_i\right|>\epsilon )\le 2\exp (-\frac{n{\epsilon }^2}{2(1+\epsilon /3)})$

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

不等式

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

$\mathbb{P}(\sum _{i=1}^n{X}_i>t)\le \exp (-\frac{t^2/2}{\sum 𝔼X_j^2+Mt/3})$

2.设$X_1,\cdots ,X_n$是独立的随机变量。若存在正实数$L$，使得对任意整数$k>1$，都有$𝔼|X_i^k|\le \frac{1}{2}k!L^{k-2}𝔼X_i^2$，则对$0<t<\frac{1}{2L}\sqrt{\sum 𝔼X_j^2}$

$\mathbb{P}(\sum _{i=1}^n{X}_i\ge 2t\sqrt{\sum 𝔼X_i^2})<\exp (-t^2)$

3.设$X_1,\cdots ,X_n$是独立的随机变量。若对任意整数$k\ge 4$，都有$𝔼|X_i^k|\le \frac{k!}{4!}{\left(\frac{L}{5}\right)}^{k-4}$，记$A_k=\sum _{i=1}^n𝔼X_i^k$，则对于$0<t\le \frac{5\sqrt{2A_2}}{4L}$

$\mathbb{P}(|\sum _{j=1}^n{X}_j-\frac{A_3{t}^2}{3A_2}|\ge \sqrt{2A_2}t(1+\frac{A_4{t}^2}{6A_2^2}))<2\exp (-t^2)$

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

$𝔼(X_i|X_1,\cdots ,X_{i-1})=0,$

$𝔼(X_i^2|X_1,\cdots ,X_{i-1})\le R_i𝔼X_i^2,$

$𝔼(X_i^k|X_1,\cdots ,X_{i-1})\le \frac{k!L^{k-2}}{2}𝔼(X_i^2|X_1,\cdots ,X_{i-1}),$

则对于$0<t<\frac{1}{2L}\sqrt{\sum _{i=1}^n{R}_i𝔼X_i^2}$，

$\mathbb{P}(\sum _{i=1}^n{X}_i\ge 2t\sqrt{\sum _{i=1}^n{R}_i𝔼X_i^2})<\exp (-t^2)$

另见

• 集中不等式