Чернов связан

В теории вероятностей граница Чернова представляет собой экспоненциально убывающую верхнюю границу хвоста случайной величины, основанную на ее производящей функции момента . Минимум всех таких экспоненциальных границ образует границу Чернова или Чернова-Крамера , которая может затухать быстрее, чем экспоненциальная (например , субгауссова ). Это особенно полезно для сумм независимых случайных величин, таких как суммы случайных величин Бернулли .

Границу обычно называют в честь Германа Чернова, который описал этот метод в статье 1952 года. хотя сам Чернов приписывал это Герману Рубину. В 1938 году Харальд Крамер опубликовал почти идентичную концепцию, теперь известную как теорема Крамера .

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

Граница Чернова связана с неравенствами Бернштейна . Он также используется для доказательства неравенства Хеффдинга , неравенства Беннета и неравенства Мак-Диармида .

Общие границы Чернова

Двусторонняя оценка Чернова для хи-квадрат случайной величины

Общая оценка Чернова для случайной величины $X$ достигается применением неравенства Маркова к $e^{tX}$ (поэтому его иногда называют экспоненциальной марковской границей или экспоненциальной границей моментов). Для позитива $t$ это дает границу на правом хвосте $X$ с точки зрения его моментообразующей функции $M(t)=\operatorname {E} (e^{tX})$:

$\operatorname {P} \left(X\geq a\right)=\operatorname {P} \left(e^{tX}\geq e^{ta}\right)\leq M(t)e^{-ta}\qquad (t>0)$

Поскольку эта оценка справедлива для любого положительного $t$, мы можем взять нижнюю грань :

$\operatorname {P} \left(X\geq a\right)\leq \inf _{t>0}M(t)e^{-ta}$

Проведение того же анализа с отрицательным $t$ мы получаем аналогичную границу для левого хвоста :

$\operatorname {P} \left(X\leq a\right)=\operatorname {P} \left(e^{tX}\geq e^{ta}\right)\leq M(t)e^{-ta}\qquad (t<0)$

и

$\operatorname {P} \left(X\leq a\right)\leq \inf _{t<0}M(t)e^{-ta}$

Количество $M(t)e^{-ta}$ может быть выражено как математическое ожидание $\operatorname {E} (e^{tX})e^{-ta}$или эквивалентно $\operatorname {E} (e^{t(X-a)})$.

Характеристики

Показательная функция выпуклая, поэтому по неравенству Йенсена $\operatorname {E} (e^{tX})\geq e^{t\operatorname {E} (X)}$. Отсюда следует, что граница правого хвоста больше или равна единице, когда $a\leq \operatorname {E} (X)$, и, следовательно, тривиально; аналогично левая оценка тривиальна для $a\geq \operatorname {E} (X)$. Поэтому мы можем объединить две инфимы и определить двустороннюю границу Чернова: $$C(a)=\inf _{t}M(t)e^{-ta}$$который обеспечивает верхнюю границу сложенной распределения кумулятивной функции $X$ (сложено в среднем, а не в медиане).

Логарифм двусторонней границы Чернова известен как функция скорости (или преобразование Крамера ). $I=-\log C$. Это эквивалентно преобразованию Лежандра – Фенхеля или выпуклому сопряжению кумулянтной производящей функции. $K=\log M$, определяемый как: $$I(a)=\sup _{t}at-K(t)$$ является Производящая функция момента лог -выпуклой , поэтому по свойству выпуклого сопряжения граница Чернова должна быть лог-вогнутой . Граница Чернова достигает максимума в среднем: $C(\operatorname {E} (X))=1$, и инвариантен при переводе: ${\textstyle C_{X+k}(a)=C_{X}(a-k)}$.

