Все формулы РФ

Математика / Вероятность и статистика

Граница Чернова для верхнего хвоста биномиальной суммы

Граница Чернова даёт экспоненциальную верхнюю оценку вероятности большого превышения среднего у суммы независимых индикаторов. Она ограничивает хвост, а не вычисляет его точное значение.

Опубликовано: Обновлено:

Ручной расчетСтраницы с задачами и решениямиЕсть историческая справкаДиагностика условий

Формула

$$\Pr(X\ge(1+\delta)\mu)\le\exp\!\left(-\frac{\mu\delta^2}{2+\delta}\right),\quad\delta>0$$
Схема Гарантированные границы двух хвостов
00.050.0498t=454.54e−5t=60

Для μ=30: пороги 45 и 60 соответствуют δ=0,5 и 1. Правые части exp(−3) и exp(−10).

Обозначения

$X$
сумма независимых индикаторов, счёт
$μ$
математическое ожидание X, положительное, счёт
$δ$
относительное превышение среднего, доля
$exp$
экспоненциальная функция

Условия применения

X=ΣX_i, где независимые X_i принимают 0 и 1, μ=ΣE[X_i]>0. Рассматривается верхний хвост и δ>0. Для биномиального закона μ=np; одинаковость вероятностей отдельных индикаторов не обязательна для этой версии границы.

Ограничения

Оценка обычно завышает истинную вероятность и может быть грубой около среднего. Зависимость индикаторов не входит в данное условие и требует другого обоснования. Для нижнего хвоста нужна соответствующая отдельная формула; механическая подстановка отрицательного δ в эту запись недопустима.

Подробное объяснение

Граница Чернова не вычисляет точную массу биномиального закона. Она заменяет трудную сумму вероятностей простым выражением, которое гарантированно не меньше истинного верхнего хвоста. Параметр δ измеряет относительное превышение среднего μ.

Экспонента возникает из неравенства Маркова, применённого к exp(tX), и оптимального выбора t. Поэтому оценка особенно полезна при больших n: даже грубая граница быстро становится малой.

Нельзя применять формулу к нижнему хвосту без соответствующей версии и нельзя забывать, что независимость испытаний входит в вывод. Для умеренных порогов точный биномиальный расчёт может быть заметно точнее.

В алгоритмах и контроле качества граница отвечает на вопрос «насколько гарантированно событие редко», когда точная вероятность не нужна или слишком дорога.

Более точная мультипликативная форма содержит [e^δ/(1+δ)^(1+δ)]^μ. Приведённая экспонента проще для ручного расчёта и даёт более слабую, но сохраняющую гарантию оценку. Эти формы нельзя смешивать по коэффициентам: знаменатель 2+δ относится именно к выбранному упрощению.

Как пользоваться формулой

  1. Убедитесь, что величина является суммой независимых индикаторов, и вычислите её среднее μ по вероятностям всех слагаемых.
  2. Для порога t>μ найдите относительное превышение δ=t/μ−1; не путайте его с абсолютной разностью t−μ.
  3. Вычислите показатель −μδ²/(2+δ), затем экспоненту, сохраняя знак и скобки знаменателя.
  4. Запишите результат как верхнюю границу, сравните с единицей и при доступном биномиальном законе проверьте точный хвост отдельно.

Историческая справка

Экспоненциальные оценки концентрации связывают вероятностную задачу с производящей функцией моментов. Вместо применения Маркова непосредственно к X его применяют к положительной exp(sX), а параметр s затем выбирают для уменьшения верхней границы.

Название Чернова закрепилось за этим подходом к экспоненциальным хвостам. В современных курсах рандомизированных алгоритмов рассматривают несколько упрощённых вариантов, зависящих от способа параметризации порога. Курс MIT2009 года выделяет границы Чернова в отдельную лекцию. Поэтому при ссылке на название недостаточно сказать «по Чернову»: нужно указать конкретную правую часть, направление хвоста и условия независимости, как сделано в данной статье.

Историческая линия формулы

Название связывает метод с Германом Черновым и традицией экспоненциальных вероятностных оценок. Разные учебные формы получаются дополнительными неравенствами из более точной оптимизированной границы; здесь приведена версия с знаменателем 2+δ для верхнего хвоста.

Пример

Пусть X~Bin(100;0,3), среднее μ=30. Нужно ограничить вероятность не менее 45 успехов. Относительное превышение δ=45/30−1=0,5. Подстановка: P(X≥45)≤exp[−30·0,5²/(2+0,5)]=exp(−3)≈0,04978707. Ответ: вероятность не превосходит примерно 4,979%. Это оценка сверху, а не точное значение хвоста. Проверка порога: (1+δ)μ=1,5·30=45. Если ошибочно взять δ=15 как абсолютное превышение, показатель изменится во много раз и гарантия перестанет относиться к заявленному событию. При δ→0 правая часть стремится к 1: малая прибавка к среднему не объявляется экспоненциально редкой только из-за большого числа испытаний.

Частая ошибка

Не заменяйте δ относительного превышения числом лишних успехов. Не выдавайте exp(−3) за точную вероятность. Не применяйте верхнюю границу к нижнему хвосту отрицательным δ. Не забывайте независимость индикаторов; одинаковое среднее зависимой суммы не гарантирует ту же концентрацию.

Практика

Задачи с решением

Превышение вдвое

Условие. μ=20. Оцените вероятность X≥40 для суммы независимых индикаторов.

Решение. δ=1; граница exp(−20/(2+1))=exp(−20/3)≈0,0012726338.

Ответ. Не более 0,0012726338.

Перевод порога

Условие. μ=50,t=60. Найдите δ и оценку верхнего хвоста.

Решение. δ=60/50−1=0,2. Показатель−50·0,04/2,2=−10/11; граница exp(−10/11)≈0,40289032.

Ответ. δ=0,2; вероятность не более 0,40289032.

Дополнительные источники

  • https://ocw.mit.edu/courses/18-409-topics-in-theoretical-computer-science-an-algorithmists-toolkit-fall-2009/resources/mit18_409f09_scribe16/
  • https://probabilitycomputing.github.io/CMU%20Lecture%20Notes.pdf

Связанные формулы

Математика

Неравенство Маркова для хвостовой вероятности

$P(X\ge a)\le\frac{E[X]}{a},\qquad X\ge0,\ a>0$

Неравенство Маркова даёт верхнюю границу вероятности большого значения неотрицательной случайной величины через её среднее. Оно работает без знания точного распределения, поэтому граница может быть грубой, но остаётся гарантированной при выполнении условий.

Математика

Вероятность в биномиальном распределении

$P(X=k)=C_n^kp^k(1-p)^{n-k}$

Формула «Вероятность в биномиальном распределении» задает численную характеристику вероятностной модели. Она переводит исходы, вероятности или наблюдения в показатель, который удобно считать, сравнивать и проверять.

Математика

Граница Буля—Бонферрони для объединения событий

$\Pr\!\left(\bigcup_{i=1}^{m}A_i\right)\le\min\!\left(1,\sum_{i=1}^{m}\Pr(A_i)\right)$

Вероятность хотя бы одного из нескольких событий не превосходит суммы их вероятностей. Граница работает без независимости и позволяет контролировать общую ошибку по отдельным рискам.