Batas atas eksponensial

12

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 X1,,XnBer(θ)XiY1,,YnBer(1/2)XiYiN=i=1nYiYiXi

Z={1Ni=1nXiYiifN>0,0ifN=0.
Untuk , kami ingin menemukan batas atas untuk yang meluruh secara eksponensial dengan . Ketidaksetaraan Hoeffding tidak berlaku segera karena ketergantungan antar variabel.ϵ>0Pr(Zθ+ϵ)n
Zen
sumber
1
Biarkan . (i) Bukankah tidak tergantung dari ? (ii) bukankah ? ... Akibatnya, tidak jelas bagi saya bahwa bukan 'jumlah variabel acak independen'Zi=1NXiYiZiZjiZ=ZiZ
Glen_b -Reinstate Monica
Ah, poin bagus. Aku sedang memikirkan , daripada . Tapi tidak bisakah kamu menulis , dan biarkan ? Yaitu, jumlah semua kasus, apakah adalah 1 atau 0. ... tidak, itu tidak berhasil. Pembilangnya sama tetapi penyebutnya berbeda. N Z i = 1nNZ= n i = 1 ZiYZi=1nXiYiZ=i=1nZiY
Glen_b -Reinstate Monica
Itu memberi kurang dari sebagian keberhasilan dalam sampel, yang merupakan jumlah bunga dalam masalah, karena , karena . N n(1/n)i=1nXiYi(1/N)i=1nXiYiNn
Zen
1
Ya, itu sebabnya saya mengakhiri dengan "tidak itu tidak berhasil". Ada ketidaksetaraan yang berlaku untuk kasus non-independen, seperti beberapa ketidaksetaraan Bernstein (lihat item keempat), dan ada sejumlah ketidaksetaraan yang berlaku untuk martingales (meskipun saya tidak tahu bahwa itu akan berlaku di sini).
Glen_b -Reinstate Monica
1
Saya akan memeriksanya, dan juga mencoba menemukan koneksi dengan hasil martingales. Batas untuk sangat mudah ( ) bahwa tergoda untuk menghubungkan ini dengan menggunakan semacam pengkondisian. P r ( U θ / 2 + ϵ ) exp ( - 2 n ϵ 2 ) ZU=(1/n)i=1nXiYiPr(Uθ/2+ϵ)exp(2nϵ2)Z
Zen

Jawaban:

16

Kita dapat menarik koneksi ke ketidaksetaraan Hoeffding dengan cara yang cukup langsung .

Perhatikan bahwa kita memiliki

{Z>θ+ϵ}={iXiYi>(θ+ϵ)iYi}={i(Xiθϵ)Yi>0}.

Set sehingga Z i adalah iid, E Z i = 0 dan P ( Z > θ + ϵ ) = P ( i Z i > n ϵ / 2 )e - n ε 2 / 2Zi=(Xiθϵ)Yi+ϵ/2ZiEZi=0 Dengan aplikasi langsung dariketidaksetaraan Hoeffding ini(sejak Z i[ - θ - ε / 2 , 1 - θ - ε / 2 ] dan mengambil nilai dalam selang waktu satu ukuran).

P(Z>θ+ϵ)=P(iZi>nϵ/2)enϵ2/2,
Zi[θϵ/2,1θϵ/2]

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:

R. Vershynin, Pengantar analisis non-asimptotik dari matriks acak , Bab 5 dari Penginderaan Terkompresi, Teori dan Aplikasi. Diedit oleh Y. Eldar dan G. Kutyniok. Cambridge University Press, 2012.

Saya pikir eksposisi jelas dan memberikan cara yang sangat baik untuk segera terbiasa dengan literatur.

kardinal
sumber
1
Karena menyertakan ϵ / 2 dalam definisi mereka, saya memiliki kesan bahwa Z i[ - θ - ϵ / 2 , 1 - θ - ϵ / 2 ] (batas tidak berubah). Ziϵ/2Zi[θϵ/2,1θϵ/2]
Alecos Papadopoulos
1
Dear @Zen: Perhatikan bahwa penghitungan kasus yang cermat akan memungkinkan Anda untuk mengganti ketimpangan yang ketat > dengan ≥ di mana-mana tanpa mengubah batas akhir. N=0>
kardinal
Sayang @cardinal: Saya sudah reworded pertanyaan karena sebenarnya adalah (sedikit) bias estimator θ , karena E [ Z ] = E [ I { N = 0 } Z ] + E [ I { N > 0 } Z ] = ( 1 - 1 / 2 n )Zθ . E[Z]=E[I{N=0}Z]+E[I{N>0}Z]=(11/2n)θ
Zen
6

Detail untuk menangani kasus . N=0

{Zθ+ϵ}=({Zθ+ϵ}{N=0})({Zθ+ϵ}{N>0})=({0θ+ϵ}{N=0})({Zθ+ϵ}{N>0})=({N=0})({Zθ+ϵ}{N>0})={i=1nXiYi(θ+ϵ)i=1nYi}{N>0}{i=1nXiYi(θ+ϵ)i=1nYi}={i=1n(Xiθϵ)Yi0}={i=1n((Xiθϵ)Yi+ϵ/2)nϵ/2}.

Untuk Alecos.

E[i=1nWi]=E[I{i=1nYi=0}i=1nWi]+E[I{i=1nYi>0}i=1nWi]=E[I{i=1nYi>0}i=1nYii=1nYi]=E[I{i=1nYi>0}]=11/2n.
Zen
sumber
5

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

WiYii=1nYi,i=1nYi0,i=1nWi=1,n2

sementara kita mengatur jika Σ n i = 1 Y i = 0 .Wi=0i=1nYi=0

Kemudian kita memiliki variabel

Zn=i=1nWiXi,E(Zn)μn

Kami tertarik pada probabilitas

Pr(Znμn+ϵ),ϵ<1-μn

Adapun banyak ketidaksetaraan lainnya, Hoeffding memulai alasannya dengan mencatat bahwa dan itu

Pr(Znμn+ϵ)=E[1{Zn-μn-ϵ0}]

1{Zn-μn-ϵ0}exp{h(Zn-μn-ϵ)},h>0

Untuk kasus tergantung-variabel, seperti Hoeffding kita menggunakan fakta bahwa dan aktifkan ketidaksetaraan Jensen untuk (cembung) fungsi eksponensial, untuk menulissaya=1nWsaya=1

ehZn=exp{h(saya=1nWsayaXsaya)}saya=1nWsayaehXsaya

dan menghubungkan hasil untuk sampai pada

Pr(Znμn+ϵ)e-h(μn+ϵ)E[saya=1nWsayaehXsaya]

Berfokus pada kasus kami, karena dan X i bersifat independen, nilai yang diharapkan dapat dipisahkan,WsayaXsaya

Pr(Znμn+ϵ)e-h(μn+ϵ)saya=1nE(Wsaya)E(ehXsaya)

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[ehXsaya]hE[ehXsaya]=1-θ+θeh

Pr(Znμn+ϵ)e-h(μn+ϵ)(1-θ+θeh)saya=1nE(Wsaya)

Meminimalkan RHS sehubungan dengan , kita dapatkanh

eh=(1-θ)(μn+ϵ)θ(1-μn-ϵ)

Memasukkannya ke dalam ketidaksetaraan dan memanipulasi kita dapatkan

Pr(Znμn+ϵ)(θμn+ϵ)μn+ϵ(1-θ1-μn-ϵ)1-μn-ϵsaya=1nE(Wsaya)

sementara

Pr(Znθ+ϵ)(θθ+ϵ)θ+ϵ(1-θ1-θ-ϵ)1-θ-ϵsaya=1nE(Wsaya)

Hoeffding menunjukkan itu

(θθ+ϵ)θ+ϵ(1-θ1-θ-ϵ)1-θ-ϵe-2ϵ2

saya=1nE(Wsaya)=1-1/2n

Pr(Znθ+ϵ)(1-12n)e-2ϵ2BD

Bsaya

BD=(1-12n)e-2ϵ2e-nϵ2/2=Bsaya

2n-12nexp{(4-n2)ϵ2}

n4BDBsayan5BsayaBDϵn=12ϵ0,008Bsaya


WsayaXsayaXsaya

Alecos Papadopoulos
sumber
E[W1]=(1-1/2n)/nn
@ Zen Memang (sebenarnya itu meningkat dengan ukuran sampel, meskipun terikat), itulah sebabnya ikatan Kardinal lebih berguna untuk sebagian besar ukuran sampel.
Alecos Papadopoulos