Оценка Чернова точна тогда и только тогда, когда $X$ представляет собой единую концентрированную массу ( вырожденное распределение ). Граница точная только в крайних значениях ограниченной случайной величины или за их пределами, где нижняя граница достигается для бесконечного числа. $t$. Для неограниченных случайных величин граница нигде не является жесткой, хотя она асимптотически точна с точностью до субэкспоненциальных факторов («экспоненциально узкая»). Отдельные моменты могут обеспечить более жесткие границы за счет большей аналитической сложности.

На практике точная граница Чернова может быть громоздкой или трудной для аналитической оценки, и в этом случае вместо нее можно использовать подходящую верхнюю границу производящей функции момента (или кумулянта) (например, субпараболический CGF, дающий субгауссову границу Чернова ).

Точные функции скоростей и границы Чернова для распространенных распределений скрывать

Распределение	$\operatorname {E} (X)$	$K(t)$	$I(a)$	$C(a)$
Нормальное распределение	$0$	${\frac {1}{2}}\sigma ^{2}t^{2}$	${\frac {1}{2}}\left({\frac {a}{\sigma }}\right)^{2}$	$\exp \left({-{\frac {a^{2}}{2\sigma ^{2}}}}\right)$
Распределение Бернулли (подробно ниже)	$p$	$\ln \left(1-p+pe^{t}\right)$	$D_{KL}(a\parallel p)$	$\left({\frac {p}{a}}\right)^{a}{\left({\frac {1-p}{1-a}}\right)}^{1-a}$
Стандарт Бернулли ( H — двоичная функция энтропии )	${\frac {1}{2}}$	$\ln \left(1+e^{t}\right)-\ln(2)$	$\ln(2)-H(a)$	${\frac {1}{2}}a^{-a}(1-a)^{-(1-a)}$
Распределение Радемахера	$0$	$\ln \cosh(t)$	$\ln(2)-H\left({\frac {1+a}{2}}\right)$	${\sqrt {(1+a)^{-1-a}(1-a)^{-1+a}}}$
Гамма-распределение	$\theta k$	$-k\ln(1-\theta t)$	$-k\ln {\frac {a}{\theta k}}-k+{\frac {a}{\theta }}$	$\left({\frac {a}{\theta k}}\right)^{k}e^{k-a/\theta }$
Распределение хи-квадрат	$k$	$-{\frac {k}{2}}\ln(1-2t)$	${\frac {k}{2}}\left({\frac {a}{k}}-1-\ln {\frac {a}{k}}\right)$	$\left({\frac {a}{k}}\right)^{k/2}e^{k/2-a/2}$
Распределение Пуассона	$\lambda$	$\lambda (e^{t}-1)$	$a\ln(a/\lambda )-a+\lambda$	$(a/\lambda )^{-a}e^{a-\lambda }$

Нижние границы MGF

Используя только производящую функцию момента, нижнюю границу вероятностей хвоста можно получить, применив неравенство Пэли-Зигмунда к $e^{tX}$, что дает: $$\operatorname {P} \left(X>a\right)\geq \sup _{t>0\land M(t)\geq e^{ta}}\left(1-{\frac {e^{ta}}{M(t)}}\right)^{2}{\frac {M(t)^{2}}{M(2t)}}$$(оценка на левом хвосте получена для отрицательных $t$). Однако в отличие от границы Чернова этот результат не является экспоненциально точным.

Теодосопулос построил точную нижнюю границу на основе MGF, используя процедуру экспоненциального наклона .

Для конкретных распределений (таких как биномиальное ) часто доступны нижние границы того же экспоненциального порядка, что и граница Чернова.

Суммы независимых случайных величин

Когда X представляет собой сумму n независимых случайных величин X ₁ , ..., X _n , производящая функция момента X является произведением отдельных производящих функций момента, что дает следующее:

$\Pr(X\geq a)\leq \inf _{t>0}{\frac {\operatorname {E} \left[\prod _{i}e^{t\cdot X_{i}}\right]}{e^{t\cdot a}}}=\inf _{t>0}e^{-t\cdot a}\prod _{i}\operatorname {E} \left[e^{t\cdot X_{i}}\right].$ ( 1 )

