Memahami bukti lemma yang digunakan dalam ketidaksetaraan Hoeffding

Saya sedang mempelajari catatan kuliah Larry Wasserman tentang Statistik yang menggunakan Casella dan Berger sebagai teks utamanya. Saya sedang mengerjakan catatan kuliahnya set 2 dan terjebak dalam derivasi lemma yang digunakan dalam ketidaksetaraan Hoeffding (hal.2-3). Saya mereproduksi bukti dalam catatan di bawah ini dan setelah bukti saya akan menunjukkan di mana saya terjebak.

Kata pengantar singkat

Misalkan dan . Kemudian .$\mathbb{E}(X) = 0$$a \le X \le b$$\mathbb{E}(e^{tX}) \le e^{t^2 (b-a)^2/8}$

Bukti

Karena , kita dapat menulis sebagai kombinasi cembung dari dan , yaitu mana . Dengan cembung dari fungsi kita miliki$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}$

Ambil harapan dari kedua belah pihak dan gunakan fakta untuk mendapatkan$\mathbb{E}(X) = 0$

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

di mana , dan . Perhatikan bahwa . Juga untuk semua 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$

Dengan teorema Taylor, ada $\varepsilon \in (0, u)$ sedemikian sehingga $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}$

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

Saya bisa mengikuti buktinya sampai

$\mathbb{E}(e^{tX}) \le \frac{-a}{b-a} e^{tb} + \frac{b}{b-a} e^{ta} = e^{g(u)}$ tetapi saya tidak dapat menemukan cara menurunkan .$u, g(u), \gamma$

Saya tidak yakin saya memahami pertanyaan Anda dengan benar. Saya akan mencoba menjawab: coba tulis sebagai fungsi : this adalah alami karena Anda ingin terikat dalam .

Dengan dibantu oleh pengalaman, Anda akan tahu bahwa lebih baik memilih untuk menuliskannya dalam bentuk . Kemudian mengarah ke dengan .$e^{g(u)}$

Apakah itu jenis hal yang Anda minta?

Sunting: beberapa komentar tentang buktinya

1. Trik pertama layak untuk diperhatikan dengan cermat: jika adalah fungsi cembung, dan adalah variabel acak terpusat, maka mana adalah variabel diskrit yang ditentukan oleh Sebagai konsekuensinya, Anda mendapatkan adalah variabel terpusat dengan dukungan dalam yang memiliki varian tertinggi: Perhatikan bahwa jika kami memperbaiki lebar dukungan$\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)$, ini kurang dari seperti Dilip katakan dalam komentar, ini karena ; batas diperoleh untuk .$(b-a)^2\over 4$$(b-a)^2 + 4ab \ge 0$$a=-b$

2. Sekarang giliran masalah kita. Mengapa mungkin untuk mendapatkan ikatan hanya bergantung pada ? Secara intuitif, ini hanya masalah : jika Anda memiliki batas untuk kasus , maka batas umum dapat diperoleh dengan mengambil . Sekarang pikirkan kumpulan variabel terpusat dengan dukungan lebar 1: tidak ada begitu banyak kebebasan, jadi batas seperti harus ada. Pendekatan lain adalah dengan mengatakan bahwa dengan lemma di atas pada , maka lebih umum , yang hanya bergantung pada dan$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$ : jika Anda memperbaiki dan , dan biarkan bervariasi, hanya ada satu derajat kebebasan, dan , , . Kita mendapatkan Anda hanya perlu menemukan ikatan yang hanya melibatkan .$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. Sekarang kami yakin itu bisa dilakukan, itu pasti jauh lebih mudah! Anda tidak perlu berpikir untuk untuk memulai. Intinya adalah bahwa Anda harus menulis semuanya sebagai fungsi dari dan . Perhatikan pertama bahwa , , dan . Kemudian Sekarang kita berada dalam kasus khusus ... I pikir kamu bisa menyelesaikannya.$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$

Saya harap saya mengklarifikasi sedikit.