Bagaimana bukti Sampling Penolakan masuk akal?

9

Saya mengambil kursus tentang metode Monte Carlo dan kami belajar metode Sampling Penolakan (atau Sampling Terima-Tolak) dalam kuliah terakhir. Ada banyak sumber daya di web yang menunjukkan bukti metode ini, tetapi entah bagaimana saya tidak yakin dengan mereka.

Jadi, dalam Sampel Penolakan, kami memiliki distribusi f(x)yang sulit untuk diambil sampelnya. Kami memilih distribusi sampel yang mudahg(x) dan temukan koefisien c seperti yang f(x)cg(x). Kemudian kami sampel darig(x) dan untuk setiap undian, xi, kami juga mencicipi a u dari distribusi seragam standar U(u|0,1).

Contoh xi diterima jika itu cg(xi)uf(xi) dan menolak sebaliknya.

Bukti yang saya temui biasanya hanya menunjukkan itu p(x|Accept)=f(x) dan berhenti di situ.

Apa yang saya pikirkan tentang proses ini adalah bahwa kita memiliki urutan variabel x1,Accept1,x2,Accept2,...,xn,Acceptn dan a xi,Accepti pasangan sesuai dengan sampel i.th kami (xi) dan apakah itu diterima (Accepti). Kita tahu itu masing-masingxi,Accepti pasangan tidak tergantung satu sama lain, sehingga:

P(x1,Accept1,x2,Accept2,...,xn,Acceptn)=i=1nP(xi,Accepti)

Untuk sebuah (xi,Accepti) pasangan kita tahu itu P(xi)=g(xi) dan P(Accepti|xi)=f(xi)cg(xi). Kami siap menghitungp(xi|Accepti)tapi saya tidak mengerti bagaimana itu cukup sebagai bukti. Kita perlu menunjukkan bahwa algoritme berfungsi, jadi saya pikir bukti harus menunjukkan bahwa distribusi empiris dari sampel yang diterima konvergen kef(x) sebagai n. Maksudku, dengann menjadi jumlah semua sampel yang diterima dan ditolak:

Numberofsampleswith(AxiB)NumberofacceptedsamplesABf(x)dx sebagai n.

Apakah saya salah dengan pola pikir ini? Atau adakah hubungan antara bukti umum dari algoritma dan ini?

Terima kasih sebelumnya

Ufuk Can Bicici
sumber

Jawaban:

8

Anda harus menganggap algoritma sebagai penghasil undian dari variabel acak, untuk menunjukkan bahwa algoritme berfungsi, cukup untuk menunjukkan bahwa algoritme menarik dari variabel acak yang Anda inginkan.

Membiarkan X dan Y menjadi variabel acak skalar dengan pdf fX dan fY masing-masing, di mana Yadalah sesuatu yang sudah kita ketahui cara mengambil sampel. Kita juga bisa tahu bahwa kita bisa terikatfX oleh MfY dimana M1.

Kami sekarang membentuk variabel acak baru A dimana A|yBernoulli (fX(y)MfY(y)), ini mengambil nilai 1 dengan probabilitas fX(y)MfY(y) dan 0jika tidak. Ini mewakili algoritme 'menerima' hasil seriY.

Sekarang kita jalankan algoritme dan kumpulkan semua hasil undian Y yang diterima, sebut saja variabel acak ini Z=Y|A=1.

Untuk menunjukkan itu ZX, untuk acara apa pun E, kita harus tunjukkan itu P(ZE)=P(XE).

Jadi mari kita coba itu, pertama gunakan aturan Bayes:

P(ZE)=P(YE|A=1)=P(YE&A=1)P(A=1),

dan bagian atas kita tuliskan sebagai

P(YE&A=1)=EfY,A(y,1)dy=EfA|Y(1,y)fY(y)dy=EfY(y)fX(y)MfY(y)dy=P(XE)M.

Dan kemudian bagian bawahnya sederhana

P(A=1)=fY,A(y,1)dy=1M,

dengan alasan yang sama seperti di atas, pengaturan E=(,+).

Dan ini bergabung untuk memberi P(XE), itulah yang kami inginkan, ZX.

Begitulah cara algoritma bekerja, tetapi pada akhir pertanyaan Anda, Anda tampaknya khawatir tentang ide yang lebih umum, yaitu kapan distribusi empiris bertemu dengan distribusi sampel? Ini adalah fenomena umum tentang pengambilan sampel apa pun jika saya mengerti Anda dengan benar.

Dalam hal ini, biarkan X1,,Xn menjadi variabel acak semua dengan distribusi X. Lalu untuk acara apa punE, i=1n1XiEn memiliki harapan P(XE) oleh linearitas harapan.

