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

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

Оценка Чернова имеет отношение к Шаблон:Не переведено 5 и неравенству Хёфдинга, которые ей исторически предшествуют.

Основной случай

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

$P(X\ge a)=P(e^{t\cdot X}\ge e^{t\cdot a})\le \frac{\mathrm{E}\left[e^{t\cdot X}\right]}{e^{t\cdot a}}.$

Когда Шаблон:Mvar является суммой Шаблон:Mvar случайных величин Шаблон:Math, для любого $t>0$

$P(X\ge a)\le e^{-ta}\mathrm{E}\left[\prod _i{e}^{t\cdot X_i}\right].$

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

$P(X\ge a)\le \underset{t>0}{\min }{e}^{-ta}\prod _i\mathrm{E}\left[e^{t{X}_i}\right].$ (1)

Аналогично

$P(X\le a)=P(e^{-tX}\ge e^{-ta})$

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

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

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

Пример

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

$\mathrm{E}\left[e^{t\cdot X_i}\right]=(1-p)e^0+p{e}^t=1+p(e^t-1)\le e^{p(e^t-1)},$

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

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

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

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

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

$P[X\ge (1+\delta )np]\le \frac{e^{\delta np}}{(1+\delta {)}^{(1+\delta )np}}={\left[\frac{e^{\delta }}{(1+\delta {)}^{1+\delta }}\right]}^{np}.$

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

$P[X>\frac{n}{2}]=\sum _{i=\lfloor \frac{n}{2}\rfloor +1}^n(\genfrac{}{}{0ex}{}{n}{i})p^i(1-p{)}^{n-i}.$

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

$P[X>\frac{n}{2}]\ge 1-e^{-\frac{1}{2p}n{(p-\frac{1}{2})}^2}.$

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

$\begin{array}{cc}P(X\le \lfloor \frac{n}{2}\rfloor )& =P(X\le (1-(1-\frac{1}{2p}))\mu )\\ & \le e^{-\frac{\mu }{2}{(1-\frac{1}{2p})}^2}\\ & =e^{-\frac{n}{2p}{(p-\frac{1}{2})}^2.}\end{array}$

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

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

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

Теорема Чернова — Хёфдинга. Пусть Шаблон:Math — независимые одинаково распределённые случайные величины, принимающие значения Шаблон:Math

Положим Шаблон:Math и Шаблон:Math. Тогда

$\begin{array}{cc}P(\frac{1}{n}\sum X_i\ge p+\epsilon )\le {\left({\left(\frac{p}{p+\epsilon }\right)}^{p+\epsilon }{\left(\frac{1-p}{1-p-\epsilon }\right)}^{1-p-\epsilon }\right)}^n& =e^{-D(p+\epsilon \parallel p)n},\\ P(\frac{1}{n}\sum X_i\le p-\epsilon )\le {\left({\left(\frac{p}{p-\epsilon }\right)}^{p-\epsilon }{\left(\frac{1-p}{1-p+\epsilon }\right)}^{1-p+\epsilon }\right)}^n& =e^{-D(p-\epsilon \parallel p)n},\end{array}$

где

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

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

$P(\sum X_i>np+x)\le \exp (-\frac{x^2}{2np(1-p)}).$

Более простая оценка получается ослаблением этой теоремы, используя неравенство Шаблон:Math, которое следует из выпуклости Шаблон:Math и того факта, что

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

Этот результат является частным случаем неравенства Хёфдинга. В некоторых случаях используются оценки

$\begin{array}{cccc}D((1+x)p\parallel p)\ge \frac{1}{4}{x}^{2}p,& & & -\frac{1}{2}\le x\le \frac{1}{2},\\ D(x\parallel y)\ge \frac{3(x-y{)}^2}{2(2y+x)},\\ D(x\parallel y)\ge \frac{(x-y{)}^2}{2y},& & & x\le y,\\ D(x\parallel y)\ge \frac{(x-y{)}^2}{2x},& & & x\ge y\end{array}$

более сильные при Шаблон:Math.

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

Мультипликативная оценка Чернова. Пусть Шаблон:Math — независимые случайные величины, принимающие значения Шаблон:Math Их сумму обозначим Шаблон:Mvar, математическое ожидание этой суммы обозначим μ. Тогда для всякого $\delta \ge 0$

$P(X\ge (1+\delta )\mu )\le {\left(\frac{e^{\delta }}{(1+\delta {)}^{1+\delta }}\right)}^{\mu }.$

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

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

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

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

$P(X\ge (1+\delta )\mu )\le e^{-\frac{{\delta }^2\mu }{2+\delta }},0\le \delta ,$

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

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

Приложения

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

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

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

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

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

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

Шаблон:Не переведено 5 и Шаблон:Не переведено 5 использовали оценки Чернова для случайных величин с матричными значениями. Следующую версию неравенства можно найти в работе Троппа.

