Экспоненциальная верхняя граница

12

Предположим, у нас есть случайные величины IID с распределением . Мы будем наблюдать образец 'ы следующим образом: пусть быть независимыми случайные величины, предположим , что все х и «s являются независимыми и определяют размер выборки . В «s показывают , какой из » с в образце, и мы хотим , чтобы изучить часть успехов в образце , определяемом X1,,XnBer(θ)XiY1,,YnBer(1/2)XiYiN=i=1nYiYiXiϵ>0Пр

Z={1Ni=1nXiYiifN>0,0ifN=0.
Для мы хотим найти верхнюю границу для которая экспоненциально убывает с . Неравенство Хеффдинга не применяется немедленно из-за зависимостей между переменными.ϵ>0 nPr(Zθ+ϵ)n
Zen
источник
1
Пусть . (i) Разве не зависит от ? (ii) не ? ... В результате, мне не ясно, что не является «суммой независимых случайных величин»ZiZjiZ=ZiZZi=1NXiYiZiZjiZ=ZiZ
Glen_b -Reinstate Monica
Ах, хорошая мысль. Я думал о , а не о . Но вы не можете вместо этого написать и позволить ? То есть сумма по всем случаям, независимо от того, равен ли 1 или 0. ... нет, это не работает. Числитель такой же, но знаменатель другой. N Z i = 1nNZ= n i = 1 ZiYZi=1nXiYiZ=i=1nZiY
Glen_b
Это дает меньше доли успехов в выборке, что представляет собой интерес к задаче, потому что , так как . N N(1/n)i=1nXiYi(1/N)i=1nXiYiNn
Дзен
1
Да, именно поэтому я закончил с «нет, это не работает». Существуют неравенства, которые применяются к независимому случаю, например, некоторые из неравенств Бернштейна (см. Четвертый пункт), и существует ряд неравенств, применимых к мартингалам (хотя я не знаю, будут ли они применяться здесь).
Glen_b
1
Я посмотрю, а также попробую найти связь с результатами мартингейла. Оценка для очень проста ( ) что заманчиво связать это с используя какое-то условие. Р г ( U ≥ & thetas ; / 2 + ε ) ехр ( - 2 п ε 2 ) ZU=(1/n)i=1nXiYiPr(Uθ/2+ϵ)exp(2nϵ2)Z
Дзен

Ответы:

16

Мы можем установить прямую связь с неравенством Хеффдинга .

Обратите внимание, что у нас есть

{Z>θ+ϵ}={iXiYi>(θ+ϵ)iYi}={i(Xiθϵ)Yi>0}.

Установите так, чтобы были iid, и простым применением неравенства Хеффдинга (поскольку и поэтому принимают значения в интервале первого размера).Z i E Z i = 0 P ( Z > θ + ϵ ) = P ( i Z i > n ϵ / 2 )e - n ϵ 2 / 2Zi=(Xiθϵ)Yi+ϵ/2ZiEZi=0Z i[ - θ - ϵ / 2 , 1 - θ - ϵ / 2 ]

P(Z>θ+ϵ)=P(iZi>nϵ/2)enϵ2/2,
Zi[θϵ/2,1θϵ/2]

За последние несколько лет появилась обширная и увлекательная литература, в частности, по темам, связанным с теорией случайных матриц, с различными практическими приложениями. Если вы заинтересованы в таких вещах, я настоятельно рекомендую:

Р. Вершинин, Введение в неасимптотический анализ случайных матриц , глава 5 «Сжатое зондирование, теория и приложения». Под редакцией Ю. Эльдара и Г. Кутыниока. Издательство Кембриджского университета, 2012.

Я думаю, что экспозиция ясна и дает очень хороший способ быстро привыкнуть к литературе.

кардинальный
источник
1
Поскольку включает в свое определение, у меня сложилось впечатление, что (граница не меняется). ϵ / 2 Z i[ - θ - ϵ / 2 , 1 - θ - ϵ / 2 ]Ziϵ/2Zi[θϵ/2,1θϵ/2]
Алекос Пападопулос
1
Уважаемый @Zen: Обратите внимание, что тщательный учет случая позволит вам заменить строгое неравенство на везде без изменения окончательной границы. > N=0>
кардинал
Уважаемый @cardinal: я перефразировал вопрос, потому что на самом деле является (слегка) смещенной оценкой , поскольку . thetas ; E [ Z ] = E [ I { N = 0 } Z ] + Е [ Я { Н > 0 } Z ] = ( 1 - 1 / 2 л )ZθE[Z]=E[I{N=0}Z]+E[I{N>0}Z]=(11/2n)θ
Дзен
6

Детали, чтобы заботиться о случае . N=0

{Zθ+ϵ}=({Zθ+ϵ}{N=0})({Zθ+ϵ}{N>0})=({0θ+ϵ}{N=0})({Zθ+ϵ}{N>0})=({N=0})({Zθ+ϵ}{N>0})={i=1nXiYi(θ+ϵ)i=1nYi}{N>0}{i=1nXiYi(θ+ϵ)i=1nYi}={i=1n(Xiθϵ)Yi0}={i=1n((Xiθϵ)Yi+ϵ/2)nϵ/2}.

Для Алекоса.

E[i=1nWi]=E[I{i=1nYi=0}i=1nWi]+E[I{i=1nYi>0}i=1nWi]=E[I{i=1nYi>0}i=1nYii=1nYi]=E[I{i=1nYi>0}]=11/2n.
Zen
источник
5

Этот ответ продолжает мутировать. Текущая версия не имеет отношения к обсуждению, которое я имел с @cardinal в комментариях (хотя именно благодаря этому обсуждению я, к счастью, понял, что подход к созданию условий ни к чему не привел).

Для этой попытки я буду использовать другую часть оригинальной статьи Хеффдинга 1963 года , а именно раздел 5 «Суммы зависимых случайных величин».

Установите

WiYii=1nYi,i=1nYi0,i=1nWi=1,n2

в то время как мы устанавливаем если .n i = 1 Y i = 0Wi=0i=1nYi=0

Тогда у нас есть переменная

Zn=i=1nWiXi,E(Zn)μn

Нас интересует вероятность

Pr(Znμn+ϵ),ϵ<1μn

Как и для многих других неравенств, Хоффдинг начинает свои рассуждения, отмечая, что и это

Pr(Znμn+ϵ)=E[1{Znμnϵ0}]

1{Znμnϵ0}exp{h(Znμnϵ)},h>0

Для случая зависимых переменных, в качестве Хеффдинга мы используем тот факт, что и вызываем неравенство Дженсена для (выпуклой) экспоненциальной функции, чтобы записатьi=1nWi=1

ehZn=exp{h(i=1nWiXi)}i=1nWiehXi

и связывая результаты, чтобы прийти к

Pr(Znμn+ϵ)eh(μn+ϵ)E[i=1nWiehXi]

Сосредоточив внимание на нашем случае, поскольку и независимы, ожидаемые значения могут быть разделены,WiXi

Pr(Znμn+ϵ)eh(μn+ϵ)i=1nE(Wi)E(ehXi)

В нашем случае - это Бернулли с параметром , а - их общая функция, генерирующая моменты в , . ТакXiθE[ehXi]hE[ehXi]=1θ+θeh

Pr(Znμn+ϵ)eh(μn+ϵ)(1θ+θeh)i=1nE(Wi)

Минимизируя RHS по отношению к , получаемh

eh=(1θ)(μn+ϵ)θ(1μnϵ)

Включив его в неравенство и манипулируя, мы получаем

Pr(Znμn+ϵ)(θμn+ϵ)μn+ϵ(1θ1μnϵ)1μnϵi=1nE(Wi)

пока

Pr(Znθ+ϵ)(θθ+ϵ)θ+ϵ(1θ1θϵ)1θϵi=1nE(Wi)

Хоффдинг показывает, что

(θθ+ϵ)θ+ϵ(1θ1θϵ)1θϵe2ϵ2

Предоставлено ОП (спасибо, я немного истощился ...)

i=1nE(Wi)=11/2n

Итак, наконец, подход «зависимых переменных» дает нам

Pr(Znθ+ϵ)(112n)e2ϵ2BD

Давайте сравним это с оценкой Кардинала, основанной на преобразовании «независимости», . Для того, чтобы наши были более тесными, нам нужноBI

BD=(112n)e2ϵ2enϵ2/2=BI

2n12nexp{(4n2)ϵ2}

Таким образом, для у нас есть . Для довольно быстро становится плотнее, чем но для очень маленьких , в то время как даже это маленькое "окно" быстро сходится к нулю. Например, для , если , то является более . Так что в целом оценка кардинала более полезна. B DB I n 5 B I B D ϵ n = 12 ϵ 0,008 B In4BDBIn5BIBDϵn=12ϵ0.008BI

КОММЕНТАРИЙ
Чтобы избежать вводящих в заблуждение впечатлений относительно оригинальной статьи Хоффдинга, я должен упомянуть, что Хеффдинг рассматривает случай детерминированной выпуклой комбинации зависимых случайных величин. В частности, его являются числами, а не случайными переменными, в то время как каждый является суммой независимых случайных величин, в то время как между может существовать зависимость . Затем он рассматривает различные «U-статистики», которые могут быть представлены таким образом.X i X iWiXiXi

Алекос Пападопулос
источник
Alecos: (посмотрите на вывод в конце моего ответа). Ваша граница не уменьшается экспоненциально с как у кардинала. пE[W1]=(11/2n)/nn
Дзен
@Zen Действительно (на самом деле он увеличивается с размером выборки, хотя и ограниченно), поэтому граница Кардинала более полезна для большинства размеров выборки.
Алекос Пападопулос