Вероятностные неравенства

37

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

Моя задача состоит в том, чтобы найти экспоненциальную верхнюю границу вероятности того, что сумма неограниченных случайных величин iid, которые на самом деле являются умножением двух iid Gaussian, превышает некоторое определенное значение, то есть , где , и генерируются из .Pr[Xϵσ2N]exp(?)X=i=1NwiviwiviN(0,σ)

Я попытался использовать границу Черноффа, используя функцию генерирования момента (MGF), полученная граница определяется как:

Pr[Xϵσ2N]minsexp(sϵσ2N)gX(s)=exp(N2(1+4ϵ21+log(1+4ϵ21)log(2ϵ2)))

где gX(s)=(11σ4s2)N2 является ФМГ из X . Но граница не такая уж тесная. Основная проблема в моей задаче состоит в том, что случайные величины не ограничены, и, к сожалению, я не могу использовать границу неравенства Хеффдинга.

Я буду счастлив, если вы поможете мне найти какую-то тесную экспоненциальную границу.

Farzad
источник
3
Звучит как проблема, связанная со сжатием. Посмотрите заметки Р. Вершинина о неасимптотической теории случайных матриц, в частности, оценки того, что он называет субэкспоненциальными случайными величинами. Это поможет вам начать. Если вам нужно больше указателей, дайте нам знать, и я постараюсь опубликовать дополнительную информацию.
кардинал
1
Есть по крайней мере пара связанных вопросов и ответов по этой теме на math.SE (отказ от ответственности: включая тот, в котором я принимал участие).
кардинал
1
Продукт wivi имеет «нормальный продукт». Я полагаю, что среднее значение этого продукта равно нулю, а дисперсия σ4 где σ2 - дисперсия wi и vi . Для N largeish, вы можете использовать центральную предельную теорему , чтобы получить приблизительную norality из X . Если вы можете вычислить перекос нормального распределения продуктов, я полагаю, что вы можете применить теорему Берри-Эссеена, чтобы ограничить скорость сходимости CDF.
Шаббычеф
1
@shabbychef, Берри-Эссеено имеет довольно медленную сходимость, так как это равномерная оценку по классу всех функций распределения . F
кардинал
4
@DilipSarwate: Извините, что только сейчас вижу ваш комментарий. Я думаю, что вам может быть интересна следующая небольшая статья, которую я также пару раз связывал по математике. TK Phillips и R. Nelson (1995) . Момент более жесткий, чем у Черноффа для положительного хвоста. вероятности , Американский статистик , том 42, нет. 2. 175-178.
кардинал

Ответы:

1

Используя черновскую границу, которую вы предложили для некоторого который будет указан позже, где выполняется второе неравенство благодаря для любого . Теперь возьмите и , правая часть становится что дает для любого .s1/(2σ2)

P[X>t]exp(st)exp((N/2)log(1σ4s2))exp(st+σ4s2N)
log(1x)2xx(0,1/2)t=ϵσ2Ns=t/(2σ4N)exp(t2/(4σ4N)=exp(ϵ2N/4)
P[X>ϵσ2N]exp(ϵ2N/4).
ϵ(0,1)

Другой путь заключается в прямом применении неравенств концентрации, таких как неравенство Хансона-Райта, или неравенств концентрации для гауссовского хаоса порядка 2, который охватывает интересующую вас случайную величину.

Более простой подход без использования функции, генерирующей момент

Для простоты возьмем (в противном случае можно изменить масштаб, разделив на ).σ=1σ2

Запись и . Вы запрашиваете верхние границы для .v=(v1,...,vn)Tw=(w1,...,wn)TP(vTw>ϵN)

Пусть, Тогда в зависимости от и не зависит от с с степенями свободы.Z=wTv/vZN(0,1)v,wv2Zχ2n

По стандартным оценкам стандартных нормальных и случайных величин Объединение с объединенной границей дает верхнюю границу для вида .χ2

P(|Z|>ϵn/2)2exp(ϵ2n/4),P(v>2n)exp(n(21)2/2).
P(vTw>ϵN)2exp(ϵ2n/4)+exp(n(21)2/2)

jlewk
источник
0

Полученная граница имеет порядок как . Я не думаю , что вы можете сделать гораздо лучше для общего . На странице Википедии о переменных продукта распределение имеет вид где - модифицированная функция Бесселя. Из (10.25.3) в списке функций DLMF , , так что для достаточно больших который не даст вам субгауссову оценку.eϵϵϵwiviK0(z)/πK0K0(t)et/txP(wivi>x)xet/tdt

BookYourLuck
источник