и:

$\Pr(X\leq a)\leq \inf _{t<0}e^{-ta}\prod _{i}\operatorname {E} \left[e^{tX_{i}}\right]$

Конкретные границы Чернова достигаются путем вычисления производящей функции момента $\operatorname {E} \left[e^{-t\cdot X_{i}}\right]$ для конкретных случаев случайных величин $X_{i}$.

Когда случайные величины также одинаково распределены ( iid ), граница Чернова для суммы сводится к простому изменению масштаба границы Чернова для одной переменной. То есть граница Чернова для среднего значения n iid переменных эквивалентна n-й степени границы Чернова для одной переменной (см. теорему Крамера ).

Суммы независимых ограниченных случайных величин

Основная статья: неравенство Хёффдинга

Границы Чернова также могут применяться к общим суммам независимых ограниченных случайных величин, независимо от их распределения; это известно как неравенство Хеффдинга . Доказательство использует тот же подход, что и другие границы Чернова, но с применением леммы Хёффдинга для оценки производящих функций момента (см. неравенство Хёффдинга ).

Неравенство Хеффдинга . Предположим, что X ₁ , ..., X _n — независимые случайные величины, принимающие значения в [a,b]. Пусть X обозначает их сумму и пусть µ = E[ X ] обозначает ожидаемое значение суммы. Тогда для любого $t>0$,

$\Pr(X\leq \mu -t)<e^{-2t^{2}/(n(b-a)^{2})},$

$\Pr(X\geq \mu +t)<e^{-2t^{2}/(n(b-a)^{2})}.$

Суммы независимых случайных величин Бернулли

Оценки в следующих разделах для случайных величин Бернулли получены с использованием этих оценок для случайной величины Бернулли. $X_{i}$ с вероятностью p , равной 1,

$\operatorname {E} \left[e^{t\cdot X_{i}}\right]=(1-p)e^{0}+pe^{t}=1+p(e^{t}-1)\leq e^{p(e^{t}-1)}.$

Можно встретить множество разновидностей границ Чернова: исходную аддитивную форму (которая дает оценку абсолютной ошибки ) или более практичную мультипликативную форму (которая ограничивает ошибку относительно среднего).

Мультипликативная форма (относительная ошибка)

Мультипликативная граница Чернова. Предположим, X ₁ , ..., X _n — независимые случайные величины, принимающие значения в {0, 1}. Пусть X обозначает их сумму и пусть µ = E[ X ] обозначает ожидаемое значение суммы. Тогда для любого δ > 0

$\Pr(X\geq (1+\delta )\mu )\leq \left({\frac {e^{\delta }}{(1+\delta )^{1+\delta }}}\right)^{\mu }.$

Аналогичную стратегию доказательства можно использовать, чтобы показать, что при 0 < δ < 1

$\Pr(X\leq (1-\delta )\mu )\leq \left({\frac {e^{-\delta }}{(1-\delta )^{1-\delta }}}\right)^{\mu }.$

Приведенная выше формула на практике часто оказывается громоздкой, поэтому следующие более слабые, но более удобные оценки часто используются, которые следуют из неравенства $\textstyle {\frac {2\delta }{2+\delta }}\leq \log(1+\delta )$ из списка логарифмических неравенств :

$\Pr(X\geq (1+\delta )\mu )\leq e^{-\delta ^{2}\mu /(2+\delta )},\qquad 0\leq \delta ,$

$\Pr(X\leq (1-\delta )\mu )\leq e^{-\delta ^{2}\mu /2},\qquad 0<\delta <1,$

$\Pr(|X-\mu |\geq \delta \mu )\leq 2e^{-\delta ^{2}\mu /3},\qquad 0<\delta <1.$

Обратите внимание, что оценки тривиальны для $\delta =0$.

