Чернов связан

Экспоненциально убывающие границы хвостовых распределений случайных величин

В теории вероятностей граница Чернова представляет собой экспоненциально убывающую верхнюю границу хвоста случайной величины, основанную на ее производящей функции момента . Минимум всех таких экспоненциальных границ образует границу Чернова или Чернова-Крамера , которая может затухать быстрее, чем экспоненциальная (например, субгауссова ). ^{[1] [2]} Это особенно полезно для сумм независимых случайных величин, таких как суммы случайных величин Бернулли . ^{[3] [4]}

Границу обычно называют в честь Германа Чернова , который описал этот метод в статье 1952 года ^[5] , хотя сам Чернов приписал его Герману Рубину. ^[6] В 1938 году Харальд Крамер опубликовал почти идентичную концепцию, теперь известную как теорема Крамера .

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

Граница Чернова связана с неравенствами Бернштейна . Он также используется для доказательства неравенства Хеффдинга , неравенства Беннета и неравенства Мак-Диармида .

Общие границы Чернова

Двусторонняя оценка Чернова для случайной величины хи-квадрат

Общая оценка Чернова для случайной величины достигается путем применения неравенства Маркова к (поэтому его иногда называют экспоненциальной марковской границей или экспоненциальной границей моментов). Для положительного результата это дает оценку правого хвоста функции , генерирующей момент : ${\displaystyle X}$ ${\displaystyle e^{tX}}$ ${\displaystyle t}$ ${\displaystyle X}$ ${\displaystyle M(t)=\operatorname {E} (e^{tX})}$

${\displaystyle \operatorname {P} \left(X\geq a\right)=\operatorname {P} \left(e^{tX}\geq e^{ta}\right)\leq M(t)e^{-ta}\qquad (t>0)}$

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

${\displaystyle \operatorname {P} \left(X\geq a\right)\leq \inf _{t>0}M(t)e^{-ta}}$

Выполняя тот же анализ с отрицанием, мы получаем аналогичную границу для левого хвоста : ${\displaystyle t}$

${\displaystyle \operatorname {P} \left(X\leq a\right)=\operatorname {P} \left(e^{tX}\geq e^{ta}\right)\leq M(t)e^{-ta}\qquad (t<0)}$

и

${\displaystyle \operatorname {P} \left(X\leq a\right)\leq \inf _{t<0}M(t)e^{-ta}}$

Количество может быть выражено как ожидаемое значение или что-то подобное . ${\displaystyle M(t)e^{-ta}}$ ${\displaystyle \operatorname {E} (e^{tX})e^{-ta}}$ ${\displaystyle \operatorname {E} (e^{t(X-a)})}$

Характеристики

Показательная функция выпуклая, поэтому по неравенству Йенсена . Отсюда следует, что оценка правого хвоста больше или равна единице при и, следовательно, тривиальна; аналогично левая оценка тривиальна для . Поэтому мы можем объединить две нижние точки и определить двустороннюю границу Чернова: которая обеспечивает верхнюю границу сложенной кумулятивной функции распределения ( свернутой в среднем, а не в медиане). ${\displaystyle \operatorname {E} (e^{tX})\geq e^{t\operatorname {E} (X)}}$ ${\displaystyle a\leq \operatorname {E} (X)}$ ${\displaystyle a\geq \operatorname {E} (X)}$ $${\displaystyle C(a)=\inf _{t}M(t)e^{-ta}}$$ ${\displaystyle X}$

Логарифм двусторонней границы Чернова известен как функция скорости (или преобразование Крамера ) . Это эквивалентно преобразованию Лежандра-Фенхеля или выпуклому сопряжению производящей функции кумулянта , определяемому как: Производящая функция момента является лог-выпуклой , поэтому по свойству выпуклого сопряжения граница Чернова должна быть лог-вогнутой . Граница Чернова достигает максимума в среднем , и является инвариантной относительно трансляции: . ${\displaystyle I=-\log C}$ ${\displaystyle K=\log M}$ $${\displaystyle I(a)=\sup _{t}at-K(t)}$$ ${\displaystyle C(\operatorname {E} (X))=1}$ ${\textstyle C_{X+k}(a)=C_{X}(a-k)}$

