Обратный Чернов

31

Существует ли обратная граница Черноффа, определяющая, что вероятность хвоста хотя бы так велика?

т.е. если являются независимыми биномиальными случайными переменными и . Тогда мы можем доказать для некоторой функции .X1,X2,,Xnμ=E[i=1nXi]Pr[i=1nXi(1+δ)μ]f(μ,δ,n)f

Ашвинкумар Б.В.
источник
1
Ваш пример требует слишком много: при стандартная граница Черноффа показывает, что и \ Pr [| T \ cap S_2 | \ sqrt {1.1} \ leq n ^ {1/3}] не более \ exp (-cn ^ { 1/3}) для некоторых в . p=n2/3Pr[|TS1|1.1n1/3]Pr[|TS2|1.1n1/3]exp(cn1/3)c
Колин Маккуиллан
Вы правы, я запутался в том, какой термин в черновом переплете имеет квадрат. Я изменил вопрос, чтобы отразить более слабую границу. Я не думаю, что это поможет мне в моем текущем приложении, но это может быть интересно по другим причинам.
Ашвинкумар Б.В.

Ответы:

28

Вот явное доказательство того, что стандартная оценка Чернова тесно связана с постоянными множителями в показателе степени для определенного диапазона параметров. (В частности, всякий раз, когда переменные равны 0 или 1, и 1 с вероятностью 1/2 или меньше, и ϵ(0,1/2) , а верхняя граница Чернова меньше константы.)

Если вы нашли ошибку, пожалуйста, дайте мне знать.

Лемма 1. (теснота границы Чернова). Пусть X - среднее значение k независимых 0/1 случайных величин (rv). Для любых ϵ(0,1/2] и p(0,1/2] , предполагая, что ϵ2pk3 ,

(i) Если каждый rv равен 1 с вероятностью не более p , то

Pr[X(1ϵ)p]  exp(9ϵ2pk).

(ii) Если каждый rv равен 1 с вероятностью не менее p , то

Pr[X(1+ϵ)p]  exp(9ϵ2pk).

Доказательство. Мы используем следующее наблюдение:

Утверждение 1. Если , то 1k1(k)  1e2π(k)(kk)k

Доказательство утверждения 1. В приближении Стирлинга гдеi!=2πi(i/e)ieλλ[1/(12i+1),1/12i].

Таким образом, , который является , по крайней мере, QED(k)k!!(k)!

2πk(ke)k2π(e)  2π(k)(ke)kexp(112k+1112112(k))
  12π(k)(kk)ke1.

Доказательство леммы 1 часть (i). Без ограничения общности предположим, что каждая 0/1 случайная величина в сумме равна 1 с вероятностью ровно . Примечание. равно сумме , и .X pPr[X(1ϵ)p]i=0(1ϵ)pkPr[X=i/k]Pr[X=i/k]=(ki)pi(1p)ki

Исправьте . Слагаемые в сумме растут, поэтому каждый член с индексом имеет значение не менее , поэтому их сумма имеет суммарное значение не менее . Для завершения доказательства покажем, что =(12ϵ)pk+1iPr[X=/k](ϵpk2)Pr[X=/k]

(ϵpk2)Pr[X=/k]  exp(9ϵ2pk).

Предположения и дают , поэтому левая часть выше по крайней мере . Используя пункт 1, чтобы ограничить , это в свою очередь, по крайней мере, где и ϵ2pk3ϵ1/2ϵpk623ϵpk(k)p(1p)k(k)ABA=23eϵpk/2πB=(k)(kk)kp(1p)k.

Чтобы закончить, мы показываем и .Aexp(ϵ2pk)Bexp(8ϵ2pk)

Утверждение 2. Aexp(ϵ2pk)

Доказательство утверждения 2. Предположения и подразумевают (i) .ϵ2pk3ϵ1/2pk12

По определению, . По (i) . Таким образом, (ii) .pk+1pk121.1pk

Подстановка правой части (ii) для в дает (iii) .AA23eϵpk/2.2π

Предположение подразумевает , что с помощью (iii) дает (iv) .ϵ2pk3ϵpk3A23e3/2.2π0.1

