Сумма независимых экспоненциальных случайных величин

12

Можем ли мы доказать точный результат концентрации на сумме независимых экспоненциальных случайных величин, т.е. пусть - независимые случайные величины, такие что . Пусть . Можем ли мы доказать оценки вида . Это следует непосредственно, если мы используем дисперсионную форму границ Чернова и, следовательно, я считаю, что это правда, но границы, которые я читаю, требуют ограниченности или имеют некоторую зависимость от ограниченности переменных. Может ли кто-нибудь указать мне на доказательство вышеизложенного? X1,XrPr(Xi<x)=1ex/λiZ=XiPr(|ZμZ|>t)<et2/(λi)2

кляча
источник
просто следуйте доказательству Чернова: легко связать экспоненциальный момент экспоненциальных случайных величин.
Сашо Николов
Я попытался повторить доказательство Чернова. Я сделал это для более простого случая, когда все λi=λ . Я могу получить вид отношений, который я ищу, при мягком условии . Возникает ли такое состояние естественным образом или это связано с моим не очень хорошим решением? t<nλ
NAg
3
Проверьте лемму 2.8 здесь eprint.iacr.org/2010/076.pdf
Сашо Николов
Да, это имеет смысл. Даже в их лемме они имеют условие на быть достаточно мал. Хорошо, тогда мое решение кажется правильным. Большое спасибо за ссылки и предложение. t
NAg
1
Pr[Xi<x]=eλixPr [ X i < x ] = 1 - e - λ i x λ - 2 ixPr[Xi<x]=1eλixλi2

Ответы:

7

Для конкретности, скажем , что ПДФ с.в. являетсяXi

p(Xi=x)=12λieλi|x|.

Это распределение Лапласа или двойное экспоненциальное распределение. Его дисперсия . Cdf является2λi2

Pr[Xix]=112eλix
для .x0

Генерирующий момент функция являетсяXi

E euXi=11u2/λi2,
| ты| <λiX=iXiσ2=2iλ - 2 i для . Используя этот факт и метод экспоненциального момента, который является стандартным в доказательстве границ Чернова, вы получите, что для и выполняется следующее неравенство|u|<λiX=iXiσ2=2iλi2

Pr[X>tσ]<et2/4,
т 2 σ мин я λ я пока . Вы можете найти подробный вывод в доказательстве леммы 2.8 этой статьи .t2σminiλi

Сашо Николов
источник
Большое спасибо за ответ. Однако в моем приложении не обязательно верно, что . Однако можно ожидать еще большей концентрации в случае . Мы можем получить такой результат, если не будем использовать приближение которое ограничивает диапазон в доказательстве, но анализ этого становится неуправляемым в случае различных . Есть предложения на этот счет? t>t2σminiλi1/(1-x)e c x tt>2σminiλi1/(1x)ecxtλis
NAg
это будет энергичное размахивание руками, но я ожидаю, что такие большие значения наиболее вероятны, когда только небольшое число превышает медианумного. но двойные экспоненциальные переменные имеют более тяжелый хвост, чем гауссианы, и небольшое количество из них не может сосредоточиться так плотноX я | X я |XXi|Xi|
Сашо Николов
2
Я понимаю, что то, что я написал выше, не ясно: я ожидаю, что выход в хвосте выглядит как хвост другого rv который является суммой небольшого числа двойной экспоненциальной rv. Хвост такого не должен быть к югу от гауссовой. X X XXX
Сашо Николов
3

Для распределения Лапласа, если вы используете границу Бернулли, вы можете написать

σ2=2Σяλ - 2 я

EeuiXi=i11u2/λi211u2σ2/2,
где . Тогда классический метод Черноффа даетσ2=2iλi2

Pr[iXitσ]1+1+2t22e11+2t2{(et/2+1)e2tet2/2+t4/8.

Обратите внимание, что эти границы справедливы для неограниченных значений и . Границы справа показывают два возможных режима. Для малых значений мы получаем «нормальную» концентрацию , в то время как для больших значений мы получаем , что также является CDF для одна переменная Лапласа.λ я т е - т +2 / +2 т е - tλitet2/2te2t

связаны позволяет интерполировать между этими двумя ситуациями, но я подозреваю , что почти во всех случаях один будет твердо в любом большом или малым лагеря. тт11+2t2tt

Для экспоненциального распределения те же методы дают нам где . Следовательно, Таким образом, вы по-прежнему выглядите слегка нормально, но с а не с как мы могли бы надеяться. Я не знаю, возможно ли получить границу с точки зрения дисперсии. Вы можете попытаться изучить , но с ним не так легко работать.EeuiXi11uμμ=i1/λi

Pr[(iXi)μtμ](t+1)etet2/2+t3/3.
tμtσEeu(Xiμ)2
Томас Але
источник
У меня нет времени, чтобы проработать детали, но я на 99,9% уверен, что можно получить границу для экспоненциально распределенных случайных величин, которая зависит от дисперсии. Ваша ограниченная функция генерирования момента выглядит чрезмерно свободной.
Уоррен Шуди
@ Уоррен Шуди, какой у тебя подход?
Томас Але
Я вижу два очевидных подхода: 1. Вторая граница, перечисленная на en.wikipedia.org/wiki/…, выглядит так, как будто она должна работать. 2. Найти более плотную границу для функции, генерирующей момент.
Уоррен Шуди
@WarrenSchudy Граница Бернштейна дает , но только для . Я полагаю, это похоже на ответ Сашо. т сг мин я λ я / 2Pr[iXitσ]et2/2tσminiλi/2
Томас Але
Это неизбежно, что границы в стиле Гаусса прекратятся в какой-то момент. Даже одна экспоненциально распределенная случайная величина в конечном итоге имеет более толстые хвосты, чем любая гауссовская.
Уоррен Шуди