Граница Чернова точна тогда и только тогда, когда это одна концентрированная масса ( вырожденное распределение ). Граница точная только в крайних значениях ограниченной случайной величины или за их пределами, где нижняя граница достигается при бесконечном . Для неограниченных случайных величин граница нигде не является жесткой, хотя она асимптотически точна с точностью до субэкспоненциальных факторов («экспоненциально узкая»). ^{[ нужна цитата ]} Отдельные моменты могут обеспечить более жесткие границы за счет большей аналитической сложности. ^[7] ${\displaystyle X}$ ${\displaystyle t}$

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

Нижние границы MGF

Используя только производящую функцию момента, нижнюю границу вероятностей хвоста можно получить, применив неравенство Пэли-Зигмунда к , что дает: (ограничение на левый хвост получается для отрицательного ). Однако в отличие от границы Чернова этот результат не является экспоненциально точным. ${\displaystyle e^{tX}}$ $${\displaystyle \operatorname {P} \left(X>a\right)\geq \sup _{t>0\land M(t)\geq e^{ta}}\left(1-{\frac {e^{ta}}{M(t)}}\right)^{2}{\frac {M(t)^{2}}{M(2t)}}}$$ ${\displaystyle t}$

Теодосопулос ^[9] построил точную нижнюю границу на основе MGF, используя процедуру экспоненциального наклона .

Для конкретных распределений (таких как биномиальное ) часто доступны нижние границы того же экспоненциального порядка, что и граница Чернова.

Суммы независимых случайных величин

Когда X представляет собой сумму n независимых случайных величин X ₁ , ..., X _n , производящая функция момента X является произведением отдельных производящих функций момента, что дает следующее:

и:

${\displaystyle \Pr(X\leq a)\leq \inf _{t<0}e^{-ta}\prod _{i}\operatorname {E} \left[e^{tX_{i}}\right]}$

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

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

Суммы независимых ограниченных случайных величин

Границы Чернова также могут применяться к общим суммам независимых ограниченных случайных величин, независимо от их распределения; это известно как неравенство Хеффдинга . Доказательство использует тот же подход, что и другие границы Чернова, но с применением леммы Хёффдинга для оценки производящих функций момента (см. неравенство Хёффдинга ).

Неравенство Хеффдинга . Предположим, что X ₁ , ..., X _n — независимые случайные величины, принимающие значения в [a,b]. Пусть X обозначает их сумму и пусть µ = E[ X ] обозначает ожидаемое значение суммы. Тогда длялюбого ${\displaystyle t>0}$

${\displaystyle \Pr(X\leq \mu -t)<e^{-2t^{2}/(n(b-a)^{2})},}$

${\displaystyle \Pr(X\geq \mu +t)<e^{-2t^{2}/(n(b-a)^{2})}.}$

Суммы независимых случайных величин Бернулли

Оценки в следующих разделах для случайных величин Бернулли получены с использованием того, что для случайной величины Бернулли с вероятностью p , равной 1, ${\displaystyle X_{i}}$

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

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

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

Мультипликативная граница Чернова. Предположим, что X ₁ , ..., X _n — независимые случайные величины, принимающие значения в {0, 1}. Пусть X обозначает их сумму и пусть µ = E[ X ] обозначает ожидаемое значение суммы. Тогда для любого δ > 0

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

Аналогичную стратегию доказательства можно использовать, чтобы показать, что при 0 < δ < 1

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

Приведенная выше формула на практике зачастую оказывается громоздкой, поэтому часто используют следующие более слабые, но более удобные оценки ^[10] , которые следуют из неравенства из списка логарифмических неравенств : ${\displaystyle \textstyle {\frac {2\delta }{2+\delta }}\leq \log(1+\delta )}$

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

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

${\displaystyle \Pr(|X-\mu |\geq \delta \mu )\leq 2e^{-\delta ^{2}\mu /3},\qquad 0<\delta <1.}$

Обратите внимание, что границы для . ${\displaystyle \delta =0}$

Кроме того, на основе разложения Тейлора для W-функции Ламберта [ ^11]