Из следует, что (v) .ϵ2pk3exp(ϵ2pk)exp(3)0.04

(iv) и (v) вместе дают иск. QED

Утверждение 3. .Bexp(8ϵ2pk)

Доказательство утверждения 3. Зафиксируйте , чтобы . Выбор подразумевает , поэтому утверждение будет выполняться до тех пор, пока . Принимая каждую сторону этого последнего неравенства в степень и упрощая, оно эквивалентно Подставляя и упрощая, он эквивалентен δ=(1δ)pk
δ2ϵBexp(2δ2pk)1/

pk(k(1p)k)k/1  exp(2δ2pk).
=(1δ)pk
(1δ)(1+δp1p)1(1δ)p1  exp(2δ21δ).
Если взять логарифм обеих сторон и дважды использовать , он будет держаться до тех пор, пока Левая часть выше упрощается до , что меньше потому что , QEDln(1+z)z
δ+δp1p(1(1δ)p1)  2δ21δ.
δ2/(1p)(1δ)2δ2/(1δ)p1/2

Утверждения 2 и 3 подразумевают . Это подразумевает часть (i) леммы.ABexp(ϵ2pk)exp(8ϵ2pk)

Доказательство леммы 1 ч. (Ii). Без ограничения общности предположим, что каждая случайная величина равна с вероятностью ровно .1p

Примечание . Исправьте .Pr[X(1+ϵ)p]=i=(1ϵ)pknPr[X=i/k]^=(1+2ϵ)pk1

Последние члены в общей сумме не менее , что не менее . (Доказательство тому же, что и для (i), за исключением того, что заменяется на а заменяется на , так что .) КЭДϵpk(ϵpk2)Pr[X=^/k]exp(9ϵ2pk)^δδ^^=(1+δ^)pk

Нил Янг
источник
Несколько [математических ошибок обработки] - есть ли шанс их исправить?
Арье
Те математические выражения, используемые для отображения просто отлично. По некоторым причинам команда \ choose не работает в mathjax. Ни один не \ binom. Например, $ a \ choose b $ дает . Предположительно это ошибка в конфигурации mathjax. Надеюсь, это будет исправлено в ближайшее время. Тем временем см. Лемму 5.2 в приложении к arxiv.org/pdf/cs/0205046v2.pdf или cs.ucr.edu/~neal/Klein15Number . (ab)
Нил Янг
22

Теорема Берри-Эссеена может дать нижние оценки вероятности хвоста, если они выше, чем .n1/2

Еще один инструмент, который вы можете использовать, это неравенство Пейли-Зигмунда . Это означает, что для любого четного целого числа и любой действительной случайной величины ,kX

Pr[|X|>=12(E[Xk])1/k]E[Xk]24E[X2k]

Вместе с полиномиальной теоремой для сумма случайных величин rademacher Пейли-Зигмунда может дать вам довольно сильные нижние оценки. Также он работает со случайными переменными с ограниченной независимостью. Например, вы легко получаете, что сумма 4-независимых независимых переменных равна с постоянной вероятностью.Xnn±1Ω(n)

Сашо Николов
источник
14

Если вы действительно в порядке с ограничивающими суммами испытаний Бернулли (а не, скажем, ограниченных случайных величин), то следующее довольно трудное.

Неравенство Слуда *. Пусть это ничья из розыгрыша Бернулли с , и пусть задано целое число . Если либо (a) и , либо (b) , то где - это cdf стандартного нормали.{Xi}i=1nE(X1)=pknp1/4npknpkn(1p)

Pr[iXik]1Φ(knpnp(1p)),
Φ

(Рассматривая аргумент как преобразование стандартной нормали, это в точности соответствует тому, что говорит вам CLT; фактически, он говорит нам, что биномы, удовлетворяющие условиям теоремы, будут доминировать над соответствующими им гауссианами на верхних хвостах.)Φ

Отсюда вы можете использовать границы чтобы получить что-то более приятное. Например, в первой книге Феллера в разделе о гауссианах для каждого показано, что где - плотность стандартной нормали. В статье в Википедии есть аналогичные оценки и для «Q-функции».Φz>0

