Diberikan urutan variabel acak iid, katakanlah, untuk , saya mencoba untuk mengikat berapa kali rata-rata empiris berarti akan melebihi nilai, , saat kami terus menggambar sampel, yaitu: i = 1 , 2 , . . . , n 1c≥0T d e f = n ∑ j=1P({ 1
Jika kita mengasumsikan bahwa untuk beberapa , kita dapat menggunakan ketidaksetaraan Hoeffding untuk sampai padaa > 0
Yang terlihat bagus (mungkin) tetapi sebenarnya cukup longgar, apakah ada cara yang lebih baik untuk membatasi nilai ini? Saya berharap mungkin ada cara karena berbagai peristiwa (untuk masing-masing ) jelas tidak independen, saya tidak mengetahui cara untuk mengeksploitasi ketergantungan ini. Juga, alangkah baiknya untuk menghapus batasan bahwa lebih besar dari rata-rata.c
sunting : Pembatasan menjadi lebih besar dari rata-rata dapat dihapus jika kita menggunakan Ketimpangan Markov sebagai berikut:
Jawaban:
Ini adalah pendekatan yang dibuat dengan tangan, dan saya akan sangat menghargai beberapa komentar tentang itu, (dan yang mengkritik biasanya yang paling bermanfaat). Jika saya mengerti dengan benar, OP menghitung sampel berarti , di mana setiap sampel berisi observasi +1 sampel sebelumnya dari rv baru. distribusi setiap mean sampel. Lalu kita bisa menulisx¯j Fj
Pertimbangkan ukuran sampel setelah distribusi mean sampel hampir normal, menunjukkan itu . Lalu kita bisa menulism G^
Memecahkan kita memperoleh mana adalah standar normal cdf, adalah standar deviasi dari proses iid, dan adalah artinya. Memasukkan ke dalam terikat dan mengatur ulang kita dapatkanG^j(c)
Perhatikan bahwa batasan ini juga tergantung pada varian proses. Apakah ini ikatan yang lebih baik daripada yang disajikan dalam pertanyaan? Ini akan sangat tergantung pada seberapa "cepat" distribusi rata-rata sampel menjadi "hampir normal". Untuk memberikan contoh angka, asumsikan bahwa . Asumsikan juga bahwa variabel acak seragam dalam . Kemudian dan . Pertimbangkan deviasi 10% dari nilai tengah, yaitu atur . lalu: sudah untuk batas yang saya usulkan (yang berarti untuk ) menjadi lebih ketat. Untuk batas Hoeffding adalahm=30 [0,1] σ=112−−√ a=0,05n=34n>30n=10078,536,2≈199,5≈38,5μ=12 a=0.05 n=34 n>30 n=100 78.5 sedangkan batas yang saya usulkan adalah . The Hoeffding terikat konvergen ke sedangkan terikat Saya mengusulkan untuk Jika Anda meningkatkan perbedaan antara dua batas mengurangi namun tetap terlihat: untuk deviasi 20%, , yang Hoeffding terikat konvergen ke sementara terikat Saya mengusulkan konvergen ke (yaitu jumlah dari cdf normal memberikan kontribusi sangat sedikit untuk keseluruhan terikat).
Agak lebih umum, kami perhatikan bahwa untuk , batas Hoeffding bertemu36.2 ≈199.5 ≈38.5 a a=0.1 49.5 30.5
n→∞
Karena untuk nilai-nilai kecil dari (yang lebih merupakan kasus yang menarik) menjadi sejumlah besar, masih ada kasus bahwa dapat mengungguli dalam ketat, bahkan jika sampel sedemikian rupa sehingga distribusi sampel berarti konvergen perlahan ke distribusi normal.H b A ba Hb Ab
sumber