伯恩施坦不等式 在概率论中，伯恩施坦不等式（Bernstein inequalities）给出了随机变量的和对平均值偏离的概率。在最简单的情况下，设 X 1 , ⋯ , X n {\displaystyle X_{1},\cdots ,X_{n}} 是独立的伯努利随机变量，取值+1和-1的概率各是1/2，则对任意正数 ε {\displaystyle \varepsilon } P ( | 1 n ∑ i = 1 n X i | > ε ) ≤ 2 exp ( − n ε 2 2 ( 1 + ε / 3 ) ) {\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.设 X 1 , ⋯ , X n {\displaystyle X_{1},\cdots ,X_{n}} 是数学期望为0的独立的随机变量。若对所有 i {\displaystyle i} ， | X i | ≤ M {\displaystyle |X_{i}|\leq M} 几乎必然成立，则对任意正数 t {\displaystyle t} P ( ∑ i = 1 n X i > t ) ≤ exp ( − t 2 / 2 ∑ E X j 2 + M t / 3 ) {\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.设 X 1 , ⋯ , X n {\displaystyle X_{1},\cdots ,X_{n}} 是独立的随机变量。若存在正实数 L {\displaystyle L} ，使得对任意整数 k > 1 {\displaystyle k>1} ，都有 E | X i k | ≤ 1 2 k ! L k − 2 E X i 2 {\displaystyle \mathbb {E} |X_{i}^{k}|\leq {\frac {1}{2}}k!L^{k-2}\mathbb {E} X_{i}^{2}} ，则对 0 < t < 1 2 L ∑ E X j 2 {\displaystyle 0<t<{\frac {1}{2L}}{\sqrt {\sum {\mathbb {E} X_{j}^{2}}}}} P ( ∑ i = 1 n X i ≥ 2 t ∑ E X i 2 ) < exp ( − t 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.设 X 1 , ⋯ , X n {\displaystyle X_{1},\cdots ,X_{n}} 是独立的随机变量。若对任意整数 k ≥ 4 {\displaystyle k\geq 4} ，都有 E | X i k | ≤ k ! 4 ! ( L 5 ) k − 4 {\displaystyle \mathbb {E} |X_{i}^{k}|\leq {\frac {k!}{4!}}\left({\frac {L}{5}}\right)^{k-4}} ，记 A k = ∑ i = 1 n E X i k {\displaystyle A_{k}=\sum _{i=1}^{n}{\mathbb {E} X_{i}^{k}}} ，则对于 0 < t ≤ 5 2 A 2 4 L {\displaystyle 0<t\leq {\frac {5{\sqrt {2A_{2}}}}{4L}}} P ( | ∑ j = 1 n X j − A 3 t 2 3 A 2 | ≥ 2 A 2 t ( 1 + A 4 t 2 6 A 2 2 ) ) < 2 exp ( − t 2 ) {\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）可以推广成以下形式。 X 1 , ⋯ , X n {\displaystyle X_{1},\cdots ,X_{n}} 可以不是独立随机变量。若对任意正整数 i {\displaystyle i} ， E ( X i | X 1 , ⋯ , X i − 1 ) = 0 , {\displaystyle \mathbb {E} (X_{i}|X_{1},\cdots ,X_{i-1})=0,} E ( X i 2 | X 1 , ⋯ , X i − 1 ) ≤ R i E X i 2 , {\displaystyle \mathbb {E} (X_{i}^{2}|X_{1},\cdots ,X_{i-1})\leq R_{i}\mathbb {E} X_{i}^{2},} E ( X i k | X 1 , ⋯ , X i − 1 ) ≤ k ! L k − 2 2 E ( X i 2 | X 1 , ⋯ , X i − 1 ) , {\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}),} 则对于 0 < t < 1 2 L ∑ i = 1 n R i E X i 2 {\displaystyle 0<t<{\frac {1}{2L}}{\sqrt {\sum _{i=1}^{n}{R_{i}\mathbb {E} X_{i}^{2}}}}} ， P ( ∑ i = 1 n X i ≥ 2 t ∑ i = 1 n R i E X i 2 ) < exp ( − t 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})}} 另见 集中不等式参考资料 ^ S.N.Bernstein, "On a modification of Chebyshev’s inequality and of the error formula of Laplace" vol. 4, #5 (original publication: Ann. Sci. Inst. Sav. Ukraine, Sect. Math. 1, 1924) ^ Bernstein, S. N. (1937). "Об определенных модификациях неравенства Чебышева" [On certain modifications of Chebyshev's inequality]. Doklady Akademii Nauk SSSR. 17 (6): 275–277. ^ S.N.Bernstein, "Theory of Probability" (俄语), Moscow, 1927 ^ J.V.Uspensky, "Introduction to Mathematical Probability", McGraw-Hill Book Company, 1937
