Оценка Чернова

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

Оценка Чернова имеет отношение к неравенствам Бернштейна^[en] и неравенству Хёфдинга, которые ей исторически предшествуют.

Основной случайПравить

Основной случай оценки Чернова для случайной величины $X$$X$  достигается применением неравенства Маркова к e^tX . Для каждого $t>0$$t>0$ 

$P(X\ge <!--\; \ge \; -->a)=P(e^{t\cdot <!--\; \cdot \; -->X}\ge <!--\; \ge \; -->e^{t\cdot <!--\; \cdot \; -->a})\le <!--\; \le \; -->\frac{\mathrm{E}\left[e^{t\cdot <!--\; \cdot \; -->X}\right]}{e^{t\cdot <!--\; \cdot \; -->a}}.$$P(X\geq a)=P(e^{t\cdot X}\geq e^{t\cdot a})\leq {\frac {\mathrm {E} \left[e^{t\cdot X}\right]}{e^{t\cdot a}}}.$ 

Когда X является суммой n случайных величин X₁, ... ,X_n, для любого $t>0$$t>0$ 

$P(X\ge <!--\; \ge \; -->a)\le <!--\; \le \; -->e^{-<!--\; -\; -->ta}\mathrm{E}\left[\underset{i}{\prod <!--\; \prod \; -->}{e}^{t\cdot <!--\; \cdot \; -->X_i}\right].$$P(X\geq a)\leq e^{-ta}\mathrm {E} \left[\prod _{i}e^{t\cdot X_{i}}\right].$ 

В частности, оптимизируя по t и предполагая, что X_i независимы, мы получаем

$P(X\ge <!--\; \ge \; -->a)\le <!--\; \le \; -->\underset{t>0}{min}{e}^{-<!--\; -\; -->ta}\underset{i}{\prod <!--\; \prod \; -->}\mathrm{E}\left[e^{t{X}_i}\right].$$P(X\geq a)\leq \min _{t>0}e^{-ta}\prod _{i}\mathrm {E} \left[e^{tX_{i}}\right].$  (1)

Аналогично

$P(X\le <!--\; \le \; -->a)=P\left(e^{-<!--\; -\; -->tX}\ge <!--\; \ge \; -->e^{-<!--\; -\; -->ta}\right)$$P(X\leq a)=P\left(e^{-tX}\geq e^{-ta}\right)$ 

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

$P(X\le <!--\; \le \; -->a)\le <!--\; \le \; -->\underset{t>0}{min}{e}^{ta}\underset{i}{\prod <!--\; \prod \; -->}\mathrm{E}\left[e^{-<!--\; -\; -->t{X}_i}\right].$$P(X\leq a)\leq \min _{t>0}e^{ta}\prod _{i}\mathrm {E} \left[e^{-tX_{i}}\right].$ 

Конкретные значения оценок Чернова получаются вычислением $\mathrm{E}\left[e^{-<!--\; -\; -->t\cdot <!--\; \cdot \; -->X_i}\right]$$\mathrm {E} \left[e^{-t\cdot X_{i}}\right]$ для конкретных величин $X_i$$X_{i}$ .

ПримерПравить

Пусть X₁, ..., X_n — независимые случайные величины Бернулли, сумма которых X, и каждая равна 1 с вероятностью $p>0.5$$p>0.5$ . Для переменной Бернулли верно:

$\mathrm{E}\left[e^{t\cdot <!--\; \cdot \; -->X_i}\right]=(1-<!--\; -\; -->p)e^0+p{e}^t=1+p(e^t-<!--\; -\; -->1)\le <!--\; \le \; -->e^{p(e^t-<!--\; -\; -->1)},$$\mathrm {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)},$ 

следовательно,

$\mathrm{E}\left[e^{t\cdot <!--\; \cdot \; -->X}\right]\le <!--\; \le \; -->e^{n\cdot <!--\; \cdot \; -->p(e^t-<!--\; -\; -->1)}.$$\mathrm {E} \left[e^{t\cdot X}\right]\leq e^{n\cdot p(e^{t}-1)}.$ 

