Понимание доказательства леммы, используемой в неравенстве Хеффдинга

11

Я изучаю лекционные заметки Ларри Вассермана по статистике, в которых в качестве основного текста используются Казелла и Бергер. Я работаю над его комплектом лекций 2 и застрял в выводе леммы, используемой в неравенстве Хеффдинга (стр. 2-3). Я воспроизводлю доказательства в примечаниях ниже, и после доказательства я укажу, где я застрял.


лемма

Предположим, что и что . Тогда .х б Е ( е т Х ) е т 2 ( б - ) 2 / 8E(X)=0aXbE(etX)et2(ba)2/8

доказательство

Поскольку , мы можем записать как выпуклую комбинацию и , а именно где . По выпуклости функции имеемaXbXabX=αb+(1α)aα=Xabayety

etXαetb+(1α)eta=Xabaetb+bXbaeta

Возьмите ожидания обеих сторон и используйте факт чтобы получитьE(X)=0

E(etX)abaetb+bbaeta=eg(u)

где , и . Обратите внимание, что . Также для всех u> 0 .g ( u ) = - γ u + log ( 1 - γ + γ e u ) γ = - a / ( b - a ) g ( 0 ) = gu=t(ba)g(u)=γu+log(1γ+γeu)γ=a/(ba)g(0)=g(0)=0g(u)1/4u>0

По теореме Тейлора существует ε(0,u) такой, что g(u)=g(0)+ug(0)+u22g(ε)=u22g(ε)u28=t2(ba)28

Следовательно , E(etX)eg(u)et2(ba)28 .


Я мог бы следовать доказательствам до

E(etX)abaetb+bbaeta=eg(u) но я не могу понять, как получить .u,g(u),γ

Ананд
источник
3
Интересно, что максимальное значение равно и, таким образом, результат эффективно равен который выглядит слишком знакомым, чтобы возникнуть из явного совпадения. Я подозреваю, что может быть другой, возможно более простой, способ получить результат с помощью вероятностного аргумента. var(X)σmax2=(ba)2/4
E[etX]eσmax2t2/2
Dilip Sarwate
@DilipSarwate Насколько я понимаю, максимальная дисперсия возникает для равномерной случайной величины . Дисперсия равна . Не могли бы вы объяснить, как вы получили ? XU(a,b)XVar(X)=(ba)212(ba)24
Ананд
Сосредоточив массу на конечных точках ...
Элвис
@DilipSarwate Я добавил несколько комментариев в доказательство, которые могут прояснить, почему наихудший случай - это максимальная дисперсия.
Элвис
1
@DilipSarwate - см. Лемму 1 и упражнение 1 здесь: terrytao.wordpress.com/2010/01/03/… . Кажется, есть более простой вывод, основанный на неравенстве Дженсена и расширении Тейлора. Все же детали этого неясны для меня. Возможно, кто-то может понять это. (вывод из (9) в (10) и упражнение 1)
Лев

Ответы:

17

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

abaetb+bbaeta
u=t(ba)eu28

Помогал опыт, вы будете знать , что лучше выбрать , чтобы записать его в виде . Тогда приводит к с .eg(u)

eg(u)=abaetb+bbaeta
g(u)=log(abaetb+bbaeta)=log(eta(abaet(ba)+bba))=ta+log(γeu+(1γ))=γu+log(γeu+(1γ)),
γ=aba

Это то, о чем вы просили?

Изменить: несколько комментариев на доказательство

  1. Первый трюк заслуживает внимательного рассмотрения: если - выпуклая функция и - центрированная случайная величина, то где - это дискретная переменная, определяемая Как следствие, вы получите , что является центрированная переменная с поддержкой в которая имеет наибольшую дисперсию: Обратите внимание, что если мы фиксируем ширину опорыϕaXb
    E(ϕ(X))abaϕ(b)+bbaϕ(a)=E(ϕ(X0)),
    X0
    P(X0=a)=bbaP(X0=b)=aba.
    X0[a,b]
    Var(X)=E(X2)E(X02)=ba2ab2ba=ab.
    (ba), это меньше, чем как говорит Дилип в комментариях, потому что ; оценка достигается для .(ba)24(ba)2+4ab0a=b
  2. Теперь перейдем к нашей проблеме. Почему можно получить оценку в зависимости только от ? Интуитивно понятно, что это всего лишь вопрос масштабирования : если у вас есть граница для случая , тогда общая оценка можно получить, взяв . Теперь подумайте о наборе центрированных переменных с поддержкой ширины 1: свободы не так много, поэтому должна существовать граница типа . Другой подход заключается в том, чтобы просто сказать, что согласно приведенной выше лемме о , то в более общем смысле , которое зависит только от иu=t(ba)XE(etX)s(t)ba=1s(t(ba))s(t)

    E(ϕ(X))E(ϕ(tX))E(ϕ(tX0))uγ : если вы исправите и , и пусть изменяются, то существует только одна степень свободы, и , , . Мы получаем Вы просто должны найти связанные с участием только .u=u0=t0(b0a0)γ=γ0=a0b0a0t,a,bt=t0αa=αa0b=αa0

    abaϕ(tb)+bbaϕ(ta)=a0b0a0ϕ(tb0)+b0b0a0ϕ(a0).
    u
  3. Теперь мы уверены, что это можно сделать, это должно быть намного проще! Вам не обязательно думать , чтобы начать с. Дело в том, что вы должны написать все как функцию от и . Сначала обратите внимание, что , , и . Тогда Теперь мы находимся в частном случае ... I думаю, что вы можете закончить.guγ

    γ=aba1γ=bbaat=γubt=(1γ)u

    E(ϕ(tX))abaϕ(tb)+bbaϕ(ta)=γϕ((1γ)u)+(1γ)ϕ(γu)


    ϕ=exp

Надеюсь, я прояснил это немного.

Элвис
источник
это именно то, что я искал. Большое спасибо.
Ананд
1
@ И я знаю, что совету трудно следовать, однако я думаю, что не стоит начинать с технических деталей, а скорее попытаться понять, почему такая граница может существовать ... тогда доказательство должно появиться легче. Я попытался показать вам, почему во второй части добавил это утро (вам нужно поспать на вопросе, подобном этому - по крайней мере, мне нужно). Я думаю, это ужасно, что такого рода интуиция не появляется в большинстве учебников ... даже если вы получаете техническую часть, пока у вас нет идей, все выглядит волшебно. Спасибо вам и CrossV за предоставленную мне возможность подумать об этом подробнее!
Элвис
1
Вау! +1 за редактирование. Спасибо. Но было бы неплохо, если бы можно было получить что-то вроде
E[etX]eE[t2X2/2]=e(t2/2)E[X2]=e(t2/2)var(X)et2σmax2/2?
Дилип Сарвате,
@ Элвис Спасибо за совет и за то, что нашли время записать интуитивную часть. Мне нужно потратить некоторое время, чтобы понять это!
Ананд
1
@ Элвис Что касается интуиции, я хочу уточнить свое понимание. Чтобы получить более четкие границы, нужны более высокие моменты. Марков использует первый момент, Чебышев - второй, а Хоффдинг использует мгф. Это верно? Если кто-то может расширить и уточнить эту часть, это было бы здорово.
Ананд