Transformasi Box-Muller

Transformasi Box-Müller (diwanohkeun ku George Edward Pelham Box jeung Mervin Edgar Müller 1958) nyaéta métodeu  keur ngarundaykeun pasangan mandiri ilahar dina sebaran normal (ekspektasi nol, varian hiji) tina wilangan acak, nu sumber wilangan acakna tina sebaran seragam.

Geus ilahar ditembongkeun dina dua wanda. Wanda dasar nyaéta dijéntrékeun ku Box jeung Müller nu nyokot dua sampel tina sebaran seragama dina interval (0, 1] terus dipetakeun kana dua sample sebaran normal. Wanda polar nu nyokot dua sampel tina interval nu béda, [−1, +1], terus dipetakuen kana dua sampel sebaran normal tur teu maké fungsi sinus atawa kosinus.

Nu hiji kudu maké metoda sampling transformasi invers keur ngarundaykeun wilangan acak sebaran-normal; tansformasi Box-Müller geus diwangun dina métodeu  komputasi nu leuwih efektif. Salian ti eta, algoritma Ziggurat ogé bisa dipaké.

Wanda dasar 
Anggap U1 jeung U2 mangrupa variabel acak mandiri tina sebaran seragam dina interval (0, 1]. Mangka

sarta

Mangka Z0 jeung Z1 nyaéta variabel acak mandiri nu mibanda simpangan baku sarua jeung hiji dina sebaran normal.

Turunanna dumasar kana ieu kanyataan, dia dua-dimensi sistim kordinat Kartesius nu mana kordinat X jeung Y dijéntrékeun ku dua variabel mandiri tur mibanda sebaran normal, variabel acak keur R2 jeung Θ (ditembongkeun di luhur) nu pakait jeung sistim kordinat polar ogé mandiri tur dijéntrékeun salaku

jeung

Wanda polar 
Wanda polar ditambahkeun ku Devroye ka Marsaglia. Ieu ogé dianggap bari teu ditambahkeun dina Carter.

Ditangtukeun u jeung v, mandiri tur kasebar seragam dina interval nu deukeut [−1, +1], tina susunan s = R2 = u2 + v2. (Jelasna .)  Lamun s = 0 atawa s > 1, kaluarkeun u jeung v sarta coba pasangan séjén (u, v).  Teruskeun nepi ka pasangan s dina interval nu kabuka (0, 1) kapanggih.  Sabab u jeung v kasebar saragam jeung ngan dina titik sajero buleudan nu dimeunangkeun, nilai s bakal kasebar saragam dina interval kabuka (0, 1) ogé. Saterusna bisa gampang katempo ku ngitung sebaran kumulatif s dina (0, 1). Hal ieu teu leuwih tina daerah buleudan nu jari-jarina  dibagi . Ti dieu bisa kapanggih fungsi densiti probabilitas nu mibanda nilai angger hiji dina interval (0, 1). Sarua jeung sudut θ dibagi  katempo jéntré kasebar sargam dina interval nu kabuka (0, 1) jeung s nu mandiri.

Saterusna nangtukeun nilai s nu mana U1 jeung  sarta U2 dina wanda dasar. Saperti nu katempo dina gambar, nilai  jeung  dina wanda dasar bisa digantikeun ku babandingan  jeung , sacara ngaruntuy.  Kauntunganna nyaéta itungan fungsi trigonometri bisa langsung dipaké. Hal ieu kacida ngabantu lamun ngabandingkeun leuwih loba bagian tur digantikeun ku nu séjénna .

Saperti wanda dasar ngahasilkeun dua simpangan normal standar, mangka hal ieu mangrupa alternatif itungan séjén.

jeung

Beda nu jelas antara dua wanda 

métodeu  polar béda jeung métodeu  dasar nyaéta dina nolak nyokot sampel. Cara nyokotna sababara rundayan wilangan normal, sacara tipikal leuwih gancang tinimbanf métodeu  dasar, hal ieu sabab cara ngitungna nu leuwih sederhana (geus ditembongkeun yén ngarundaykeun wilangan acak leuwih gancang) sarta sacara numerik leuwih tegep.  Hal ieu bisa ngagunakeun fungsi trigonometri, nu mana mindeng dipaké dina kaperluan komputasi. Ieu nyokot 1 − π/4 ≈ 21.46% tina sakabéh asupan wilangan acak sebaran normal nu dirundaykeun, upamana nyokot 4/π − 1 ≈ 27.32% pasangan wilangan acak sebaran normal per Gaussian nu dirundaykeun, merlukeun 4/π ≈ 1.2732 asupan wilangan acak per kaluaran wilangan acak.

Wanda dasar merlukeun tilu kali prosés kakalian, hiji logaritma, hiji akar kuadrat sarta tilu fungsi trigonometri keur unggal variasi normal.

Wanda polar merlukeun dua kali prosés kakalian, hiji logaritma, hiji akar kuadrat tur hiji bagian unggal hiji variasi. Hal ini nyababkeun ngagantikeun kakalian jeung fungsi trigonometri ku hiji bagian.

Tempo oge
 Sebaran normal
 Inverse transform sampling
 Marsaglia polar method, optimasi Transformasi Box-Müller
 Ziggurat algorithm, cara nu béda kacida dina ngarundaykeun wilangan normal acak

Rujukan

Tumbu luar 
 Box-Müller running in a Java Applet 
 Generating Gaussian Random Numbers
 Box-Müller Transform on MathWorld

Transformasi
Pseudorandom number generators
Métode Monte Carlo