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

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

Нерівність

Нехай ${\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 (**).}$

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