Предположим, у нас есть случайные величины IID с распределением . Мы будем наблюдать образец 'ы следующим образом: пусть быть независимыми случайные величины, предположим , что все х и «s являются независимыми и определяют размер выборки . В «s показывают , какой из » с в образце, и мы хотим , чтобы изучить часть успехов в образце , определяемом ϵ>0Пр
Для мы хотим найти верхнюю границу для которая экспоненциально убывает с . Неравенство Хеффдинга не применяется немедленно из-за зависимостей между переменными. n
Ответы:
Мы можем установить прямую связь с неравенством Хеффдинга .
Обратите внимание, что у нас есть
Установите так, чтобы были iid, и простым применением неравенства Хеффдинга (поскольку и поэтому принимают значения в интервале первого размера).Z i E Z i = 0 P ( Z > θ + ϵ ) = P ( ∑ i Z i > n ϵ / 2 ) ≤ e - n ϵ 2 / 2Zя= ( Xя- θ - ϵ ) Yя+ ϵ / 2 Zя Е Zя= 0 Z i ∈ [ - θ - ϵ / 2 , 1 - θ - ϵ / 2 ]
За последние несколько лет появилась обширная и увлекательная литература, в частности, по темам, связанным с теорией случайных матриц, с различными практическими приложениями. Если вы заинтересованы в таких вещах, я настоятельно рекомендую:
Я думаю, что экспозиция ясна и дает очень хороший способ быстро привыкнуть к литературе.
источник
Детали, чтобы заботиться о случае .N=0
Для Алекоса.
источник
Этот ответ продолжает мутировать. Текущая версия не имеет отношения к обсуждению, которое я имел с @cardinal в комментариях (хотя именно благодаря этому обсуждению я, к счастью, понял, что подход к созданию условий ни к чему не привел).
Для этой попытки я буду использовать другую часть оригинальной статьи Хеффдинга 1963 года , а именно раздел 5 «Суммы зависимых случайных величин».
Установите
в то время как мы устанавливаем если .∑ n i = 1 Y i = 0Wi=0 ∑ni=1Yi=0
Тогда у нас есть переменная
Нас интересует вероятность
Как и для многих других неравенств, Хоффдинг начинает свои рассуждения, отмечая, что и это
Для случая зависимых переменных, в качестве Хеффдинга мы используем тот факт, что и вызываем неравенство Дженсена для (выпуклой) экспоненциальной функции, чтобы записать∑ni=1Wi=1
и связывая результаты, чтобы прийти к
Сосредоточив внимание на нашем случае, поскольку и независимы, ожидаемые значения могут быть разделены,Wi Xi
В нашем случае - это Бернулли с параметром , а - их общая функция, генерирующая моменты в , . ТакXi θ E[ehXi] h E[ehXi]=1−θ+θeh
Минимизируя RHS по отношению к , получаемh
Включив его в неравенство и манипулируя, мы получаем
пока
Хоффдинг показывает, что
Предоставлено ОП (спасибо, я немного истощился ...)
Итак, наконец, подход «зависимых переменных» дает нам
Давайте сравним это с оценкой Кардинала, основанной на преобразовании «независимости», . Для того, чтобы наши были более тесными, нам нужноBI
Таким образом, для у нас есть . Для довольно быстро становится плотнее, чем но для очень маленьких , в то время как даже это маленькое "окно" быстро сходится к нулю. Например, для , если , то является более . Так что в целом оценка кардинала более полезна. B D ≤ B I n ≥ 5 B I B D ϵ n = 12 ϵ ≥ 0,008 B In≤4 BD≤BI n≥5 BI BD ϵ n=12 ϵ≥0.008 BI
КОММЕНТАРИЙWi Xi Xi
Чтобы избежать вводящих в заблуждение впечатлений относительно оригинальной статьи Хоффдинга, я должен упомянуть, что Хеффдинг рассматривает случай детерминированной выпуклой комбинации зависимых случайных величин. В частности, его являются числами, а не случайными переменными, в то время как каждый является суммой независимых случайных величин, в то время как между может существовать зависимость . Затем он рассматривает различные «U-статистики», которые могут быть представлены таким образом.X i X i
источник