Zrozumienie dowodu lematu stosowanego w nierówności Hoeffdinga

Studiuję notatki do wykładu Larry'ego Wassermana na temat statystyki, w których Casella i Berger są głównym tekstem. Pracuję nad jego notatkami z wykładu, zestawem 2 i utknąłem w wyprowadzaniu lematu stosowanego w nierówności Hoeffdinga (s. 2-3). Powtarzam dowód w uwagach poniżej, a po dowodzie wskażę, gdzie utknąłem.

Lemat

Załóżmy, że i że . Następnie .$\mathbb{E}(X) = 0$$a \le X \le b$$\mathbb{E}(e^{tX}) \le e^{t^2 (b-a)^2/8}$

Dowód

Ponieważ , możemy napisać jako wypukłą kombinację i , a mianowicie where . Wypukłość funkcji mamy$a \le X \le b$$X$$a$$b$$X = \alpha b + (1 - \alpha) a$$\alpha = \frac{X-a}{b-a}$$y \to e^{ty}$

$e^{tX} \le \alpha e^{tb} + (1 - \alpha) e^{ta} = \frac{X-a}{b-a} e^{tb} + \frac{b-X}{b-a} e^{ta}$

Weź oczekiwania obu stron i użyj faktu aby uzyskać$\mathbb{E}(X) = 0$

$\mathbb{E}(e^{tX}) \le \frac{-a}{b-a} e^{tb} + \frac{b}{b-a} e^{ta} = e^{g(u)}$

gdzie , i . Zauważ, że . Również dla wszystkich u> 0 .$u = t(b-a)$$g(u) = -\gamma u + \log(1-\gamma + \gamma e^{u})$$\gamma = -a /(b-a)$$g(0) = g^{'}(0) = 0$$g^{''}(u) \le 1/4$$u > 0$

Według twierdzenia Taylora istnieje $\varepsilon \in (0, u)$ taki, że $g(u) = g(0) + u g^{'}(0) + \frac{u^2}{2} g^{''}(\varepsilon) = \frac{u^2}{2} g^{''}(\varepsilon) \le \frac{u^2}{8} = \frac{t^2(b-a)^2}{8}$

Stąd $\mathbb{E}(e^{tX}) \le e^{g(u)} \le e^{\frac{t^2(b-a)^2}{8}}$ .

Mogę śledzić dowód do

$\mathbb{E}(e^{tX}) \le \frac{-a}{b-a} e^{tb} + \frac{b}{b-a} e^{ta} = e^{g(u)}$ ale nie jestem w stanie dowiedzieć się, jak uzyskać .$u, g(u), \gamma$

Nie jestem pewien, czy poprawnie zrozumiałem twoje pytanie. Spróbuję odpowiedzieć: spróbuj napisać w funkcji : this jest naturalne, ponieważ chcesz powiązać w .

Dzięki doświadczeniu dowiesz się , że lepiej jest napisać go w formie . Następnie prowadzi do with .$e^{g(u)}$

Czy o to prosiłeś?

Edycja: kilka komentarzy do dowodu

1. Na pierwszą sztuczkę zasługuje się uważnie: jeśli jest funkcją wypukłą, a jest wyśrodkowaną zmienną losową, to gdzie jest zmienną dyskretną zdefiniowaną przez W rezultacie otrzymujesz, że jest środkowa zmienna z obsługą w która ma największą wariancję: Pamiętaj, że jeśli naprawimy szerokość podpory$\phi$$a\le X\le b$ $$\mathbb{E}(\phi(X)) \le -{a\over b-a} \phi(b) + {b \over b-a} \phi(a) = \mathbb{E}(\phi(X_0)),$$ $X_0$ $$\begin{align*} \mathbb P(X_0=a) &= {b \over b-a}\\ \mathbb P(X_0=b) &= -{a \over b-a}.\end{align*}$$ $X_0$$[a,b]$ $$\mathsf{Var} (X) = \mathbb{E}(X^2) \le \mathbb{E}(X_0^2) = {ba^2 - ab^2 \over b-a } = - ab.$$ $(b-a)$, jest to mniej niż jak mówi Dilip w komentarzach, dzieje się tak, ponieważ ; granica jest osiągana dla .$(b-a)^2\over 4$$(b-a)^2 + 4ab \ge 0$$a=-b$

2. Teraz przejdź do naszego problemu. Dlaczego możliwe jest uzyskanie granicy zależnej tylko od ? Intuicyjnie jest to tylko kwestia przeskalowania : jeśli masz ograniczony dla przypadku , to ogólne ograniczenie można uzyskać biorąc . Zastanówmy się teraz nad zestawem zmiennych wyśrodkowanych ze wsparciem szerokości 1: nie ma tak dużo swobody, więc powinna istnieć powiązana wartość . Innym podejściem jest powiedzenie po prostu, że z powyższego lematu na , a bardziej ogólnie , który zależy tylko od i$u = t(b-a)$$X$$\mathbb{E}\left( e^{tX} \right) \le s(t)$$b-a=1$$s( t(b-a) )$$s(t)$
   
   $\mathbb{E}(\phi(X))$$\mathbb{E}(\phi(tX)) \le \mathbb{E}(\phi(tX_0))$$u$$\gamma$ : jeśli naprawisz i i pozwól że różnią, jest tylko jeden stopień swobody, i , , . Otrzymujemy Po prostu trzeba znaleźć związany z udziałem tylko .$u = u_0 = t_0 (b_0 - a_0)$$\gamma = \gamma_0 = - {a_0 \over b_0-a_0}$$t, a, b$$t = {t_0 \over \alpha}$$a = \alpha a_0$$b = \alpha a_0$

   $$-{a\over b-a} \phi(tb) + {b \over b-a} \phi(ta) = -{a_0\over b_0-a_0} \phi(tb_0) + {b_0 \over b_0-a_0} \phi(a_0).$$ $u$

3. Teraz jesteśmy przekonani, że da się to zrobić, musi być znacznie łatwiej! Nie koniecznie pomyśleć na początku. Chodzi o to, że musisz napisać wszystko jako funkcję i . Najpierw zauważ, że , , and . Następnie Teraz jesteśmy w szczególnym przypadku ... I myślę, że możesz skończyć.$g$$u$$\gamma$
   
   $\gamma = -{a\over b-a}$$1 -\gamma = {b\over b-a}$$at = -\gamma u$$bt = (1-\gamma)u$

   $$\begin{align*} \mathbb{E}(\phi(tX)) \le &-{a\over b-a} \phi(tb) + {b \over b-a} \phi(ta) \\ = & \gamma \phi((1-\gamma)u) + (1-\gamma) \phi(-\gamma u) \end{align*}$$
   
   $\phi=\exp$

Mam nadzieję, że trochę to wyjaśniłem.