Нерівність Чернова

Нерівність Чернова — ймовірнісна нерівність, що визначає експоненційне спадання ймовірності великих відхилень суми деяких однаково розподілених незалежних випадкових величин від математичного сподівання цієї суми. Нерівність вперше була доведена американським математиком Германом Черновим для величин з розподілом Бернуллі. Згодом було одержано багато узагальнень та посилень нерівності, які теж часто називають нерівностями Чернова

Нерівність

Нехай ${\displaystyle X_{1},X_{2},\ldots ,X_{n}}$ — незалежні випадкові величини з розподілом Бернуллі ${\displaystyle \,X_{i}\sim {\mbox{bernoulli}}(p)).}$ Тоді для довільного ${\displaystyle t\geqslant 0}$ виконується нерівність:

${\displaystyle \Pr \left[|\sum _{i=1}^{n}X_{i}-np|>tn\right]<2e^{-2nt^{2}}}$

Доведення

Нехай ${\displaystyle m=n(p+t),h>0.\,}$ Тоді з нерівності Маркова випливає:

${\displaystyle \Pr \left[S_{n}\geqslant m\right]=\Pr \left[e^{hS_{n}}\geqslant e^{hm}\right]\leqslant {\frac {\mathbf {E} \left[e^{hS_{m}}\right]}{e^{hm}}}={\prod _{i}E[e^{hX_{i}}] \over e^{hm}}={\prod _{i}(1-p+pe^{h})^{n}] \over e^{hm}}.}$

Якщо ${\displaystyle 0<t<1-p}$ то можна взяти ${\displaystyle e^{h}={\frac {(p+t)(i-p)}{p(1-p-t)}}}$ для обмеження даного числа, внаслідок чого:

${\displaystyle \Pr \left[\sum _{i=1}^{n}X_{i}-np>tn\right]<e^{-2nt^{2}}.\quad (*)}$

Згідно з неперервністю твердження також справедливе для t = 1 - p. Для t = 0 і t > 1 - p нерівність очевидна.

Якщо визначити ${\displaystyle Y_{i}=1-X_{i}}$ і скористатися нерівністю (*) одержимо також:

${\displaystyle \Pr \left[\sum _{i=1}^{n}X_{i}-np>-tn\right]<e^{-2nt^{2}}.\quad (**).}$

Разом нерівності (*) і (**) утворюють нерівність Чернова, що завершує доведення.

Примітки

1. Herman Chernoff (1952). "A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations". Annals of Mathematical Statistics 23 (4): 493–507

Див. також

• Нерівність Маркова

Література

• C. McDiarmid, Concentration, In Probabilistic Methods for Algorithmic Discrete Mathematics, ed. M. Habib, C. McDiarmid, J. Ramirez-Alfonsin, B. Reed, (, 1998), 195-248.