伯恩施坦不等式

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

\mathbb{P}\left(\left|\frac 1n\sum_{i=1}^n{X_i}\right|>\varepsilon\right)\le2\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|\le M几乎必然成立，则对任意正数t

\mathbb{P}\left(\sum_{i=1}^n{X_i}>t\right)\le\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|\le\frac 12k!L^{k-2}\mathbb{E}X_i^2，则对0

\mathbb{P}\left(\sum_{i=1}^n{X_i}\ge 2t\sqrt{\sum{\mathbb{E}X_i^2}}\right)

3.设X_1,\cdots,X_n是独立的随机变量。若对任意整数k \ge 4，都有\mathbb{E}|X_i^k|\le\frac{k!}{4!}\left(\frac L5\right)^{k-4}，记A_k=\sum_{i=1}^n{\mathbb{E}X_i^k}，则对于0

\mathbb{P}\left(\left|\sum_{j=1}^n{X_j}-\frac{A_3t^2}{3A_2}\right|\ge\sqrt{2A_2}t\left(1+\frac{A_4t^2}{6A_2^2}\right)\right)

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}) \le R_i\mathbb{E}X_i^2,

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

则对于0，

\mathbb{P}\left(\sum_{i=1}^n{X_i}\ge 2t\sqrt{\sum_{i=1}^n{R_i\mathbb{E}X_i^2}}\right)

另见

参考资料