Неравенство Чернова: оценка хвоста суммы Бернулли

Неравенство Чернова отвечает на вопрос: насколько маловероятно, что сумма многих независимых случайных «да/нет»-испытаний сильно отклонится от своего среднего значения? В отличие от неравенства Маркова, которое даёт лишь грубую оценку через матожидание, и неравенства Чебышёва, использующего дисперсию, метод Чернова строит границу через момент-генерирующую функцию - и получает экспоненциально убывающую оценку хвоста. Это именно то, что нужно в анализе рандомизированных алгоритмов, хеширования, балансировки нагрузки и статистических гарантий: там важно не просто «вероятность мала», а «вероятность исчезающе мала уже при умеренном числе испытаний». Ниже разберём, откуда берётся экспонента, как выводится итоговая формула и когда она реально выигрывает у более грубых оценок.

Идея метода: экспонента вместо самой величины

Пусть $X$ - случайная величина, и нужно оценить $P(X \ge a)$. Прямое применение неравенства Маркова к самой $X$ даёт лишь $E[X]/a$ - линейное затухание по $a$. Идея Чернова - применить неравенство Маркова не к $X$, а к $e^{tX}$ при произвольном $t > 0$. Событие $\{X \ge a\}$ равносильно событию $\{e^{tX} \ge e^{ta}\}$, поскольку экспонента монотонно возрастает, поэтому

$P(X \ge a) = P\big(e^{tX} \ge e^{ta}\big) \le \frac{E[e^{tX}]}{e^{ta}} = e^{-ta} M_X(t),$

где $M_X(t) = E[e^{tX}]$ - момент-генерирующая функция $X$. Это неравенство верно при любом $t > 0$, значит, верно и для наилучшего из них:

$P(X \ge a) \le \min_{t > 0} \; e^{-ta} M_X(t).$

Именно минимизация по $t$ и превращает грубую оценку в экспоненциальную: у каждой величины $t$ своя «экспонента-фильтр», и правильный выбор наклона выжимает из неё максимум информации.

Оптимальный параметр наклона и вывод оценки

Для суммы $X = X_1 + \dots + X_n$ независимых испытаний Бернулли с $P(X_i = 1) = p$ момент-генерирующая функция каждого слагаемого равна $E[e^{tX_i}] = 1 - p + p e^t$. Пользуясь неравенством $1 + x \le e^x$, получаем $1 - p + p e^t \le \exp\big(p(e^t - 1)\big)$, а по независимости момент-генерирующая функция суммы перемножается:

$M_X(t) = \prod_{i=1}^n E[e^{tX_i}] \le \exp\big(\mu (e^t - 1)\big), \qquad \mu = E[X] = np.$

Подставляя порог $a = (1+\delta)\mu$ и минимизируя $\mu(e^t - 1) - ta$ по $t$, находим оптимум в точке $t^{*} = \ln(1+\delta)$: производная $\mu e^t - a$ обращается в нуль ровно при $e^{t} = a/\mu = 1+\delta$. Видео ниже показывает именно этот шаг - как меняется значение оценки при разных $t$ и где именно достигается минимум.

Рассчитать для своей задачи

Подставив $t^{*}$ обратно, получаем точную форму границы $\big[e^{\delta}/(1+\delta)^{1+\delta}\big]^{\mu}$. Дальнейшее алгебраическое огрубление этого выражения (стандартный приём, вынесенный за скобки в любом учебнике по вероятностным методам) даёт удобную и часто цитируемую форму без степенных выражений.

Мультипликативная граница для суммы Бернулли

Итоговая мультипликативная граница Чернова для верхнего хвоста при любом $\delta > 0$:

$P\big(X \ge (1+\delta)\mu\big) \le \exp\left(-\frac{\delta^2 \mu}{2+\delta}\right).$

Для нижнего хвоста при $0 < \delta < 1$ действует похожая, но более крутая оценка:

$P\big(X \le (1-\delta)\mu\big) \le \exp\left(-\frac{\delta^2 \mu}{2}\right).$

Обе оценки зависят только от среднего $\mu = np$ и относительного отклонения $\delta$ - не нужно знать форму распределения каждого $X_i$, достаточно независимости и ограниченности значений $0$ и $1$. Калькулятор выше считает верхнюю оценку для любых $n$, $p$ и $\delta$ и сразу сравнивает её с точным биномиальным значением. Видео ниже показывает, как ведут себя все три оценки хвоста при изменении $\delta$:

Рассчитать для своей задачи

Сравнение с неравенством Чебышёва

И неравенство Маркова, и неравенство Чебышёва, и неравенство Чернова решают одну задачу - оценить хвост распределения без знания его точной формы, но с разной «ценой информации»:

При маленьких $\delta$ разница невелика: для $n=1000$, $p=0{,}5$ обе границы почти совпадают около $\delta \approx 0{,}1$ (обе дают порядка 9-10 %), и при $\delta$ чуть меньше этого порога Чебышёв даже немного точнее. Но при $\delta = 0{,}5$ граница Чернова падает до $\approx 1{,}9 \cdot 10^{-22}$, тогда как граница Чебышёва даёт лишь $0{,}4\,\%$ - разрыв в девятнадцать порядков. Это и есть главное преимущество метода Чернова: он «спасает» оценку именно там, где дисперсии уже недостаточно.

