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

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

НерівністьРедагувати

Нехай   — незалежні випадкові величини з розподілом Бернуллі   Тоді для довільного   виконується нерівність:

 

ДоведенняРедагувати

Нехай   Тоді з нерівності Маркова випливає:

 

Якщо   то можна взяти   для обмеження даного числа, внаслідок чого:

 

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

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

 

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

ПриміткиРедагувати

  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.