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

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

В неочевидному випадку нерівності, коли можна розглядати дві змінні і Тоді за означенням відстань Кульбака — Лейблера для цих змінних є рівною:

У цих позначеннях першу нерівність можна також записати у такій формі, яка часто зустрічається у літературі:

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

Нехай тепер і розглянемо функцію . Для вказаного для цієї функції і Також:

.

Таким чином є єдиним коренем похідної (зважаючи на властивості усіх чисел в означенні функції) і у цій точці функція має мінімум адже і функція спадає в точці 1 () перед тим як почати зростання.

Відповідно можна взяти для мінімального обмеження ймовірності.

Підставивши це значення одержується варіант нерівності Чернова:

Позначимо і розглянемо функцію:

Її перші дві похідні є рівними:

і

Для випадку також і тому Також безпосередньо із виразів для похідних і тому із формули Тейлора із залишковим членом у формі Лагранжа: для деякого s, що Але із цього виразу і попередньої нерівності випливає, що для також

Проекспоненціювавши цю нерівність і піднісши до степеня n отримуємо:

Звідси остаточно:

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

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

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

Примітки

Див. також Нерівність Маркова

Література C. McDiarmid, Concentration, In Probabilistic Methods for Algorithmic Discrete Mathematics, ed. M. Habib, C. McDiarmid, J. Ramirez-Alfonsin, B. Reed, (Springer, 1998), 195-248.