Метод доказательства (обобщённая схема). Пусть $X$ — дискретная случайная величина, нужно оценить правую хвостовую вероятность $P(X\ge a)$. Применим неравенство Маркова к положительной функции $e^{tX}$ при $t>0$:
$$P(X\ge a)=P(e^{tX}\ge e^{ta})\le e^{-ta}E[e^{tX}].$$ Оптимизируя по $t>0$, получаем общую форму неравенства Чернова:
$$P(X\ge a)\le \underset{t>0}{\inf }{e}^{-ta}{M}_X(t),M_X(t)=E[e^{tX}](\text{моментоген. функция}).$$
Для суммы независимых величин $X={\sum }_{i=1}^n{X}_i$ используем независимость:
$$M_X(t)=\prod _{i=1}^n{M}_{X_i}(t),P(\sum _{i=1}^n{X}_i\ge a)\le \underset{t>0}{\inf }{e}^{-ta}\prod _{i=1}^{n}E[e^{t{X}_i}].$$
Пример (независимые бернулли $X_i\sim \mathrm{Bern}(p_i)$, $S=\sum X_i$, $\mu =E[S]=\sum p_i$). Для одинаковых $p_i=p$ и $a=(1+\delta )\mu$ ( $\delta >0$ ) стандартный вывод даёт
$$P(S\ge (1+\delta )\mu )\le {\left(\frac{e^{\delta }}{(1+\delta {)}^{1+\delta }}\right)}^{\mu },$$ что часто оценяют дальше в удобные экспоненциальные формы, напр.
$$P(S\ge (1+\delta )\mu )\le \exp (-\frac{{\delta }^2\mu }{3})(0<\delta \le 1).$$ Альтернативная запись через дивергенцию:
$$P(S\ge k)\le \exp (-nD(k/n\Vert p)),D(q\Vert p)=q\ln \frac{q}{p}+(1-q)\ln \frac{1-q}{1-p}.$$
Когда Чернов эффективнее Маркова/Чебышёва:
- Марков даёт только $P(X\ge a)\le E[X]/a$ (падает как $1/a$); Чебышёв — только $P(|X-\mu |\ge t)\le \mathrm{Var}(X)/t^2$ (падает как $1/t^2$). Оба используют лишь первый/второй моменты и дают полиномиально убывающие оценки.
- Чернов, при наличии независимости (или слабой зависимости) и конечной MGF (часто при ограниченных или подгауссовских с.в.), даёт экспоненциальное убывание вероятности хвоста по числу слагаемых $n$. Поэтому для сумм многих малых независимых вкладов (например, сумм Бернулли) Чернов значительно сильнее.
- Требования: существование/контроль MGF или ограниченность величин; независимость или подходящие условия отрицательной/слабой зависимости. Если распределение тяжёхвостое (MGF не существует) или зависимости сильны, Чернов может быть неприменим или неточным; тогда остаются более общие (но слабее) оценки Маркова/Чебышёва.
Краткое резюме: принцип — применить Марков к $e^{tX}$ и оптимизировать по $t$. Чернов эффективен, когда суммируются многие независимые (или слабо зависимые), ограниченные или подгауссовские вклады: даёт экспоненциальные оценки хвоста, тогда как Марков/Чебышёв дают только полиномиальные оценки и используют меньше информации о распределении.