Пусть Шаблон:Math — случайные величины с матричными значениями такие, что $M_i\in {ℂ}^{d_1\times d_2}$ и $𝔼[M_i]=0$. Обозначим $\Vert M\Vert$ оператор нормы матрицы $M$. Если неравенство $\Vert M_i\Vert \le \gamma$ почти наверное выполнено для всех $i\in \{1,\dots ,t\}$, то для каждого Шаблон:Math

$P(\Vert \frac{1}{t}\sum _{i=1}^t{M}_i\Vert >\epsilon )\le (d_1+d_2)\exp (-\frac{3{\epsilon }^{2}t}{8{\gamma }^2}).$

Чтобы заключить, что отклонение от 0 ограничено величиной Шаблон:Math с высокой вероятностью, нам нужно выбрать $t$ (количество образцов) пропорциональным логарифму $d_1+d_2$. В общем случае зависимость от $\ln (\min (d_1,d_2))$ неочевидна: например, возьмём диагональную случайную матрицу знаков размерности $d\times d$. Оператор нормы суммы $t$ независимых образцов является в точности максимальным отклонением среди $d$ независимых случайных блужданий длины $t$. Для того, чтобы достичь фиксированную границу максимального отклонения с постоянной вероятностью, $t$ должно логарифмически возрастать вместе с $d$.

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

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

Пусть Шаблон:Math и $M$ ─ случайная симметрическая вещественная матрица с $\Vert \mathrm{E}[M]\Vert \le 1$ и $\Vert M\Vert \le \gamma$ почти наверное. Предположим, что каждый элемент носителя $M$ имеет ранг самое большее $r$. Положим

$t=\mathrm{\Omega }\left(\frac{\gamma \ln (\gamma /{\epsilon }^2)}{{\epsilon }^2}\right).$

Если $r\le t$ почти наверное, то

$P(\Vert \frac{1}{t}\sum _{i=1}^t{M}_i-\mathrm{E}[M]\Vert >\epsilon )\le \frac{1}{𝐩𝐨𝐥𝐲(t)},$

где Шаблон:Math — это независимые одинаково распределенные копии $M$.

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

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

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

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

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

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

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

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

$P(r_S<(1-d)\cdot r)<\exp (-r\cdot d^2\cdot k/2).$

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

$P(r_S>0.5)>1-\exp (-r\cdot {(1-\frac{1}{2r})}^2\cdot k/2).$

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

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

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

Пусть Шаблон:Math. Взяв Шаблон:Math в формуле (1), получаем:

$P(\frac{1}{n}\sum X_i\ge q)\le \underset{t>0}{\inf }\frac{E[\prod e^{t{X}_i}]}{e^{tnq}}=\underset{t>0}{\inf }{\left(\frac{E\left[e^{t{X}_i}\right]}{e^{tq}}\right)}^n.$

Теперь, зная что Шаблон:Math, имеем

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

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

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

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

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

так что

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

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

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

Поскольку Шаблон:Math, то мы видим, что Шаблон:Math, так что наша оценка удовлетворяется по Шаблон:Mvar. Получив Шаблон:Mvar, мы можем вернуться в предыдущие уравнения и найти

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

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

$P(\frac{1}{n}\sum X_i\ge p+\epsilon )\le e^{-D(p+\epsilon \parallel p)n}.$

Для завершения доказательства в симметрическом случае мы попросту определим случайную величину Шаблон:Math, применим к ней точно такое же доказательство и присоединим результат к нашей оценке.

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

Положим Шаблон:Math. Согласно формуле (1),

$\begin{array}{cc}P(X\ge (1+\delta )\mu )& \le \underset{t>0}{\inf }\frac{\mathrm{E}\left[\prod _{i=1}^n{e}^{t{X}_i}\right]}{e^{t(1+\delta )\mu }}\\ & =\underset{t>0}{\inf }\frac{\prod _{i=1}^n\mathrm{E}\left[e^{t{X}_i}\right]}{e^{t(1+\delta )\mu }}\\ & =\underset{t>0}{\inf }\frac{\prod _{i=1}^n[p_i{e}^t+(1-p_i)]}{e^{t(1+\delta )\mu }}.\end{array}$

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

Переписав $p_i{e}^t+(1-p_i)$ как $p_i(e^t-1)+1$ и вспомнив, что $1+x\le e^x$ (если Шаблон:Math, то неравенство строгое), мы положим $x=p_i(e^t-1)$. Тот же результат можно получить, напрямую заменяя Шаблон:Mvar в уравнении для оценки Чернова на Шаблон:Math.

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

$P(X\ge (1+\delta )\mu )\le \frac{\prod _{i=1}^n{e}^{p_i(e^t-1)}}{e^{t(1+\delta )\mu }}=\frac{e^{((e^t-1)\sum _{i=1}^n{p}_i)}}{e^{t(1+\delta )\mu }}=\frac{e^{(e^t-1)\mu }}{e^{t(1+\delta )\mu }}.$

Если мы просто положим Шаблон:Math, так что Шаблон:Math для Шаблон:Math, то сможем подставить это в последнее выражение и найти

$\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 }$,

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

См. также

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

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

• Шаблон:Cite journal
• Шаблон:Cite journal
• Шаблон:Cite journal
• Шаблон:Cite arXiv