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

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

Нерівність

Нехай $X_1,X_2,\dots ,X_n$ — незалежні випадкові величини з розподілом Бернуллі $X_i\sim \text{bernoulli}(p)).$ Тоді для довільного $t⩾0$ виконується нерівність:

$\mathrm{Pr}[|\sum _{i=1}^n{X}_i-np|>tn]<2e^{-2n{t}^2}$

Доведення

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

$\mathrm{Pr}[S_n⩾m]=\mathrm{Pr}[e^{h{S}_n}⩾e^{hm}]⩽\frac{𝐄\left[e^{h{S}_m}\right]}{e^{hm}}=\frac{\prod _{i}E[e^{h{X}_i}]}{e^{hm}}=\frac{\prod _i(1-p+p{e}^h{)}^n]}{e^{hm}}.$

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

$\mathrm{Pr}[\sum _{i=1}^n{X}_i-np>tn]<e^{-2n{t}^2}.(*)$

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

Якщо визначити $Y_i=1-X_i$ і скористатися нерівністю (*) одержимо також:

$\mathrm{Pr}[\sum _{i=1}^n{X}_i-np>-tn]<e^{-2n{t}^2}.(**).$

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

Див. також

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

Література

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