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

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

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

Основной случай оценки Чернова для случайной величины ${\displaystyle X}$ достигается применением неравенства Маркова к e ^tX . Для каждого ${\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}}},}$

и общий случай оценки Чернова даёт ^: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) :

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

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

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

Следующая Теорема была доказана .

Теорема Чернова — Хёфдинга . Пусть 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 }.}$

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

${\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 )}$ из списка логарифмических неравенств . Или ещё более слабое неравенство

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

Приложения

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

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

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

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

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

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

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

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

Следующая теорема получена в предположении, что ${\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}$ .

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

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

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

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

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

Предположим, имеется общая популяция ${\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}}}$ :

${\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 + δ ) μ .

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

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

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

См. также

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

Ссылки

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

• Chernoff, H. (1952). . . 23 (4): 493—507. doi : . JSTOR . MR . Zbl .
• Chernoff, H. (1981). . . 9 (3): 533—535. doi : . JSTOR . MR . Zbl .
• Hagerup, T.; Rüb, C. (1990). "A guided tour of Chernoff bounds". . 33 (6): 305. doi : .
• Nielsen, F. (2011). "Chernoff information of exponential families". arXiv : [ ].