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

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

Нерівність Чернова — ймовірнісна нерівність, що визначає експоненційне спадання ймовірності великих відхилень суми деяких однаково розподілених незалежних випадкових величин від математичного сподівання цієї суми. Нерівність вперше була доведена американським математиком Германом Черновим[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.