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

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

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

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

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

${\displaystyle 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, для любого ${\displaystyle t>0}$

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

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

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

Аналогично

${\displaystyle P(X\leq a)=P\left(e^{-tX}\geq e^{-ta}\right)}$

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

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

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

Пример

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

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

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

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

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

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

и общий случай оценки Чернова даёт^[2]:64

${\displaystyle 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} в точности равна:

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

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

${\displaystyle 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)^[3]:

${\displaystyle {\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}}}$

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

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

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

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

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

${\displaystyle {\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}}}$

где

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

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

${\displaystyle 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) и того факта, что

${\displaystyle {\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}).}$

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

${\displaystyle {\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, математическое ожидание этой суммы обозначим μ. Тогда для всякого ${\displaystyle \delta \geq 0}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Если ${\displaystyle r\leq t}$ почти наверное, то

${\displaystyle 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 — это независимые одинаково распределенные копии ${\displaystyle M}$.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle 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, имеем

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

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

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

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

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

так что

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

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

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

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

${\displaystyle {\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}}}$

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

${\displaystyle 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),

${\displaystyle {\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}}}$

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

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

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

${\displaystyle 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, то сможем подставить это в последнее выражение и найти

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

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

См. также

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