Lebih jauh lagi, dengan asumsi yang sesuai, Anda dapat menggunakan hukum kuat jumlah besar untuk menunjukkan bahwa probabilitas empiris konvergen hampir pasti dengan probabilitas sebenarnya.

Harri
sumber
Terima kasih atas jawabannya. Bisakah Anda mengklarifikasi bagaimana saya bisa menunjukkan bahwa distribusi empiris menyatu dengan distribusi target dengan menggunakan Hukum Angka Besar? Persis seperti itulah yang saya coba tunjukkan dalam kasus ini.
Ufuk Can Bicici
4
Glivenko-Cantelli: www2.imperial.ac.uk/ ~das01
Zen
@ Harri Yang mengganggu saya adalah fakta bahwa kita mempelajari variabel acak yang menunjukkan penerimaan undian (A=1) setelah kita mempelajari nilai dari variabel aktual. Kami mengamati variabel sesuai dengan urutannyaY1,A1,Y2,A2,...,Yn,An, jadi jika kita akan mengamati variabel Y2, apa yang kita ketahui tentang sistem ini Y1 dan A1 dan sejak itu Y2 tidak tergantung pada mereka, apa yang kami proses adalah yang pertama P(Y2), kemudian P(A2|Y2)bukan sebaliknya.
Ufuk Can Bicici
Bisakah Anda mengatakan lebih banyak tentang mengapa urutan pengetahuan P(Y2) lalu P(A2|Y2)mengganggu Anda?
Harri
1

Pertama, perlu diingat bahwa prosedur lengkap metode penolakan sampel hanya menghasilkan variabel acak tunggal . Ketika beberapaxi diterima, prosedur berhenti, dan tidak ada xi+1lagi. Jika Anda ingin beberapa variabel acak, ulangi prosedur beberapa kali.

Di beberapa buku teks, mereka menunjukkan acara penerimaan oleh A dan menghitung probabilitas

P(A)=dx0f(x)cg(x)g(x)du=1cf(x)dx=1c.

Dan

fX(x|A)=fX(x)P(A|x)P(A)=g(x)f(x)cg(x)1c=f(x).

Yang membingungkan adalah penerimaan itu A di sini tampaknya penerimaan sampel tunggal xi, tetapi seluruh prosedur dapat menolak banyak xiini

Ya, bukti yang lebih ketat harus mempertimbangkan kemungkinan penerimaan pada langkah yang berbeda. MembiarkanXi menunjukkan isampel th, fXi menunjukkan fungsi kepadatan probabilitas Xi, Ai menunjukkan ipenerimaan th, dan Xmenunjukkan nilai akhir yang diterima. Kemudian fungsi kepadatan probabilitasX adalah

fX(x)=P(A1)fX1(x|A1)+P(A2)fX2(x|A2)+.
P(A1) adalah 1c dan fX1(x|A1) adalah f(x)seperti yang dihitung sebelumnya. CatatanP(A2) adalah (11c)1c dimana 11c adalah probabilitas penolakan X1 sejak kapan X1 ditolak jika kami memiliki kesempatan untuk memilih X2.

Dan fX2(x|A2) adalah f(x)juga karena langkah kedua tidak terpengaruh oleh langkah-langkah sebelumnya, kemungkinannya harus sama dengan langkah pertama. Jika penjelasan ini tidak meyakinkan Anda, kami juga bisa menyelesaikannya dengan keras. Hati-hatiX2 tidak ditentukan kapan X1 diterima (atau Anda dapat mendefinisikannya sebagai nomor acak kapan saja) X1 diterima jika nilai yang tidak ditentukan membuat Anda tidak nyaman), jadi untuk probabilitas tentang X2, hanya probabilitas kondisional yang diberikan A1c atau himpunan bagian dari A1cmasuk akal. Sekarang

fX2(x|A2)=P(A1c)fX2(x|A1c)P(A2|X2=x)P(A2)=P(A1c)fX2(x|A1c)P(A2|X2=x)P(A1c)P(A2|A1c)=fX2(x|A1c)P(A2|X2=x)P(A2|A1c)=g(x)f(x)cg(x)1c=f(x).
Begitu
fX(x)=P(A1)f(x)+P(A2)f(x)+=(P(A1)+P(A2)+)f(x)=(1c+(11c)1c+(11c)21c+)f(x)=f(x).
Itu adalah hasil yang diinginkan. CatatanP(A1)+P(A2)+ = 1 memiliki makna intuitif, yang pada akhirnya satu sampel akan diterima pada beberapa langkah i.
Cosyn
sumber