Кроме того, на основе разложения Тейлора для функции Ламберта W :

$\Pr(X\geq R)\leq 2^{-xR},\qquad x>0,\ R\geq (2^{x}e-1)\mu .$

Аддитивная форма (абсолютная ошибка)

Следующая теорема принадлежит Василию Хеффдингу. и поэтому называется теоремой Чернова – Хеффдинга.

Теорема Чернова–Хеффдинга. Предположим, что X ₁ , ..., X _n — случайные величины iid , принимающие значения в {0, 1}. Пусть p = E[ X ₁ ] и ε > 0 .

${\begin{aligned}\Pr \left({\frac {1}{n}}\sum X_{i}\geq p+\varepsilon \right)\leq \left(\left({\frac {p}{p+\varepsilon }}\right)^{p+\varepsilon }{\left({\frac {1-p}{1-p-\varepsilon }}\right)}^{1-p-\varepsilon }\right)^{n}&=e^{-D(p+\varepsilon \parallel p)n}\\\Pr \left({\frac {1}{n}}\sum X_{i}\leq p-\varepsilon \right)\leq \left(\left({\frac {p}{p-\varepsilon }}\right)^{p-\varepsilon }{\left({\frac {1-p}{1-p+\varepsilon }}\right)}^{1-p+\varepsilon }\right)^{n}&=e^{-D(p-\varepsilon \parallel p)n}\end{aligned}}$

где

$D(x\parallel y)=x\ln {\frac {x}{y}}+(1-x)\ln \left({\frac {1-x}{1-y}}\right)$

— это расхождение Кульбака–Лейблера между распределенными по Бернулли случайными величинами с параметрами x и y соответственно. Если р ≥ ⁠ 1/2 ​ ⁠ ​ , тогда $D(p+\varepsilon \parallel p)\geq {\tfrac {\varepsilon ^{2}}{2p(1-p)}}$ что означает

$\Pr \left({\frac {1}{n}}\sum X_{i}>p+x\right)\leq \exp \left(-{\frac {x^{2}n}{2p(1-p)}}\right).$

Более простая оценка получается путем ослабления теоремы с использованием D ( p + ε || p ) ≥ 2 ε ² следует из выпуклости D , что ( p + ε || p ) и того факта, что

${\frac {d^{2}}{d\varepsilon ^{2}}}D(p+\varepsilon \parallel p)={\frac {1}{(p+\varepsilon )(1-p-\varepsilon )}}\geq 4={\frac {d^{2}}{d\varepsilon ^{2}}}(2\varepsilon ^{2}).$

Этот результат является частным случаем неравенства Хеффдинга . Иногда границы

${\begin{aligned}D((1+x)p\parallel p)\geq {\frac {1}{4}}x^{2}p,&&&{-{\tfrac {1}{2}}}\leq x\leq {\tfrac {1}{2}},\\[6pt]D(x\parallel y)\geq {\frac {3(x-y)^{2}}{2(2y+x)}},\\[6pt]D(x\parallel y)\geq {\frac {(x-y)^{2}}{2y}},&&&x\leq y,\\[6pt]D(x\parallel y)\geq {\frac {(x-y)^{2}}{2x}},&&&x\geq y\end{aligned}}$

которые сильнее при p < ⁠ 1/8 ​ ⁠ также . используются

Приложения

Границы Чернова имеют очень полезные применения при балансировке наборов и пакетов маршрутизации в разреженных сетях.

Проблема балансировки множества возникает при планировании статистических экспериментов. Обычно при планировании статистического эксперимента, учитывая особенности каждого участника эксперимента, нам необходимо знать, как разделить участников на две непересекающиеся группы так, чтобы каждая особенность была примерно максимально сбалансирована между двумя группами.

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

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

