Misalkan kita memiliki variabel acak IID dengan distribusi . Kita akan mengamati sampel dengan cara berikut: biarkan menjadi independen variabel acak, misalkan semua dan 's independen, dan menentukan ukuran sampel . The 's menunjukkan yang mana dari ' s berada dalam sampel, dan kami ingin belajar fraksi keberhasilan dalam sampel didefinisikan oleh
Untuk , kami ingin menemukan batas atas untuk yang meluruh secara eksponensial dengan . Ketidaksetaraan Hoeffding tidak berlaku segera karena ketergantungan antar variabel.
Jawaban:
Kita dapat menarik koneksi ke ketidaksetaraan Hoeffding dengan cara yang cukup langsung .
Perhatikan bahwa kita memiliki
Set sehingga Z i adalah iid, E Z i = 0 dan P ( Z > θ + ϵ ) = P ( ∑ i Z i > n ϵ / 2 ) ≤ e - n ε 2 / 2Zsaya= ( Xsaya- θ - ϵ ) Ysaya+ ϵ / 2 Zsaya E Zsaya= 0
Dengan aplikasi langsung dariketidaksetaraan Hoeffding ini(sejak Z i ∈ [ - θ - ε / 2 , 1 - θ - ε / 2 ] dan mengambil nilai dalam selang waktu satu ukuran).
Ada literatur terkait yang kaya dan menarik yang telah dibangun selama beberapa tahun terakhir, khususnya, pada topik yang berkaitan dengan teori matriks acak dengan berbagai aplikasi praktis. Jika Anda tertarik pada hal semacam ini, saya sangat merekomendasikan:
Saya pikir eksposisi jelas dan memberikan cara yang sangat baik untuk segera terbiasa dengan literatur.
sumber
Detail untuk menangani kasus .N= 0
Untuk Alecos.
sumber
Jawaban ini terus bermutasi. Versi saat ini tidak berhubungan dengan diskusi yang saya lakukan dengan @ cardinal di komentar (meskipun melalui diskusi ini saya untungnya menyadari bahwa pendekatan pengkondisian tampaknya tidak mengarah ke mana pun).
Untuk upaya ini, saya akan menggunakan bagian lain dari makalah asli Hoeffding 1963 , yaitu bagian 5 "Jumlah Variabel Acak Tergantung".
Atur
sementara kita mengatur jika Σ n i = 1 Y i = 0 .Wsaya= 0 ∑ni = 1Ysaya= 0
Kemudian kita memiliki variabel
Kami tertarik pada probabilitas
Adapun banyak ketidaksetaraan lainnya, Hoeffding memulai alasannya dengan mencatat bahwa dan itu
Untuk kasus tergantung-variabel, seperti Hoeffding kita menggunakan fakta bahwa dan aktifkan ketidaksetaraan Jensen untuk (cembung) fungsi eksponensial, untuk menulis∑ni = 1Wsaya= 1
dan menghubungkan hasil untuk sampai pada
Berfokus pada kasus kami, karena dan X i bersifat independen, nilai yang diharapkan dapat dipisahkan,Wsaya Xsaya
Dalam kasus kami, adalah iid Bernoullis dengan parameter θ , dan E [ e h X i ] adalah fungsi yang menghasilkan momen umum dalam h , E [ e h X i ] = 1 - θ + θ e h . BegituXsaya θ E[ eh Xsaya] h E[ eh Xsaya] = 1 - θ + θ eh
Meminimalkan RHS sehubungan dengan , kita dapatkanh
Memasukkannya ke dalam ketidaksetaraan dan memanipulasi kita dapatkan
sementara
Hoeffding menunjukkan itu
sumber