Рассчитать для своей задачи

Пример: 1000 подбрасываний монеты

Разберём вычисление руками на дефолтных значениях калькулятора. Пусть $n = 1000$ честных монет ($p = 0{,}5$), интересует вероятность выпадения не менее $550$ орлов, то есть $\delta = 0{,}1$ относительно среднего $\mu = np = 500$.

Порог: $a = (1+\delta)\mu = 1{,}1 \cdot 500 = 550$. Подставляем в мультипликативную границу:

$P(X \ge 550) \le \exp\left(-\frac{0{,}1^2 \cdot 500}{2{,}1}\right) = \exp(-2{,}381) \approx 0{,}0925,$

то есть не более $9{,}25\,\%$. Для сравнения, граница Чебышёва в этой же точке даёт $0{,}5/(1000 \cdot 0{,}5 \cdot 0{,}01) = 0{,}1$, то есть $10\,\%$ - немного грубее. Точное биномиальное значение $P(X \ge 550)$ оказывается заметно меньше обеих границ, около $0{,}09\,\%$: обе оценки честны (вероятность действительно не превышает заявленного предела), но не точны - это нормально для верхних границ, их сила в гарантии, а не в точности.

Где применяется неравенство Чернова

В анализе рандомизированных алгоритмов неравенство Чернова - стандартный инструмент доказательства «концентрации»: например, что случайное распределение задач по $n$ серверам почти наверняка близко к равномерному, или что случайная хеш-функция почти наверняка не создаёт длинных цепочек коллизий. В статистике оно лежит в основе PAC-обучения и границ обобщения в машинном обучении: чем больше независимых наблюдений, тем экспоненциально быстрее сужается доверительный интервал вокруг истинного параметра. В теории больших уклонений неравенство Чернова - простейший, но рабочий инструмент; более тонкие версии (Бернштейна, Беннета) добавляют поправки для случаев, когда отдельные слагаемые не ограничены единицей.

Частые ошибки

• Применять мультипликативную форму к событию $X \le (1-\delta)\mu$ с формулой верхнего хвоста. У нижнего и верхнего хвостов разные показатели экспоненты ($\delta^2\mu/2$ против $\delta^2\mu/(2+\delta)$) - их нельзя путать местами.
• Забывать про независимость слагаемых. Вывод опирается на то, что момент-генерирующая функция суммы равна произведению момент-генерирующих функций слагаемых; для зависимых величин это неверно, и граница просто неприменима без дополнительных условий.
• Считать оценку Чернова точной. Как и граница Маркова, это верхняя граница «в худшем случае»: истинная вероятность обычно на порядки меньше, и путать одно с другим - типичная ошибка в учебных задачах.
• Использовать формулу при малых $\mu$. Оценка становится содержательной, когда $\mu$ достаточно велико (десятки и больше); для $\mu \approx 1$ экспонента даёт немного лучше тривиального $P \le 1$.
• Игнорировать диапазон $\delta$. Формула нижнего хвоста работает только при $0 < \delta < 1$ (иначе порог $(1-\delta)\mu$ становится отрицательным и теряет смысл), а верхняя работает при любом $\delta > 0$.

FAQ

В чём разница между неравенством Чернова и неравенством Хёфдинга? Оба относятся к семейству границ, полученных через момент-генерирующую функцию. Неравенство Чернова в классической форме заточено под сумму испытаний Бернулли (или ограниченных величин с известным средним $p_i$), тогда как неравенство Хёфдинга работает для суммы произвольных независимых величин, ограниченных отрезком, и не требует знания их точного распределения внутри отрезка.

Почему граница Чернова экспоненциальна, а Чебышёва - только полиномиальна? Потому что Чебышёв использует лишь второй момент (дисперсию), а Чернов - всю момент-генерирующую функцию, то есть фактически бесконечно много моментов сразу. Больше информации о распределении даёт более крутое затухание хвоста.

Можно ли применить неравенство Чернова к не-бернуллиевским слагаемым? Да, общая форма $P(X \ge a) \le \min_{t>0} e^{-ta} M_X(t)$ работает для любой суммы независимых величин с конечной момент-генерирующей функцией; конкретный вид итоговой экспоненты зависит от того, как выглядит $M_X(t)$ для этих слагаемых - для Бернулли получается разобранная выше формула.

Коротко

Неравенство Чернова оценивает хвост суммы независимых испытаний Бернулли через момент-генерирующую функцию и оптимальный выбор параметра наклона $t^{*} = \ln(1+\delta)$. Итоговая мультипликативная граница $P(X \ge (1+\delta)\mu) \le \exp(-\delta^2\mu/(2+\delta))$ убывает экспоненциально по $\mu$ и при заметных отклонениях на порядки точнее полиномиальной границы Чебышёва, хотя при малых $\delta$ обе оценки сопоставимы. Это делает метод Чернова базовым инструментом доказательства концентрации в рандомизированных алгоритмах, статистике и теории больших уклонений.