Границы Чернова можно эффективно использовать для оценки «уровня устойчивости» приложения/алгоритма путем исследования его пространства возмущений с помощью рандомизации. Использование границы Чернова позволяет отказаться от сильной и по большей части нереалистичной гипотезы малого возмущения (величина возмущения мала). Уровень устойчивости, в свою очередь, может использоваться либо для подтверждения, либо для отклонения конкретного алгоритмического выбора, аппаратной реализации или приемлемости решения, на структурные параметры которого влияют неопределенности.

Простое и распространенное использование границ Чернова — для «усиления» рандомизированных алгоритмов . Если у кого-то есть алгоритм, который выводит предположение, которое является желаемым ответом с вероятностью p > 1/2, то можно получить более высокий уровень успеха, запустив алгоритм $n=\log(1/\delta )2p/(p-1/2)^{2}$ раз и выводит предположение, которое выводится более чем n /2 запусками алгоритма. (Таких предположений не может быть более одного.) Если предположить, что эти прогоны алгоритма независимы, вероятность того, что более n /2 предположений верны, равна вероятности того, что сумма независимых случайных величин Бернулли X _k , равная 1 с вероятностью p больше n /2. Можно показать, что это, по крайней мере, $1-\delta$ через мультипликативную границу Чернова (следствие 13.3 в классных заметках Синклера, µ = np ).:

$\Pr \left[X>{n \over 2}\right]\geq 1-e^{-n\left(p-1/2\right)^{2}/(2p)}\geq 1-\delta$

Матрица Чернова связана

Основная статья: Матрица Чернова, связанная

Рудольф Альсведе и Андреас Винтер ввели оценку Чернова для матричных случайных величин. Следующий вариант неравенства можно найти в работе Троппа.

Пусть M ₁ , ..., M _t — независимые матричные случайные величины такие, что $M_{i}\in \mathbb {C} ^{d_{1}\times d_{2}}$ и $\mathbb {E} [M_{i}]=0$. Обозначим через $\lVert M\rVert$ операторная норма матрицы $M$. Если $\lVert M_{i}\rVert \leq \gamma$ почти наверняка справедливо для всех $i\in \{1,\ldots ,t\}$, то для любого ε > 0

$\Pr \left(\left\|{\frac {1}{t}}\sum _{i=1}^{t}M_{i}\right\|>\varepsilon \right)\leq (d_{1}+d_{2})\exp \left(-{\frac {3\varepsilon ^{2}t}{8\gamma ^{2}}}\right).$

Обратите внимание, что для того, чтобы сделать вывод, что отклонение от 0 с высокой вероятностью ограничено ε , нам нужно выбрать количество выборок $t$ пропорциональна логарифму $d_{1}+d_{2}$. В целом, к сожалению, зависимость от $\log(\min(d_{1},d_{2}))$ неизбежно: возьмем, к примеру, диагональную матрицу случайных знаков размерности $d\times d$. Операторная норма суммы t независимых выборок — это в точности максимальное отклонение среди d независимых случайных блужданий длины t . Чтобы добиться фиксированной границы максимального отклонения с постоянной вероятностью, легко видеть, что t должно расти логарифмически с d . в этом сценарии

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

Теорема без зависимости от размерностей

Пусть 0 < ε < 1 и M — случайная симметричная действительная матрица с $\|\operatorname {E} [M]\|\leq 1$ и $\|M\|\leq \gamma$ почти наверняка. Предположим, что каждый элемент на носителе M имеет не более ранга r . Набор

$t=\Omega \left({\frac {\gamma \log(\gamma /\varepsilon ^{2})}{\varepsilon ^{2}}}\right).$

Если $r\leq t$ выполняется почти наверняка, тогда

$\Pr \left(\left\|{\frac {1}{t}}\sum _{i=1}^{t}M_{i}-\operatorname {E} [M]\right\|>\varepsilon \right)\leq {\frac {1}{\mathbf {poly} (t)}}$

где M ₁ , ..., M _t являются iid копиями M .

Выборочный вариант

