Memahami mengukur ketimpangan konsentrasi

Dalam semangat pertanyaan Memahami bukti lemma yang digunakan dalam ketidaksetaraan Hoeffding , saya mencoba memahami langkah-langkah yang mengarah pada ketidaksetaraan Hoeffding.

Apa yang memegang misteri paling bagi saya dalam buktinya adalah bagian di mana momen eksponensial dihitung untuk jumlah variabel iid, setelah mana ketimpangan Markov diterapkan.

Tujuan saya adalah untuk memahami: Mengapa teknik ini memberikan ketimpangan yang ketat, dan apakah itu yang paling ketat yang bisa kita capai? Penjelasan tipikal mengacu pada properti penghasil momen dari eksponen. Namun, saya menemukan ini terlalu kabur.

Sebuah posting di blog Tao, http://terrytao.wordpress.com/2010/01/03/254a-notes-1-concentration-of-measure/#hoeff , mungkin menyimpan beberapa jawaban.

Dengan mengingat tujuan ini, pertanyaan saya adalah tentang tiga poin dalam jabatan Tao yang saya hambatkan dan yang saya harap dapat memberikan wawasan yang pernah dijelaskan.

1. Tao mendapatkan ketidaksetaraan berikut menggunakan momen k-th Jika ini benar untuk setiap k, ia menyimpulkan batas eksponensial. Di sinilah aku tersesat. P(|Sn|≥λ

   $$\displaystyle {\bf P}( |S_n| \geq \lambda \sqrt{n} ) \leq 2 (\frac{\sqrt{ek/2}}{\lambda})^k. \ \ \ \ \ (7)$$ $$\displaystyle {\bf P}( |S_n| \geq \lambda \sqrt{n} ) \leq C \exp( - c \lambda^2 ) \ \ \ \ \ (8)$$

2. Lemma Hoeffding disajikan: Lemma 1 (lemma Hoeffding) Misalkan menjadi variabel skalar yang mengambil nilai dalam interval . Kemudian untuk , Khususnya Bukti Lemma 1 dimulai dengan mengambil ekspektasi atas ekspansi taylor Mengapa ekspansi dapat dibatasi oleh istilah kuadratik dan bagaimana persamaan 10 mengikuti?[ a , b ] t > 0 E e t X ≤ e t E X ( 1 + O ( t 2 V a r ( X ) exp ( O ( t ( b - a ) ) ) ) . ( 9 ) E e t X ≤ e t E X exp ( O ${X}$${[a,b]}$${t>0}$

   $$\displaystyle {\bf E} e^{tX} \leq e^{t {\bf E} X} (1 + O( t^2 {\bf Var}(X) \exp( O( t (b-a) ) ) ). \ \ \ \ \ (9)$$ e t X = 1 + t X + O ( t 2 X 2 exp ( O ( t ) ) $$\displaystyle {\bf E} e^{tX} \leq e^{t {\bf E} X} \exp( O( t^2 (b-a)^2 ) ). \ \ \ \ \ (10)$$ $\displaystyle e^{tX} = 1 + tX + O( t^2 X^2 \exp( O(t) ) )$

3. Akhirnya, latihan diberikan:
   Latihan 1 Tunjukkan bahwa faktor dalam (10) dapat diganti dengan , dan bahwa ini tajam. Ini akan memberikan bukti yang jauh lebih pendek daripada yang ada di Memahami bukti lemma yang digunakan dalam ketidaksetaraan Hoeffding , tapi saya tidak tahu bagaimana menyelesaikannya.t 2 ( b - a ) 2 /${O(t^2(b-a)^2)}$${t^2 (b-a)^2/8}$

Semua intuisi \ penjelasan lebih lanjut tentang bukti ketidaksetaraan atau alasan kita tidak dapat memperoleh ikatan yang lebih ketat pasti diterima.

Penggunaan momen eksponensial adalah langkah umum dalam proses pembuktian konsentrasi ketidaksetaraan ukuran. Pemahaman saya adalah sebagai berikut 1) Dengan menggunakan daripada , seseorang menangkap semua momen , bukan hanya momen pertama. Oleh karena itu, selalu menguntungkan untuk terikat , daripada terikat , karena ada informasi lebih lanjut dalam . Mengapa memiliki informasi lebih lanjut? Penjelasan informal diberikan oleh fakta bahwa Taylor mengembangkan . Seperti yang Anda lihat, semua kekuatanE X X E e $\mathbb{E}e^X$$\mathbb{E} X$$X$$\mathbb{E} e^X$$\mathbb{E}X$$\mathbb{E} e^X$$\mathbb{E} e^X$XEX$e^{X}=1+X+\frac{X^2}{2}+\frac{X^3}{6}+\ldots$$X$terlibat. Oleh karena itu, ketika Anda mengambil , Anda pada dasarnya berakhir berlari semua momen dari . $\mathbb{E}X$$X$