z1+z2φ(z)<1Φ(z)<1zφ(z),
φ

Помимо этого, и того, что говорили другие люди, вы также можете попробовать использовать Бином непосредственно, возможно, с каким-нибудь Стирлингом.

(*) Некоторые более новые утверждения о неравенстве Слуда исключают некоторые из этих условий; Я воспроизвел один в статье Слуда.

Матус
источник
7

Теорема де Муавра-Лапласа показывает, что переменные типапосле соответствующей нормализации и при определенных условиях сойдутся в распределении к нормальному распределению. Этого достаточно, если вы хотите постоянные нижние границы.|TS1|

Для нижних границ, таких как , вам понадобится немного более тонкий инструмент. Вот одно упоминание, о котором я знаю (но только случайно - у меня никогда не было возможности использовать такое неравенство самостоятельно). Некоторые явные нижние оценки вероятностей хвостов биномиальных распределений приведены в виде теоремы 1.5 книги Случайные графы Белы Боллобаса, Кембридж, 2-е издание, где даны дополнительные ссылки на Введение в вероятность и ее применения Феллера и Основы вероятности Рени.nc

Колин Маккуиллан
источник
4

Обобщенная теорема Литтлвуда-Оффорда не совсем то, что вам нужно, но она дает то, что я считаю «обратной черновской» границей, показывая, что сумма случайных величин вряд ли попадет в небольшой диапазон вокруг какого-либо конкретного значения (включая ожидание). Возможно, это будет полезно.

Формально теорема состоит в следующем.

Обобщенная теорема Литтлвуда-Оффорда : Пусть и - такие действительные числа, что для и пусть - независимые случайные величины со значениями ноль и единица. Предположим, что для для всех . Тогда для любого , где - константа, зависящая только от .a1,,ans>0|ai|s1inX1,,Xn0<p12pPr[Xi=0]1p1inrR

Pr[ri=1naiXi<r+s]cpn
cpp
Лев Рейзин
источник
3
Другим может быть полезно знать, что этот тип результата также известен как «неравенство маленьких шариков», и Нгуен и Ву провели потрясающий опрос people.math.osu.edu/nguyen.1261/cikk/LO-survey.pdf , Моя точка зрения здесь немного отличается от вашей. Я думаю, что «обратный черновский» предел дает более низкую оценку вероятностной массы маленького шарика около 0. Я думаю, что неравенство маленького шарика качественно говорит о том, что вероятность маленького шарика максимизируется шаром при 0. В этом Смысл обратной черновской оценки обычно легче доказать, чем неравенства малых шариков.
Сашо Николов
3

Показатель степени в стандартной границе Черноффа, как это указано в Википедии, является жестким для 0/1-значных случайных величин. Пусть а - последовательность независимых случайных величин, такая что для каждого , и . Тогда для любого , 0<p<1X1,X2,iPr[Xi=1]=pPr[Xi=0]=1pε>0

2D(p+εp)nn+1Pr[i=1nXi(p+ε)n]2D(p+εp)n.

Здесь , что является дивергенцией Кульбака-Лейблера между случайными значениями Бернулли переменные с параметрами и .D(xy)=xlog2(x/y)+(1x)log2((1x)/(1y))xy

Как уже упоминалось, верхняя граница в неравенстве выше доказана в Википедии ( https://en.wikipedia.org/wiki/Chernoff_bound ) под названием «Теорема Чернова-Хеффдинга, аддитивная форма». Нижняя граница может быть доказана с помощью, например, «метода типов». См. Лемму II.2 в [1]. Кроме того, это описано в классическом учебнике по теории информации, написанном Кавером и Томасом.

[1] Имре Цишар: метод типов. IEEE Труды по теории информации (1998). http://dx.doi.org/10.1109/18.720546

JWM
источник
Также стоит отметить, что , а для общего случая это . Это показывает, что когда типичная граница является четкой. (И когда для ). D(p+δpp)=p22pδ2+O(δ3)p=1/212δ2+O(δ4)δ=O(n1/3)eCδ2δ=O(n1/4)p=1/2
Томас Але