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

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

В теории вероятностей граница Чернова — это экспоненциально убывающая верхняя граница на хвосте случайной величины, основанная на ее функции генерации моментов . Минимум всех таких экспоненциальных границ образует границу Чернова или Чернова-Крамера , которая может затухать быстрее экспоненциальной (например, субгауссовской ). ^{[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}$

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

Нижние границы от 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 — это независимые случайные величины, принимающие значения в {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 соответственно. Если p ≥ ⁠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 ε 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⁠ , также используются.

Приложения

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

Проблема балансировки набора возникает при планировании статистических экспериментов. Обычно при планировании статистического эксперимента, учитывая особенности каждого участника эксперимента, нам нужно знать, как разделить участников на 2 непересекающиеся группы таким образом, чтобы каждая особенность была примерно максимально сбалансирована между двумя группами. ^[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 — это идентичные копии 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). Неравенства концентрации: неасимптотическая теория независимости. Габор Лугоши, Паскаль Массар. Оксфорд: Oxford University Press. стр. 21. ISBN 978-0-19-953525-5. OCLC  837517674.
2. Уэйнрайт, М. (22 января 2015 г.). "Базовый хвост и границы концентрации" (PDF) . Архивировано (PDF) из оригинала 2016-05-08.
3. Вершинин, Роман (2018). Высокомерная вероятность: введение с приложениями в науке о данных. Кембридж, Великобритания. С. 19. ISBN 978-1-108-41519-4. OCLC  1029247498.{{cite book}}: CS1 maint: location missing publisher (link)
4. Тропп, Джоэл А. (2015-05-26). «Введение в неравенства концентрации матриц». Основы и тенденции в машинном обучении . 8 (1–2): 60. arXiv : 1501.01571 . doi :10.1561/2200000048. ISSN  1935-8237. S2CID  5679583.
5. Чернофф, Герман (1952). «Мера асимптотической эффективности для проверки гипотезы на основе суммы наблюдений». Анналы математической статистики . 23 (4): 493–507. doi : 10.1214/aoms/1177729330 . ISSN  0003-4851. JSTOR  2236576.
6. Чернофф, Герман (2014). «Карьера в статистике» (PDF) . В Lin, Xihong; Genest, Christian; Banks, David L.; Molenberghs, Geert; Scott, David W.; Wang, Jane-Ling (ред.). Прошлое, настоящее и будущее статистики. CRC Press. стр. 35. ISBN 9781482204964. Архивировано из оригинала (PDF) 2015-02-11.
7. Филипс, Томас К.; Нельсон, Рэндольф (1995). «Граница момента жестче, чем граница Чернова для положительных хвостовых вероятностей». The American Statistician . 49 (2): 175–178. doi :10.2307/2684633. ISSN  0003-1305. JSTOR  2684633.
8. Гош, Малай (2021-03-04). "Экспоненциальные границы хвоста для хи-квадратных случайных величин". Журнал статистической теории и практики . 15 (2): 35. doi : 10.1007/s42519-020-00156-x . ISSN  1559-8616. S2CID  233546315.
9. Теодосопоулос, Тед (2007-03-01). «Возврат границы Чернова». Statistics & Probability Letters . 77 (5): 558–565. arXiv : math/0501360 . doi :10.1016/j.spl.2006.09.003. ISSN  0167-7152. S2CID  16139953.
10. Митценмахер, Майкл; Упфал, Эли (2005). Вероятность и вычисления: рандомизированные алгоритмы и вероятностный анализ. Cambridge University Press. ISBN 978-0-521-83540-4.
11. Дилленкурт, Майкл; Гудрич, Майкл; Митценмахер, Майкл (2024). «Использование параметризованных границ Чернова для упрощенного анализа алгоритмов». Information Processing Letters . 187 (106516). doi : 10.1016/j.ipl.2024.106516 .
12. Hoeffding, W. (1963). "Вероятностные неравенства для сумм ограниченных случайных величин" (PDF) . Журнал Американской статистической ассоциации . 58 (301): 13–30. doi :10.2307/2282952. JSTOR  2282952.
13. Более подробную информацию об этой проблеме можно найти в этом разделе книги.
14. Кернс, М.; Вазирани, У. (1994). Введение в теорию вычислительного обучения . MIT Press. Глава 9 (Приложение), страницы 190–192. ISBN 0-262-11193-4.
15. Alippi, C. (2014). «Рандомизированные алгоритмы». Интеллект для встроенных систем . Springer. 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 . doi : 10.1109/18.985947. S2CID  523176.
18. Tropp, J. (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). «Конкурентные аукционы для нескольких цифровых товаров». Алгоритмы — ESA 2001. Конспект лекций по информатике. Том 2161. стр. 416. CiteSeerX 10.1.1.8.5115 . doi :10.1007/3-540-44676-1_35. ISBN  978-3-540-42493-2.; лемма 6.1
21. Смотрите графики: границы как функции r при изменении k и границы как функции k при изменении r.

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

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