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

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

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

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

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

$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$

$P(X\geq a)\leq e^{-ta}\mathrm {E} \left[\prod _{i}e^{t\cdot X_{i}}\right].$

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

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

Аналогично

$P(X\leq a)=P\left(e^{-tX}\geq e^{-ta}\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 X_{i}}\right]$для конкретных величин $X_{i}$.

Пример

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

$\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 X}\right]\leq 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]\leq e^{\delta np}$ , $e^{-ta}={\frac {1}{(1+\delta )^{(1+\delta )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>{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>{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 y)=x\ln {\frac {x}{y}}+(1-x)\ln \left({\frac {1-x}{1-y}}\right).$

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

$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\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.

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

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

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

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

$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\geq (1+\delta )\mu )\leq e^{-{\frac {\delta ^{2}\mu }{2+\delta }}},\qquad 0\leq \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.

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

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

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

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

Пусть 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

$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$ (количество образцов) пропорциональным логарифму $d_{1}+d_{2}$. В общем случае зависимость от $\ln(\min(d_{1},d_{2}))$ неочевидна: например, возьмём диагональную случайную матрицу знаков размерности $d\times d$. Оператор нормы суммы $t$ независимых образцов является в точности максимальным отклонением среди $d$ независимых случайных блужданий длины $t$. Для того, чтобы достичь фиксированную границу максимального отклонения с постоянной вероятностью, $t$ должно логарифмически возрастать вместе с $d$.

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

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

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

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

Если $r\leq 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$.

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

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

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

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

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

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

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

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

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

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

$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$, то мы получаем тривиальную оценку $P>0$.

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

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

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

$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^{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}.$

Приравнивая полученное выражение к нулю и разрешая уравнение относительно $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}}.$

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

$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({\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^{tX_{i}}$ принимает значение e^t с вероятностью p_i и значение 1 с вероятностью 1 − p_i. Это идентично вычислениям выше в доказательстве аддитивной формы.

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

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

$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)\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. 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. 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. 33 (6): 305. doi:10.1016/0020-0190(90)90214-I.
• Nielsen, F. (2011). "Chernoff information of exponential families". arXiv:1102.2684 [cs.IT].