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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

Нерівність[ред.ред. код]

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

\Pr \left[\sum_{i=1}^n |X_i - np| > tn \right] < 2 e^{-2nt^2}

Доведення[ред.ред. код]

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

\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}}.

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

\Pr \left[\sum_{i=1}^n X_i - np > tn \right] <  e^{-2nt^2}. \quad (*)

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

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

\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, (Springer, 1998), 195-248.