Кратко — формула, интуиция, области применения и когда плохо.
1) Формула (биномиальное $X\sim \mathrm{Bin}(n,p)$). Для любого $\epsilon >0$ $$P(\frac{X}{n}\ge p+\epsilon )\le \exp (-nD(p+\epsilon \Vert p)),$$ где
$$D(q\Vert p)=q\ln \frac{q}{p}+(1-q)\ln \frac{1-q}{1-p}$$ — относительная энтропия (Kullback–Leibler). Аналогично для левого хвоста с $q=p-\epsilon$. Более простые (но обычно слабее) варианты: Хёффдинг
P ⁣(∣Xn−p∣≥ε)≤2exp⁡(−2nε2), P\!\Big(\big|\tfrac{X}{n}-p\big|\ge\varepsilon\Big)\le 2\exp(-2n\varepsilon^2),
P( nX −p ≥ε)≤2exp(−2nε2), и (Bernstein/Bennett) с учётом дисперсии:
$$P(\frac{X}{n}-p\ge \epsilon )\le \exp (-\frac{n{\epsilon }^2}{2p(1-p)+\frac{2}{3}\epsilon }).$$
2) Интуиция. Chernoff получается из mgf/метода экспоненциального наклона: выбирают оптимальный экспоненциальный фактор, чтобы минимизировать оценку. Функция $D(q\Vert p)$ — скорость (rate function) в т.ч. из теоремы Крамера: для фиксированного отклонения $\epsilon >0$ вероятность убывает экспоненциально как $\exp (-n\cdot \text{скорость})$. Это даёт правильный показатель в экспоненте (асимптотически точный порядок экспоненты).
3) Связь с гауссовской аппроксимацией (малые отклонения). Для малых $\epsilon$ имеем разложение
$$D(p+\epsilon \Vert p)=\frac{{\epsilon }^2}{2p(1-p)}+O({\epsilon }^3).$$ Следовательно при $\epsilon \to 0$ и $n{\epsilon }^2\to \infty$ крайние вероятности примерно равны
$$P(\frac{X}{n}\approx p+\epsilon )\asymp \exp (-\frac{n{\epsilon }^2}{2p(1-p)}),$$ что совпадает по главному показателю с CLT/квадратичной аппроксимацией (модератные отклонения). Если же $\epsilon =O(1/\sqrt{n})$, то надо использовать CLT/точные приближения с коэффициентами (Edgeworth), потому что Chernoff даёт только экспоненциальный порядок и теряет предэкспоненциальный множитель.
4) Когда Chernoff/простые оценки работают хорошо
- фиксированное $p\in (0,1)$ и фиксированное $\epsilon >0$ (отклонения порядка $\Theta (n)$): оценка даёт правильный экспоненциальный темп и часто достаточно точна;
- модератные отклонения с $\epsilon \to 0$, но $n{\epsilon }^2\to \infty$: квадратичная аппроксимация по $D$ делает оценку согласованной с нормальной.
5) Когда приближения работают плохо (и почему)
- очень малые отклонения $\epsilon \ll 1/\sqrt{n}$: вероятности не экспоненциально малы, Chernoff даёт неинформативные или слишком грубые пределы; лучше CLT/точные локальные приближения;
- когда важен предэкспоненциальный множитель (мелкие вероятности, где требуется точная численность), а не только экспонента — Chernoff пропускает полные константы (нужны Bahadur–Rao, локальные формулы, Edgeworth);
- разрежённый режим $p=p_n\to 0$ (или $p_n\to 0$, $n{p}_n$ фикс.): оптимальнее Пуассоновское приближение; KL-оценка может давать корректный темп, но по точности (и по предэкспоненту) хуже, чем прямой анализ Пуассона;
- крайние случаи у границы $p\to 0$ или $p\to 1$ вместе с малыми абсолютными числами успехов: дисперсия малы, и поведение хвостов диктуется пуассоноподобными эффектами; простые Хёффдинг‑оценки особенно сильно расходятся, так как они отталкиваются от наихудшей дисперсии $1/4$;
- когда нужна очень точная численная оценка для конечных $n$: Chernoff часто консервативен (в примере ниже видно, во сколько раз).
6) Небольшой численный пример (иллюстрация потерянных предэкспонент):
Пусть $n=1000,p=0.01$. Событие $X\ge 20$ даёт $q=20/1000=0.02$, $\epsilon =0.01$.
Квадратичная аппроксимация: $nD\approx n\cdot \frac{{\epsilon }^2}{2p(1-p)}\approx 5.05$, значит Chernoff даёт
$$P(X\ge 20)\lesssim e^{-5.05}\approx 6.4\cdot 10^{-3}.$$ По CLT: $\mathbb{E}X=10,\sigma \approx \sqrt{9.9}\approx 3.15$, сдвиг $(20-10)/\sigma \approx 3.18$ даёт настоящую вероятность порядка $7\cdot 10^{-4}$. То есть Chernoff правильно предсказывает экспоненциальный характер малости, но в данном конечном примере консервативен в ~9 раз по величине (предэкспоненциальный множитель).
7) Выводы — практические рекомендации
- Для оценки больших отклонений порядка $\Theta (n)$ или модератных ($n{\epsilon }^2\to \infty$) Chernoff/KL — естественный инструмент (правильный скоростной показатель).
- Для малых отклонений ($\epsilon =O(1/\sqrt{n})$) и для точных численных оценок используйте CLT/Edgeworth/локальную теорию; для разрежённых случаев ($p\to 0$, $np$ фикс.) — Пуассоновскую аппроксимацию.
- Если нужно не только экспоненциальный порядок, а точные вероятности — применяют уточнённые асимптотики (Bahadur–Rao) или вычисления сумм/интегралов напрямую.
Если нужно, могу показать вывод Chernoff‑формулы через mgf и оптимизацию экспоненциального множителя или привести сравнение для нескольких числовых пар $(n,p,k)$.