Для всякого $\mathrm{\delta <!--\; \delta \; -->}>0$$\delta >0$  при $t=\ln <!--\; \; -->(1+\mathrm{\delta <!--\; \delta \; -->})>0$$t=\ln(1+\delta )>0$  и $a=(1+\mathrm{\delta <!--\; \delta \; -->})np$$a=(1+\delta )np$  получаем

$\mathrm{E}\left[e^{t\cdot <!--\; \cdot \; -->X}\right]\le <!--\; \le \; -->e^{\mathrm{\delta <!--\; \delta \; -->}np}$$\mathrm {E} \left[e^{t\cdot X}\right]\leq e^{\delta np}$  , $e^{-<!--\; -\; -->ta}=\frac{1}{(1+\mathrm{\delta <!--\; \delta \; -->}{)}^{(1+\mathrm{\delta <!--\; \delta \; -->})np}},$$e^{-ta}={\frac {1}{(1+\delta )^{(1+\delta )np}}},$ 

и общий случай оценки Чернова даёт

$P[X\ge <!--\; \ge \; -->(1+\mathrm{\delta <!--\; \delta \; -->})np]\le <!--\; \le \; -->\frac{e^{\mathrm{\delta <!--\; \delta \; -->}np}}{(1+\mathrm{\delta <!--\; \delta \; -->}{)}^{(1+\mathrm{\delta <!--\; \delta \; -->})np}}={\left[\frac{e^{\mathrm{\delta <!--\; \delta \; -->}}}{(1+\mathrm{\delta <!--\; \delta \; -->}{)}^{1+\mathrm{\delta <!--\; \delta \; -->}}}\right]}^{np}.$$P[X\geq (1+\delta )np]\leq {\frac {e^{\delta np}}{(1+\delta )^{(1+\delta )np}}}=\left[{\frac {e^{\delta }}{(1+\delta )^{1+\delta }}}\right]^{np}.$ 

Вероятность одновременного свершения более чем n/2 событий {X_k = 1} в точности равна:

$P\left[X>\frac{n}{2}\right]=\underset{i=\lfloor <!--\; \lfloor \; -->\frac{n}{2}\rfloor <!--\; \rfloor \; -->+1}{\overset{n}{\sum <!--\; \sum \; -->}}(\genfrac{}{}{0ex}{}{n}{i})p^i(1-<!--\; -\; -->p{)}^{n-<!--\; -\; -->i}.$$P\left[X>{n \over 2}\right]=\sum _{i=\lfloor {\tfrac {n}{2}}\rfloor +1}^{n}{\binom {n}{i}}p^{i}(1-p)^{n-i}.$ 

Нижнюю оценку этой вероятности можно вычислить с помощью неравенства Чернова:

$P\left[X>\frac{n}{2}\right]\ge <!--\; \ge \; -->1-<!--\; -\; -->e^{-<!--\; -\; -->\frac{1}{2p}n{\left(p-<!--\; -\; -->\frac{1}{2}\right)}^2}.$$P\left[X>{n \over 2}\right]\geq 1-e^{-{\frac {1}{2p}}n\left(p-{\frac {1}{2}}\right)^{2}}.$ 

