Ketidaksamaan probabilitas

37

Saya mencari beberapa ketidaksetaraan probabilitas untuk jumlah variabel acak yang tidak terikat. Saya akan sangat menghargai jika ada yang bisa memberikan saya beberapa pemikiran.

Masalah saya adalah untuk menemukan batas atas eksponensial atas probabilitas bahwa jumlah variabel acak iid tidak terikat, yang sebenarnya merupakan perkalian dua iid Gaussian, melebihi beberapa nilai tertentu, yaitu, , di mana , dan v_i dihasilkan iid dari \ mathcal {N} (0, \ sigma) .Pr[Xϵσ2N]exp(?)wiviN(0,σ)X=i=1NwiviwiviN(0,σ)

Saya mencoba menggunakan Chernoff terikat menggunakan fungsi penghasil momen (MGF), batas yang diturunkan diberikan oleh:

Pr[Xϵσ2N]minsexp(sϵσ2N)gX(s)=exp(N2(1+4ϵ21+log(1+4ϵ21)log(2ϵ2)))

mana gX(s)=(11σ4s2)N2 adalah MGF dari X . Tapi ikatannya tidak terlalu ketat. Masalah utama dalam masalah saya adalah bahwa variabel acak tidak terikat, dan sayangnya saya tidak bisa menggunakan batas ketidaksetaraan Hoeffding.

Saya akan senang jika Anda membantu saya menemukan beberapa ikatan eksponensial yang ketat.

Farzad
sumber
3
Kedengarannya seperti masalah yang terkait penginderaan-terkompresi. Lihat catatan R. Vershynin tentang teori matriks acak nonasimptotik, khususnya batasan tentang apa yang ia sebut variabel acak subeksponensial . Itu akan membantu Anda memulai. Jika Anda membutuhkan lebih banyak petunjuk, beri tahu kami dan saya akan mencoba memposting beberapa info lebih lanjut.
kardinal
1
Setidaknya ada beberapa pertanyaan dan jawaban terkait pada topik ini pada math.SE (penafian: termasuk yang saya ikuti).
kardinal
1
Produk memiliki distribusi 'produk normal'. Saya percaya bahwa rata-rata produk ini adalah nol dan variansnya adalah mana adalah varian dari dan . Untuk largeish, Anda bisa menggunakan teorema limit sentral untuk mendapatkan norality perkiraan . Jika Anda dapat menghitung kemiringan dari distribusi produk normal, saya yakin Anda dapat menerapkan teorema Berry-Esseen untuk mengikat laju konvergensi CDF. σ 4 σ 2 w i v i N X,wiviσ4σ2wiviNX
shabbychef
1
@shabbychef, Berry-Esseen memiliki konvergensi cukup lambat, karena itu seragam terikat atas kelas semua fungsi distribusi . F
kardinal
4
@DilipSarwate: Maaf saya baru saja melihat komentar Anda beberapa waktu yang lalu. Saya pikir Anda mungkin tertarik pada makalah kecil berikut, yang telah saya hubungkan dengan beberapa kali pada matematika. SE juga: TK Phillips dan R. Nelson (1995), Momen terikat lebih ketat daripada Chernoff terikat untuk positive tail probabilitas , The American Statistician , vol 42, no. 2., 175-178.
kardinal

Jawaban:

1

Menggunakan batas Chernoff yang Anda sarankan untuk beberapa yang akan ditentukan kemudian, mana ketidaksamaan kedua berlaku berkat untuk setiap . Sekarang ambil dan , sisi kanan menjadi yang menghasilkan untuk setiap .s1/(2σ2)- log ( 1 - x )

P[X>t]exp(st)exp((N/2)log(1σ4s2))exp(st+σ4s2N)
log(1x)2xx(0,1/2)t=ϵσ2Ns=t/(2σ4N)exp(t2/(4σ4N)=exp(ϵ2N/4)ϵ ( 0 , 1 )
P[X>ϵσ2N]exp(ϵ2N/4).
ϵ(0,1)

Cara lain adalah secara langsung menerapkan ketidaksetaraan konsentrasi seperti ketidaksetaraan Hanson-Wright, atau ketidaksetaraan konsentrasi untuk kekacauan Gaussian pesanan 2 yang mencakup variabel acak yang Anda minati.

Pendekatan yang lebih sederhana tanpa menggunakan fungsi menghasilkan momen

Ambil untuk kesederhanaan (jika tidak, orang dapat mengubah skala dengan membaginya dengan ).σ=1σ2

Menulis dan . Anda meminta batas atas pada .v=(v1,...,vn)Tw=(w1,...,wn)TP(vTw>ϵN)

Biarkan. Kemudian dengan independensi dan tidak tergantung pada dengan dengan derajat kebebasan.Z=wTv/vZN(0,1)v,wv2Zχ2n

Dengan batasan standar pada variabel normal normal dan acak, Menggabungkan dengan ikatan gabungan memberikan batas atas pada dari formulir .χ2

P(|Z|>ϵn/2)2exp(ϵ2n/4),P(v>2n)exp(n(21)2/2).
P(vTw>ϵN)2exp(ϵ2n/4)+exp(n(21)2/2)

sial
sumber
0

Batas yang Anda peroleh adalah dengan urutan sebagai . Saya tidak berpikir Anda bisa melakukan lebih baik untuk umum . Dari halaman Wikipedia pada Variabel Produk distribusi adalah mana adalah fungsi Bessel yang dimodifikasi. Dari (10.25.3) dalam daftar fungsi DLMF , sehingga untuk cukup besar yang tidak akan memberi Anda batasan sub-Gaussian.eϵϵϵw i v i K 0 ( z ) / π K 0 K 0 ( t ) e - t / wiviK0(z)/πK0K0(t)et/txP(wivi>x)xet/tdt

BookYourLuck
sumber