Существует ли обратная граница Черноффа, определяющая, что вероятность хвоста хотя бы так велика?
т.е. если являются независимыми биномиальными случайными переменными и . Тогда мы можем доказать для некоторой функции .
pr.probability
chernoff-bound
Ашвинкумар Б.В.
источник
источник
Ответы:
Вот явное доказательство того, что стандартная оценка Чернова тесно связана с постоянными множителями в показателе степени для определенного диапазона параметров. (В частности, всякий раз, когда переменные равны 0 или 1, и 1 с вероятностью 1/2 или меньше, иϵ∈(0,1/2) , а верхняя граница Чернова меньше константы.)
Если вы нашли ошибку, пожалуйста, дайте мне знать.
Лемма 1. (теснота границы Чернова). ПустьX - среднее значение k независимых 0/1 случайных величин (rv). Для любых ϵ∈(0,1/2] и p∈(0,1/2] , предполагая, что ϵ2pk≥3 ,
(i) Если каждый rv равен 1 с вероятностью не болееp , то
(ii) Если каждый rv равен 1 с вероятностью не менееp , то
Доказательство. Мы используем следующее наблюдение:
Утверждение 1. Если , то1≤ℓ≤k−1 (kℓ) ≥ 1e2πℓ−−−√(kℓ)ℓ(kk−ℓ)k−ℓ
Доказательство утверждения 1. В приближении Стирлинга гдеi!=2πi−−−√(i/e)ieλ λ∈[1/(12i+1),1/12i].
Таким образом, , который является , по крайней мере, QED(kℓ) k!ℓ!(k−ℓ)!
Доказательство леммы 1 часть (i). Без ограничения общности предположим, что каждая 0/1 случайная величина в сумме равна 1 с вероятностью ровно . Примечание. равно сумме , и .X p Pr[X≤(1−ϵ)p] ∑⌊(1−ϵ)pk⌋i=0Pr[X=i/k] Pr[X=i/k]=(ki)pi(1−p)k−i
Исправьте . Слагаемые в сумме растут, поэтому каждый член с индексом имеет значение не менее , поэтому их сумма имеет суммарное значение не менее . Для завершения доказательства покажем, чтоℓ=⌊(1−2ϵ)pk⌋+1 i≥ℓ Pr[X=ℓ/k] (ϵpk−2)Pr[X=ℓ/k]
Предположения и дают , поэтому левая часть выше по крайней мере . Используя пункт 1, чтобы ограничить , это в свою очередь, по крайней мере, где иϵ2pk≥3 ϵ≤1/2 ϵpk≥6 23ϵpk(kℓ)pℓ(1−p)k−ℓ (kℓ) AB A=23eϵpk/2πℓ−−−√ B=(kℓ)ℓ(kk−ℓ)k−ℓpℓ(1−p)k−ℓ.
Чтобы закончить, мы показываем и .A≥exp(−ϵ2pk) B≥exp(−8ϵ2pk)
Утверждение 2.A≥exp(−ϵ2pk)
Доказательство утверждения 2. Предположения и подразумевают (i) .ϵ2pk≥3 ϵ≤1/2 pk≥12
По определению, . По (i) . Таким образом, (ii) .ℓ≤pk+1 pk≥12 ℓ≤1.1pk
Подстановка правой части (ii) для в дает (iii) .ℓ A A≥23eϵpk/2.2π−−−−−−√
Предположение подразумевает , что с помощью (iii) дает (iv) .ϵ2pk≥3 ϵpk−−√≥3–√ A≥23e3/2.2π−−−−−−√≥0.1
Из следует, что (v) .ϵ2pk≥3 exp(−ϵ2pk)≤exp(−3)≤0.04
(iv) и (v) вместе дают иск. QED
Утверждение 3. .B≥exp(−8ϵ2pk)
Доказательство утверждения 3. Зафиксируйте , чтобы . Выбор подразумевает , поэтому утверждение будет выполняться до тех пор, пока . Принимая каждую сторону этого последнего неравенства в степень и упрощая, оно эквивалентно Подставляя и упрощая, он эквивалентенδ ℓ=(1−δ)pk
ℓ δ≤2ϵ B≥exp(−2δ2pk) −1/ℓ
Утверждения 2 и 3 подразумевают . Это подразумевает часть (i) леммы.AB≥exp(−ϵ2pk)exp(−8ϵ2pk)
Доказательство леммы 1 ч. (Ii). Без ограничения общности предположим, что каждая случайная величина равна с вероятностью ровно .1 p
Примечание . Исправьте .Pr[X≥(1+ϵ)p]=∑ni=⌈(1−ϵ)pk⌉Pr[X=i/k] ℓ^=⌈(1+2ϵ)pk⌉−1
Последние члены в общей сумме не менее , что не менее . (Доказательство тому же, что и для (i), за исключением того, что заменяется на а заменяется на , так что .) КЭДϵpk (ϵpk−2)Pr[X=ℓ^/k] exp(−9ϵ2pk) ℓ ℓ^ δ −δ^ ℓ^=(1+δ^)pk
источник
Теорема Берри-Эссеена может дать нижние оценки вероятности хвоста, если они выше, чем .n−1/2
Еще один инструмент, который вы можете использовать, это неравенство Пейли-Зигмунда . Это означает, что для любого четного целого числа и любой действительной случайной величины ,k X
Вместе с полиномиальной теоремой для сумма случайных величин rademacher Пейли-Зигмунда может дать вам довольно сильные нижние оценки. Также он работает со случайными переменными с ограниченной независимостью. Например, вы легко получаете, что сумма 4-независимых независимых переменных равна с постоянной вероятностью.X n n ±1 Ω(n−−√)
источник
Если вы действительно в порядке с ограничивающими суммами испытаний Бернулли (а не, скажем, ограниченных случайных величин), то следующее довольно трудное.
(Рассматривая аргумент как преобразование стандартной нормали, это в точности соответствует тому, что говорит вам CLT; фактически, он говорит нам, что биномы, удовлетворяющие условиям теоремы, будут доминировать над соответствующими им гауссианами на верхних хвостах.)Φ
Отсюда вы можете использовать границы чтобы получить что-то более приятное. Например, в первой книге Феллера в разделе о гауссианах для каждого показано, что где - плотность стандартной нормали. В статье в Википедии есть аналогичные оценки и для «Q-функции».Φ z>0
Помимо этого, и того, что говорили другие люди, вы также можете попробовать использовать Бином непосредственно, возможно, с каким-нибудь Стирлингом.
(*) Некоторые более новые утверждения о неравенстве Слуда исключают некоторые из этих условий; Я воспроизвел один в статье Слуда.
источник
Теорема де Муавра-Лапласа показывает, что переменные типапосле соответствующей нормализации и при определенных условиях сойдутся в распределении к нормальному распределению. Этого достаточно, если вы хотите постоянные нижние границы.|T∩S1|
Для нижних границ, таких как , вам понадобится немного более тонкий инструмент. Вот одно упоминание, о котором я знаю (но только случайно - у меня никогда не было возможности использовать такое неравенство самостоятельно). Некоторые явные нижние оценки вероятностей хвостов биномиальных распределений приведены в виде теоремы 1.5 книги Случайные графы Белы Боллобаса, Кембридж, 2-е издание, где даны дополнительные ссылки на Введение в вероятность и ее применения Феллера и Основы вероятности Рени.n−c
источник
Обобщенная теорема Литтлвуда-Оффорда не совсем то, что вам нужно, но она дает то, что я считаю «обратной черновской» границей, показывая, что сумма случайных величин вряд ли попадет в небольшой диапазон вокруг какого-либо конкретного значения (включая ожидание). Возможно, это будет полезно.
Формально теорема состоит в следующем.
Обобщенная теорема Литтлвуда-Оффорда : Пусть и - такие действительные числа, что для и пусть - независимые случайные величины со значениями ноль и единица. Предположим, что для для всех . Тогда для любого , где - константа, зависящая только от .a1,…,an s>0 |ai|≥s 1≤i≤n X1,…,Xn 0<p≤12 p≤Pr[Xi=0]≤1−p 1≤i≤n r∈R
источник
Показатель степени в стандартной границе Черноффа, как это указано в Википедии, является жестким для 0/1-значных случайных величин. Пусть а - последовательность независимых случайных величин, такая что для каждого , и . Тогда для любого ,0<p<1 X1,X2,… i Pr[Xi=1]=p Pr[Xi=0]=1−p ε>0
Здесь , что является дивергенцией Кульбака-Лейблера между случайными значениями Бернулли переменные с параметрами и .D(x∥y)=xlog2(x/y)+(1−x)log2((1−x)/(1−y)) x y
Как уже упоминалось, верхняя граница в неравенстве выше доказана в Википедии ( https://en.wikipedia.org/wiki/Chernoff_bound ) под названием «Теорема Чернова-Хеффдинга, аддитивная форма». Нижняя граница может быть доказана с помощью, например, «метода типов». См. Лемму II.2 в [1]. Кроме того, это описано в классическом учебнике по теории информации, написанном Кавером и Томасом.
[1] Имре Цишар: метод типов. IEEE Труды по теории информации (1998). http://dx.doi.org/10.1109/18.720546
источник