В самом деле, обозначая μ = np, мы получаем мультипликативную форму оценки Чернова (см. ниже или Corollary 13.3 in Sinclair's class notes):

${\begin{aligned}P\left(X\leq \left\lfloor {\tfrac {n}{2}}\right\rfloor \right)&=P\left(X\leq \left(1-\left(1-{\tfrac {1}{2p}}\right)\right)\mu \right)\\&\leq e^{-{\frac {\mu }{2}}\left(1-{\frac {1}{2p}}\right)^{2}}\\&=e^{-{\frac {n}{2p}}\left(p-{\frac {1}{2}}\right)^{2}.}\end{aligned}}$ 

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

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

Следующая Теорема была доказана Василием Хёфдингом.

Теорема Чернова — Хёфдинга. Пусть X₁, ..., X_n — независимые одинаково распределённые случайные величины, принимающие значения {0, 1}.

Положим p = E[X] и ε > 0. Тогда

${\begin{aligned}P\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},\\P\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 <!--\; \parallel \; -->y)=x\ln <!--\; \; -->\frac{x}{y}+(1-<!--\; -\; -->x)\ln <!--\; \; -->\left(\frac{1-<!--\; -\; -->x}{1-<!--\; -\; -->y}\right).$$D(x\parallel y)=x\ln {\frac {x}{y}}+(1-x)\ln \left({\frac {1-x}{1-y}}\right).$ 

Это расхождение Кульбака — Лейблера между случайными величинами, имеющими бернуллиево распределение с параметрами x и y соответственно. Если p ≥ 12, то

$P\left(\sum <!--\; \sum \; -->X_i>np+x\right)\le <!--\; \le \; -->\exp <!--\; \; -->\left(-<!--\; -\; -->\frac{x^2}{2np(1-<!--\; -\; -->p)}\right).$$P\left(\sum X_{i}>np+x\right)\leq \exp \left(-{\frac {x^{2}}{2np(1-p)}}\right).$ 

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