${\displaystyle \Pr(X\geq R)\leq 2^{-xR},\qquad x>0,\ R\geq (2^{x}e-1)\mu .}$

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

Следующая теорема принадлежит Василию Хёффдингу ^[12] и поэтому называется теоремой Чернова–Хеффдинга.

Теорема Чернова–Хефдинга. Предположим, что X ₁ , ..., X _n — случайные величины iid , принимающие значения в {0, 1}. Пусть p = E[ X ₁ ] и ε > 0 .

${\displaystyle {\begin{aligned}\Pr \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}\\\Pr \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 соответственно. Если р ≥ ⁠1/2⁠ , тоэто означает ${\displaystyle D(p+\varepsilon \parallel p)\geq {\tfrac {\varepsilon ^{2}}{2p(1-p)}}}$

${\displaystyle \Pr \left({\frac {1}{n}}\sum X_{i}>p+x\right)\leq \exp \left(-{\frac {x^{2}n}{2p(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⁠ также используются.

Приложения

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

Проблема балансировки множества возникает при планировании статистических экспериментов. Обычно при планировании статистического эксперимента, учитывая особенности каждого участника эксперимента, нам необходимо знать, как разделить участников на две непересекающиеся группы так, чтобы каждая особенность была примерно максимально сбалансирована между двумя группами. ^[13]

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

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

Границы Чернова можно эффективно использовать для оценки «уровня устойчивости» приложения/алгоритма путем исследования его пространства возмущений с помощью рандомизации. ^[15] Использование границы Чернова позволяет отказаться от сильной — и по большей части нереалистичной — гипотезы малого возмущения (величина возмущения мала). Уровень устойчивости, в свою очередь, может использоваться либо для подтверждения, либо для отклонения конкретного алгоритмического выбора, аппаратной реализации или приемлемости решения, на структурные параметры которого влияют неопределенности.

Простое и распространенное использование границ Чернова — для «усиления» рандомизированных алгоритмов . Если у вас есть алгоритм, который выводит предположение, которое является желаемым ответом с вероятностью p > 1/2, то можно получить более высокий уровень успеха, запустив алгоритм несколько раз и выведя предположение, которое выводится более чем n /2 прогонами алгоритм. (Таких предположений не может быть более одного.) Если предположить, что эти прогоны алгоритма независимы, вероятность того, что более n /2 предположений верны, равна вероятности того, что сумма независимых случайных величин Бернулли X _k , равная 1 с вероятностью p больше n /2. Это можно показать, по крайней мере, с помощью мультипликативной границы Чернова (следствие 13.3 в классных заметках Синклера, µ = np ).: ^[16] ${\displaystyle n=\log(1/\delta )2p/(p-1/2)^{2}}$ ${\displaystyle 1-\delta }$

${\displaystyle \Pr \left[X>{n \over 2}\right]\geq 1-e^{-n\left(p-1/2\right)^{2}/(2p)}\geq 1-\delta }$

Матрица Чернова связана

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

Пусть M ₁ , ..., M _t — независимые матричные случайные величины такие, что и . Обозначим через операторную норму матрицы . Если почти наверняка верно для всех , то для любого ε > 0 ${\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\}}$

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

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

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

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

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

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

${\displaystyle \Pr \left(\left\|{\frac {1}{t}}\sum _{i=1}^{t}M_{i}-\operatorname {E} [M]\right\|>\varepsilon \right)\leq {\frac {1}{\mathbf {poly} (t)}}}$

где M ₁ , ..., M _t являются iid копиями M .

Выборочный вариант

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

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

Предположим, мы выбираем целое число k и случайную выборку S  ⊂  A размера k . Отметьте относительный размер подгруппы населения в выборке (| B ∩ S |/| S |) посредством r _S .

Тогда для каждой дроби d  ∈ [0,1]:

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

В частности, если B является большинством в A (т.е. r  > 0,5), мы можем ограничить вероятность того, что B останется большинством в S ( r _S  > 0,5), приняв: d  = 1 − 1/(2 r ): ^{[21 ]}

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

Эта граница, конечно, совсем не жесткая. Например, когда r  = 0,5, мы получаем тривиальную оценку Prob > 0.

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

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

Следуя условиям мультипликативной границы Чернова, пусть X ₁ , ..., X _n являются независимыми случайными величинами Бернулли , сумма которых равна X , каждая из которых имеет вероятность p _i быть равной 1. Для переменной Бернулли:

${\displaystyle \operatorname {E} \left[e^{t\cdot X_{i}}\right]=(1-p_{i})e^{0}+p_{i}e^{t}=1+p_{i}(e^{t}-1)\leq e^{p_{i}(e^{t}-1)}}$

Итак, используя ( 1 ) с для любого и где , ${\displaystyle a=(1+\delta )\mu }$ ${\displaystyle \delta >0}$ ${\displaystyle \mu =\operatorname {E} [X]=\textstyle \sum _{i=1}^{n}p_{i}}$

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

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

${\displaystyle \exp {\Big (}-t(1+\delta )\mu +(e^{t}-1)\mu {\Big )}={\frac {\exp((1+\delta -1)\mu )}{(1+\delta )^{(1+\delta )\mu }}}=\left[{\frac {e^{\delta }}{(1+\delta )^{(1+\delta )}}}\right]^{\mu }.}$

Это доказывает желаемый результат.

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

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

${\displaystyle \Pr \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 {\operatorname {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 {\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=\log \left({\frac {(1-p)q}{(1-q)p}}\right).}$

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

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

Теперь у нас есть желаемый результат:

${\displaystyle \Pr \left({\tfrac {1}{n}}\sum X_{i}\geq p+\varepsilon \right)\leq e^{-D(p+\varepsilon \parallel p)n}.}$

Чтобы завершить доказательство для симметричного случая, мы просто определяем случайную величину Y _i = 1 − X _i , применяем то же доказательство и подключаем его к нашей оценке.

Смотрите также

• Неравенства Бернштейна
• Неравенство концентрации — сводка хвостовых границ случайных величин.
• Теорема Крамера
• Энтропийное значение под угрозой
• Неравенство Хефдинга
• Матрица Чернова связана
• Функция генерации момента

Рекомендации

1. Бушерон, Стефан (2013). Неравенства концентрации: неасимптотическая теория независимости. Габор Лугоши, Паскаль Массар. Оксфорд: Издательство Оксфордского университета. п. 21. ISBN 978-0-19-953525-5. ОКЛК  837517674.
2. Уэйнрайт, М. (22 января 2015 г.). «Основные границы хвоста и концентрации» (PDF) . Архивировано (PDF) из оригинала 8 мая 2016 г.
3. Вершинин, Роман (2018). Многомерная вероятность: введение в приложения в науке о данных. Кембридж, Великобритания. п. 19. ISBN 978-1-108-41519-4. ОСЛК  1029247498.{{cite book}}: CS1 maint: location missing publisher (link)
4. Тропп, Джоэл А. (26 мая 2015 г.). «Введение в матричные неравенства концентрации». Основы и тенденции в машинном обучении . 8 (1–2): 60. arXiv : 1501.01571 . дои : 10.1561/2200000048. ISSN  1935-8237. S2CID  5679583.
5. Чернов, Герман (1952). «Мера асимптотической эффективности проверки гипотезы, основанной на сумме наблюдений». Анналы математической статистики . 23 (4): 493–507. дои : 10.1214/aoms/1177729330 . ISSN  0003-4851. JSTOR  2236576.
6. Чернов, Герман (2014). «Карьера в статистике» (PDF) . В Линь, Сихун; Дженест, Кристиан; Бэнкс, Дэвид Л.; Моленбергс, Герт; Скотт, Дэвид В.; Ван, Джейн-Линг (ред.). Прошлое, настоящее и будущее статистики. ЦРК Пресс. п. 35. ISBN 9781482204964. Архивировано из оригинала (PDF) 11 февраля 2015 г.
7. Филипс, Томас К.; Нельсон, Рэндольф (1995). «Граница момента более жесткая, чем граница Чернова для вероятностей положительного хвоста». Американский статистик . 49 (2): 175–178. дои : 10.2307/2684633. ISSN  0003-1305. JSTOR  2684633.
8. Гош, малайский (04 марта 2021 г.). «Экспоненциальные границы хвоста для хи-квадрат случайных величин». Журнал статистической теории и практики . 15 (2): 35. дои : 10.1007/s42519-020-00156-x . ISSN  1559-8616. S2CID  233546315.
9. Теодсопулос, Тед (1 марта 2007 г.). «Реверс границы Чернова». Статистика и вероятностные буквы . 77 (5): 558–565. arXiv : math/0501360 . дои : 10.1016/j.spl.2006.09.003. ISSN  0167-7152. S2CID  16139953.
10. Митценмахер, Майкл; Упфал, Эли (2005). Вероятность и вычисления: рандомизированные алгоритмы и вероятностный анализ. Издательство Кембриджского университета. ISBN 978-0-521-83540-4.
11. Дилленкур, Майкл; Гудрич, Майкл; Митценмахер, Майкл (2024). «Использование параметризованных границ Чернова для упрощенного анализа алгоритмов». Письма об обработке информации . 187 (106516). дои : 10.1016/j.ipl.2024.106516 .
12. Хоффдинг, В. (1963). «Вероятностные неравенства для сумм ограниченных случайных величин» (PDF) . Журнал Американской статистической ассоциации . 58 (301): 13–30. дои : 10.2307/2282952. JSTOR  2282952.
13. Обратитесь к этому разделу книги для получения дополнительной информации о проблеме.
14. Кернс, М.; Вазирани, У. (1994). Введение в теорию вычислительного обучения . МТИ Пресс. Глава 9 (Приложение), стр. 190–192. ISBN 0-262-11193-4.
15. Алиппи, К. (2014). «Рандомизированные алгоритмы». Интеллект для встраиваемых систем . Спрингер. ISBN 978-3-319-05278-6.
16. Синклер, Алистер (осень 2011 г.). «Конспекты по курсу «Случайность и вычисления»» (PDF) . Архивировано из оригинала (PDF) 31 октября 2014 года . Проверено 30 октября 2014 г.
17. Альсведе, Р.; Зима, А. (2003). «Сильный конверс для идентификации по квантовым каналам». Транзакции IEEE по теории информации . 48 (3): 569–579. arXiv : Quant-ph/0012127 . дои : 10.1109/18.985947. S2CID  523176.
18. Тропп, Дж. (2010). «Удобные хвостовые оценки сумм случайных матриц». Основы вычислительной математики . 12 (4): 389–434. arXiv : 1004.4389 . doi : 10.1007/s10208-011-9099-z. S2CID  17735965.
19. Маген, А .; Зузиас, А. (2011). «Низкоранговые матричные границы Чернова и приближенное умножение матриц». arXiv : 1005.2724 [cs.DM].
20. Гольдберг, А.В.; Хартлайн, Джей Ди (2001). «Конкурентные аукционы по продаже нескольких цифровых товаров». Алгоритмы — ЕКА 2001 . Конспекты лекций по информатике. Том. 2161. с. 416. CiteSeerX 10.1.1.8.5115 . дои : 10.1007/3-540-44676-1_35. ISBN  978-3-540-42493-2.; лемма 6.1
21. См. графики: граница как функция от r при изменении k и граница как функция от k при изменении r.

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

• Чернов, Х. (1952). «Мера асимптотической эффективности проверки гипотезы, основанной на сумме наблюдений». Анналы математической статистики . 23 (4): 493–507. дои : 10.1214/aoms/1177729330 . JSTOR  2236576. MR  0057518. Zbl  0048.11804.
• Чернофф, Х. (1981). «Заметка о неравенстве, связанном с нормальным распределением». Анналы вероятности . 9 (3): 533–535. дои : 10.1214/aop/1176994428 . JSTOR  2243541. MR  0614640. Збл  0457.60014.
• Хагеруп, Т.; Руб, К. (1990). «Экскурсия по пределам Чернова». Письма об обработке информации . 33 (6): 305. doi :10.1016/0020-0190(90)90214-I.
• Нильсен, Ф. (2011). «Информационно-геометрическая характеристика информации Чернова». Письма об обработке сигналов IEEE . 20 (3): 269–272. arXiv : 1102.2684 . дои :10.1109/ЛСП.2013.2243726. S2CID  15034953.