Следующий вариант границы Чернова можно использовать для оценки вероятности того, что большинство в популяции станет меньшинством в выборке или наоборот.

что существует общая популяция A и подгруппа B ⊆ A. Предположим , Отметьте относительный размер подгруппы (| B |/| A |) с помощью r .

Предположим, мы выбираем целое число k и случайную выборку S ⊂ A размера k . Отметьте относительный размер подгруппы населения в выборке (| B ∩ S |/| S |) посредством r _S .

Тогда для каждой дроби d ∈ [0,1]:

$\Pr \left(r_{S}<(1-d)\cdot r\right)<\exp \left(-r\cdot d^{2}\cdot {\frac {k}{2}}\right)$

В частности, если B является большинством в A (т.е. r > 0,5), мы можем ограничить вероятность того, что B останется большинством в S ( r _S > 0,5), приняв: d = 1 - 1/(2 r ):

$\Pr \left(r_{S}>0.5\right)>1-\exp \left(-r\cdot \left(1-{\frac {1}{2r}}\right)^{2}\cdot {\frac {k}{2}}\right)$

Эта граница, конечно, совсем не жесткая. Например, когда r = 0,5, мы получаем тривиальную оценку Prob > 0.

Доказательства

Мультипликативная форма

Следуя условиям мультипликативной границы Чернова, пусть X ₁ , ..., X _n являются независимыми случайными величинами Бернулли , сумма которых равна X , каждая из которых имеет вероятность p _i быть равной 1. Для переменной Бернулли:

$\operatorname {E} \left[e^{t\cdot X_{i}}\right]=(1-p_{i})e^{0}+p_{i}e^{t}=1+p_{i}(e^{t}-1)\leq e^{p_{i}(e^{t}-1)}$

Итак, используя ( 1 ) с $a=(1+\delta )\mu$ для любого $\delta >0$ и где $\mu =\operatorname {E} [X]=\textstyle \sum _{i=1}^{n}p_{i}$,

${\begin{aligned}\Pr(X>(1+\delta )\mu )&\leq \inf _{t\geq 0}\exp(-t(1+\delta )\mu )\prod _{i=1}^{n}\operatorname {E} [\exp(tX_{i})]\\[4pt]&\leq \inf _{t\geq 0}\exp {\Big (}-t(1+\delta )\mu +\sum _{i=1}^{n}p_{i}(e^{t}-1){\Big )}\\[4pt]&=\inf _{t\geq 0}\exp {\Big (}-t(1+\delta )\mu +(e^{t}-1)\mu {\Big )}.\end{aligned}}$

Если мы просто установим t = log(1 + δ ) так, чтобы t > 0 для δ > 0 , мы можем заменить и найти

$\exp {\Big (}-t(1+\delta )\mu +(e^{t}-1)\mu {\Big )}={\frac {\exp((1+\delta -1)\mu )}{(1+\delta )^{(1+\delta )\mu }}}=\left[{\frac {e^{\delta }}{(1+\delta )^{(1+\delta )}}}\right]^{\mu }.$

Это доказывает желаемый результат.

Теорема Чернова – Хефдинга (аддитивная форма)

Пусть q = p + ε . Взяв a = nq в ( 1 ), получим:

$\Pr \left({\frac {1}{n}}\sum X_{i}\geq q\right)\leq \inf _{t>0}{\frac {E\left[\prod e^{tX_{i}}\right]}{e^{tnq}}}=\inf _{t>0}\left({\frac {E\left[e^{tX_{i}}\right]}{e^{tq}}}\right)^{n}.$

Теперь, зная, что Pr( X _i = 1) = p , Pr( X _i = 0) = 1 − p , мы имеем

$\left({\frac {\operatorname {E} \left[e^{tX_{i}}\right]}{e^{tq}}}\right)^{n}=\left({\frac {pe^{t}+(1-p)}{e^{tq}}}\right)^{n}=\left(pe^{(1-q)t}+(1-p)e^{-qt}\right)^{n}.$