$\frac{d^2}{d{\mathrm{\epsilon <!--\; \epsilon \; -->}}^2}D(p+\mathrm{\epsilon <!--\; \epsilon \; -->}\parallel <!--\; \parallel \; -->p)=\frac{1}{(p+\mathrm{\epsilon <!--\; \epsilon \; -->})(1-<!--\; -\; -->p-<!--\; -\; -->\mathrm{\epsilon <!--\; \epsilon \; -->})}\ge <!--\; \ge \; -->4=\frac{d^2}{d{\mathrm{\epsilon <!--\; \epsilon \; -->}}^2}(2{\mathrm{\epsilon <!--\; \epsilon \; -->}}^2).$${\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 < 18.

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

Мультипликативная оценка Чернова. Пусть X₁, ..., X_n — независимые случайные величины, принимающие значения {0, 1}. Их сумму обозначим X, математическое ожидание этой суммы обозначим μ. Тогда для всякого $\mathrm{\delta <!--\; \delta \; -->}\ge <!--\; \ge \; -->0$$\delta \geq 0$ 

$P(X\ge <!--\; \ge \; -->(1+\mathrm{\delta <!--\; \delta \; -->})\mathrm{\mu <!--\; \mu \; -->})\le <!--\; \le \; -->{\left(\frac{e^{\mathrm{\delta <!--\; \delta \; -->}}}{(1+\mathrm{\delta <!--\; \delta \; -->}{)}^{1+\mathrm{\delta <!--\; \delta \; -->}}}\right)}^{\mathrm{\mu <!--\; \mu \; -->}}.$$P(X\geq (1+\delta )\mu )\leq \left({\frac {e^{\delta }}{(1+\delta )^{1+\delta }}}\right)^{\mu }.$ 

Аналогичным образом можно показать, что для любого $0<\delta <1,$ 

$P(X\le <!--\; \le \; -->(1-<!--\; -\; -->\mathrm{\delta <!--\; \delta \; -->})\mathrm{\mu <!--\; \mu \; -->})\le <!--\; \le \; -->{\left(\frac{e^{-<!--\; -\; -->\mathrm{\delta <!--\; \delta \; -->}}}{(1-<!--\; -\; -->\mathrm{\delta <!--\; \delta \; -->}{)}^{1-<!--\; -\; -->\mathrm{\delta <!--\; \delta \; -->}}}\right)}^{\mathrm{\mu <!--\; \mu \; -->}}.$$P(X\leq (1-\delta )\mu )\leq \left({\frac {e^{-\delta }}{(1-\delta )^{1-\delta }}}\right)^{\mu }.$ 

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

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

$P(X\ge <!--\; \ge \; -->(1+\mathrm{\delta <!--\; \delta \; -->})\mathrm{\mu <!--\; \mu \; -->})\le <!--\; \le \; -->e^{-<!--\; -\; -->\frac{{\mathrm{\delta <!--\; \delta \; -->}}^2\mathrm{\mu <!--\; \mu \; -->}}{2+\mathrm{\delta <!--\; \delta \; -->}}},0\le <!--\; \le \; -->\mathrm{\delta <!--\; \delta \; -->},$$P(X\geq (1+\delta )\mu )\leq e^{-{\frac {\delta ^{2}\mu }{2+\delta }}},\qquad 0\leq \delta ,$ 

которые получаются с помощью неравенства $\frac{2\mathrm{\delta <!--\; \delta \; -->}}{2+\mathrm{\delta <!--\; \delta \; -->}}\le <!--\; \le \; -->\ln <!--\; \; -->(1+\mathrm{\delta <!--\; \delta \; -->})$${\frac {2\delta }{2+\delta }}\leq \ln(1+\delta )$  из списка логарифмических неравенств. Или ещё более слабое неравенство

$P(X\geq (1+\delta )\mu )\leq e^{-{\frac {\delta ^{2}\mu }{3}}},\qquad 0<\delta \leq 1.$ 

ПриложенияПравить

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

Проблема уравновешения множества возникает при проектировании статистического эксперимента. Как правило, при проектировании статистического эксперимента с заданными в этом эксперименте свойствами участников нам необходимо разделить участников на две непересекающиеся группы так, чтобы каждое свойство было, насколько это возможно, сбалансировано между двумя группами. См. также информацию в Probability and Computing: Randomized Algorithms and Probabilistic Analysis Архивная копия от 16 апреля 2021 на Wayback Machine.

Оценки Чернова также используются для достижения жестких границ в задачах маршрутизации с использованием перестановок. Это уменьшает перегруженность при маршрутизации в разреженных сетях. См. подробнее в Probability and Computing: Randomized Algorithms and Probabilistic Analysis Архивная копия от 16 апреля 2021 на Wayback Machine.

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

Оценки Чернова могут быть эффективно использованы для оценки "уровня робастности" приложения/алгоритма посредством исследования его пространства возмущений при помощи рандомизации.

Матричная оценкаПравить

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

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

$P\left(\Vert \frac{1}{t}\underset{i=1}{\overset{t}{\sum <!--\; \sum \; -->}}{M}_i\Vert >\mathrm{\epsilon <!--\; \epsilon \; -->}\right)\le <!--\; \le \; -->(d_1+d_2)\exp <!--\; \; -->\left(-<!--\; -\; -->\frac{3{\mathrm{\epsilon <!--\; \epsilon \; -->}}^{2}t}{8{\mathrm{\gamma <!--\; \gamma \; -->}}^2}\right).$$P\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$$t$  (количество образцов) пропорциональным логарифму $d_1+d_2$$d_{1}+d_{2}$ . В общем случае зависимость от $\ln <!--\; \; -->(min(d_1,d_2))$$\ln(\min(d_{1},d_{2}))$  неочевидна: например, возьмём диагональную случайную матрицу знаков размерности $d\times <!--\; \times \; -->d$$d\times d$ . Оператор нормы суммы $t$$t$  независимых образцов является в точности максимальным отклонением среди $d$$d$  независимых случайных блужданий длины $t$$t$ . Для того, чтобы достичь фиксированную границу максимального отклонения с постоянной вероятностью, $t$$t$  должно логарифмически возрастать вместе с $d$$d$ .

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

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

Пусть 0 < ε < 1 и $M$$M$  ─ случайная симметрическая вещественная матрица с $\Vert <!--\; \Vert \; -->\mathrm{E}[M]\Vert <!--\; \Vert \; -->\le <!--\; \le \; -->1$$\|\mathrm {E} [M]\|\leq 1$  и $\Vert <!--\; \Vert \; -->M\Vert <!--\; \Vert \; -->\le <!--\; \le \; -->\mathrm{\gamma <!--\; \gamma \; -->}$$\|M\|\leq \gamma$  почти наверное. Предположим, что каждый элемент носителя $M$$M$  имеет ранг самое большее $r$$r$ . Положим

$t=\mathrm{\Omega <!--\; \Omega \; -->}\left(\frac{\mathrm{\gamma <!--\; \gamma \; -->}\ln <!--\; \; -->(\mathrm{\gamma <!--\; \gamma \; -->}/{\mathrm{\epsilon <!--\; \epsilon \; -->}}^2)}{{\mathrm{\epsilon <!--\; \epsilon \; -->}}^2}\right).$$t=\Omega \left({\frac {\gamma \ln(\gamma /\varepsilon ^{2})}{\varepsilon ^{2}}}\right).$ 

Если $r\le <!--\; \le \; -->t$$r\leq t$  почти наверное, то

$P\left(\Vert \frac{1}{t}\underset{i=1}{\overset{t}{\sum <!--\; \sum \; -->}}{M}_i-<!--\; -\; -->\mathrm{E}[M]\Vert >\mathrm{\epsilon <!--\; \epsilon \; -->}\right)\le <!--\; \le \; -->\frac{1}{\mathbf{p}\mathbf{o}\mathbf{l}\mathbf{y}(t)},$$P\left(\left\|{\frac {1}{t}}\sum _{i=1}^{t}M_{i}-\mathrm {E} [M]\right\|>\varepsilon \right)\leq {\frac {1}{\mathbf {poly} (t)}},$ 

где M₁, ..., M_t — это независимые одинаково распределенные копии $M$$M$ .

Теорема для не полностью случайных матрицПравить

Анкит Гарг, Инь Тат Ли, Чжао Сонг и Нихил Шривастава^[en] получили оценки типа Чернова для сумм матричнозначных случайных величин, семплированных с помощью случайного блуждания экспандера.

Расмус Кинг и Чжао Сонг получили оценки типа Чернова для сумм матриц лапласианов случайных деревьев.

Вариант семплингаПравить

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

Предположим, имеется общая популяция $A$$A$  и подпопуляция $B\subseteq <!--\; \subseteq \; -->A$$B\subseteq A$ . Обозначим относительный размер подпопуляции ($|B|/|A|$$|B|/|A|$ ) через $r$$r$ .

Допустим, мы выбираем целое кисло $k$$k$  и случайную выборку $S\subset <!--\; \subset \; -->A$$S\subset A$  размера $k$$k$ . Обозначим относительный размер подпопуляции ($|B\cap <!--\; \cap \; -->S|/|S|$$|B\cap S|/|S|$ ) через $r_S$$r_{S}$ .

Тогда для каждой доли $d\in <!--\; \in \; -->[0,1]$$d\in [0,1]$ :

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

В частности, если $B$$B$  ─ это большинство в $A$$A$  (то есть, $r>0.5$$r>0.5$ ), то мы можем оценить сверху вероятность того, что $B$$B$  останется большинством в $S(r_S>0.5),$$S(r_{S}>0.5),$  взяв $d=1-<!--\; -\; -->\frac{1}{2r}$$d=1-{\frac {1}{2r}}$ :

$P\left(r_S>0.5\right)>1-<!--\; -\; -->\exp <!--\; \; -->\left(-<!--\; -\; -->r\cdot <!--\; \cdot \; -->{\left(1-<!--\; -\; -->\frac{1}{2r}\right)}^2\cdot <!--\; \cdot \; -->k/2\right).$$P\left(r_{S}>0.5\right)>1-\exp \left(-r\cdot \left(1-{\frac {1}{2r}}\right)^{2}\cdot k/2\right).$ 

Эта оценка, разумеется, не является точной. Например, если $r=0.5$$r=0.5$ , то мы получаем тривиальную оценку $P>0$$P>0$ .

ДоказательстваПравить

Теорема Чернова-Хёфдинга (аддитивная форма)Править

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

$P\left(\frac{1}{n}\sum <!--\; \sum \; -->X_i\ge <!--\; \ge \; -->q\right)\le <!--\; \le \; -->\underset{t>0}{inf}\frac{E\left[\prod <!--\; \prod \; -->e^{t{X}_i}\right]}{e^{tnq}}=\underset{t>0}{inf}{\left(\frac{E\left[e^{t{X}_i}\right]}{e^{tq}}\right)}^n.$$P\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{\mathrm{E}\left[e^{t{X}_i}\right]}{e^{tq}}\right)}^n={\left(\frac{p{e}^t+(1-<!--\; -\; -->p)}{e^{tq}}\right)}^n={\left(p{e}^{(1-<!--\; -\; -->q)t}+(1-<!--\; -\; -->p)e^{-<!--\; -\; -->qt}\right)}^n.$$\left({\frac {\mathrm {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(p{e}^{(1-<!--\; -\; -->q)t}+(1-<!--\; -\; -->p)e^{-<!--\; -\; -->qt}\right)=(1-<!--\; -\; -->q)p{e}^{(1-<!--\; -\; -->q)t}-<!--\; -\; -->q(1-<!--\; -\; -->p)e^{-<!--\; -\; -->qt}.$${\frac {d}{dt}}\left(pe^{(1-q)t}+(1-p)e^{-qt}\right)=(1-q)pe^{(1-q)t}-q(1-p)e^{-qt}.$ 

Приравнивая полученное выражение к нулю и разрешая уравнение относительно $t$$t$ , получаем

${\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}.$$e^{t}={\frac {(1-p)q}{(1-q)p}}.$ 

Следовательно,

$t=\ln <!--\; \; -->\left(\frac{(1-<!--\; -\; -->p)q}{(1-<!--\; -\; -->q)p}\right).$$t=\ln \left({\frac {(1-p)q}{(1-q)p}}\right).$ 

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

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

Теперь мы имеем желаемый результат, поскольку

$P\left(\frac{1}{n}\sum <!--\; \sum \; -->X_i\ge <!--\; \ge \; -->p+\mathrm{\epsilon <!--\; \epsilon \; -->}\right)\le <!--\; \le \; -->e^{-<!--\; -\; -->D(p+\mathrm{\epsilon <!--\; \epsilon \; -->}\parallel <!--\; \parallel \; -->p)n}.$$P\left({\tfrac {1}{n}}\sum X_{i}\geq p+\varepsilon \right)\leq e^{-D(p+\varepsilon \parallel p)n}.$ 

Для завершения доказательства в симметрическом случае мы попросту определим случайную величину Y_i = 1 − X_i, применим к ней точно такое же доказательство и присоединим результат к нашей оценке.

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

Положим Pr(X_i = 1) = p_i. Согласно формуле (1),

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

Третья строчка следует из того, что $e^{t{X}_i}$$e^{tX_{i}}$  принимает значение e^t с вероятностью p_i и значение 1 с вероятностью 1 − p_i. Это идентично вычислениям выше в доказательстве аддитивной формы.

Переписав $p_i{e}^t+(1-<!--\; -\; -->p_i)$$p_{i}e^{t}+(1-p_{i})$  как $p_i(e^t-<!--\; -\; -->1)+1$$p_{i}(e^{t}-1)+1$  и вспомнив, что $1+x\le <!--\; \le \; -->e^x$$1+x\leq e^{x}$  (если x > 0, то неравенство строгое), мы положим $x=p_i(e^t-<!--\; -\; -->1)$$x=p_{i}(e^{t}-1)$ . Тот же результат можно получить, напрямую заменяя a в уравнении для оценки Чернова на (1 + δ)μ.

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

$P(X\ge <!--\; \ge \; -->(1+\mathrm{\delta <!--\; \delta \; -->})\mathrm{\mu <!--\; \mu \; -->})\le <!--\; \le \; -->\frac{\underset{i=1}{\overset{n}{\prod <!--\; \prod \; -->}}{e}^{p_i(e^t-<!--\; -\; -->1)}}{e^{t(1+\mathrm{\delta <!--\; \delta \; -->})\mathrm{\mu <!--\; \mu \; -->}}}=\frac{e^{\left((e^t-<!--\; -\; -->1)\underset{i=1}{\overset{n}{\sum <!--\; \sum \; -->}}{p}_i\right)}}{e^{t(1+\mathrm{\delta <!--\; \delta \; -->})\mathrm{\mu <!--\; \mu \; -->}}}=\frac{e^{(e^t-<!--\; -\; -->1)\mathrm{\mu <!--\; \mu \; -->}}}{e^{t(1+\mathrm{\delta <!--\; \delta \; -->})\mathrm{\mu <!--\; \mu \; -->}}}.$$P(X\geq (1+\delta )\mu )\leq {\frac {\prod _{i=1}^{n}e^{p_{i}(e^{t}-1)}}{e^{t(1+\delta )\mu }}}={\frac {e^{\left((e^{t}-1)\sum _{i=1}^{n}p_{i}\right)}}{e^{t(1+\delta )\mu }}}={\frac {e^{(e^{t}-1)\mu }}{e^{t(1+\delta )\mu }}}.$ 

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

$\frac{e^{(e^t-<!--\; -\; -->1)\mathrm{\mu <!--\; \mu \; -->}}}{e^{t(1+\mathrm{\delta <!--\; \delta \; -->})\mathrm{\mu <!--\; \mu \; -->}}}=\frac{e^{(1+\mathrm{\delta <!--\; \delta \; -->}-<!--\; -\; -->1)\mathrm{\mu <!--\; \mu \; -->}}}{(1+\mathrm{\delta <!--\; \delta \; -->}{)}^{(1+\mathrm{\delta <!--\; \delta \; -->})\mathrm{\mu <!--\; \mu \; -->}}}={\left[\frac{e^{\mathrm{\delta <!--\; \delta \; -->}}}{(1+\mathrm{\delta <!--\; \delta \; -->}{)}^{(1+\mathrm{\delta <!--\; \delta \; -->})}}\right]}^{\mathrm{\mu <!--\; \mu \; -->}}$${\frac {e^{(e^{t}-1)\mu }}{e^{t(1+\delta )\mu }}}={\frac {e^{(1+\delta -1)\mu }}{(1+\delta )^{(1+\delta )\mu }}}=\left[{\frac {e^{\delta }}{(1+\delta )^{(1+\delta )}}}\right]^{\mu }$ ,

что и требовалось доказать.

См. такжеПравить

• Неравенство концентрации меры

Дальнейшее чтениеПравить

• Chernoff, H. (1952). “A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations”. Annals of Mathematical Statistics^[en]. 23 (4): 493—507. DOI:10.1214/aoms/1177729330. JSTOR 2236576. MR 0057518. Zbl 0048.11804.
• Chernoff, H. (1981). “A Note on an Inequality Involving the Normal Distribution”. Annals of Probability^[en]. 9 (3): 533—535. DOI:10.1214/aop/1176994428. JSTOR 2243541. MR 0614640. Zbl 0457.60014.
• Hagerup, T.; Rüb, C. (1990). “A guided tour of Chernoff bounds”. Information Processing Letters^[en]. 33 (6): 305. DOI:10.1016/0020-0190(90)90214-I.
• Nielsen, F. (2011), Chernoff information of exponential families, arΧiv:1102.2684 [cs.IT].