Следовательно, мы можем легко вычислить нижнюю границу, используя исчисление:

${\frac {d}{dt}}\left(pe^{(1-q)t}+(1-p)e^{-qt}\right)=(1-q)pe^{(1-q)t}-q(1-p)e^{-qt}$

Приравнивая уравнение к нулю и решая, мы имеем

${\begin{aligned}(1-q)pe^{(1-q)t}&=q(1-p)e^{-qt}\\(1-q)pe^{t}&=q(1-p)\end{aligned}}$

так что

$e^{t}={\frac {(1-p)q}{(1-q)p}}.$

Таким образом,

$t=\log \left({\frac {(1-p)q}{(1-q)p}}\right).$

Поскольку q = p + ε > p , мы видим, что t > 0 выполняется , поэтому наша оценка для t . Решив значение t , мы можем снова подключиться к приведенным выше уравнениям и найти, что

${\begin{aligned}\log \left(pe^{(1-q)t}+(1-p)e^{-qt}\right)&=\log \left(e^{-qt}(1-p+pe^{t})\right)\\&=\log \left(e^{-q\log \left({\frac {(1-p)q}{(1-q)p}}\right)}\right)+\log \left(1-p+pe^{\log \left({\frac {1-p}{1-q}}\right)}e^{\log {\frac {q}{p}}}\right)\\&=-q\log {\frac {1-p}{1-q}}-q\log {\frac {q}{p}}+\log \left(1-p+p\left({\frac {1-p}{1-q}}\right){\frac {q}{p}}\right)\\&=-q\log {\frac {1-p}{1-q}}-q\log {\frac {q}{p}}+\log \left({\frac {(1-p)(1-q)}{1-q}}+{\frac {(1-p)q}{1-q}}\right)\\&=-q\log {\frac {q}{p}}+\left(-q\log {\frac {1-p}{1-q}}+\log {\frac {1-p}{1-q}}\right)\\&=-q\log {\frac {q}{p}}+(1-q)\log {\frac {1-p}{1-q}}\\&=-D(q\parallel p).\end{aligned}}$

Теперь у нас есть желаемый результат:

$\Pr \left({\tfrac {1}{n}}\sum X_{i}\geq p+\varepsilon \right)\leq e^{-D(p+\varepsilon \parallel p)n}.$

Чтобы завершить доказательство для симметричного случая, мы просто определяем случайную величину Y _i = 1 − X _i , применяем то же доказательство и подключаем его к нашей оценке.

См. также

• Неравенства Бернштейна
• Неравенство концентрации — сводка хвостовых границ случайных величин.
• Теорема Крамера
• Энтропийное значение под угрозой
• Неравенство Хефдинга
• Матрица Чернова связана
• Функция генерации момента

Дальнейшее чтение

• Чернов, Х. (1952). «Мера асимптотической эффективности проверки гипотезы, основанной на сумме наблюдений» . Анналы математической статистики . 23 (4): 493–507. дои : 10.1214/aoms/1177729330 . JSTOR   2236576 . МР   0057518 . Збл   0048.11804 .
• Чернофф, Х. (1981). «Заметки о неравенстве, связанном с нормальным распределением» . Анналы вероятности . 9 (3): 533–535. дои : 10.1214/aop/1176994428 . JSTOR   2243541 . МР   0614640 . Збл   0457.60014 .
• Хагеруп, Т.; Руб, К. (1990). «Экскурсия по пределам Чернова». Письма об обработке информации . 33 (6): 305. дои : 10.1016/0020-0190(90)90214-I .
• Нильсен, Ф. (2011). «Информационно-геометрическая характеристика информации Чернова». Письма об обработке сигналов IEEE . 20 (3): 269–272. arXiv : 1102.2684 . дои : 10.1109/ЛСП.2013.2243726 . S2CID   15034953 .