Transformasi Box-Muller

Transformasi Box-Müller (diwanohkeun ku George Edward Pelham Box jeung Mervin Edgar Müller 1958)^[1] 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.^[2] Salian ti eta, algoritma Ziggurat ogé bisa dipaké.

Wanda dasar

Anggap U₁ jeung U₂ mangrupa variabel acak mandiri tina sebaran seragam dina interval (0, 1]. Mangka

Z_{0}=R\cos(\Theta )={\sqrt {-2\ln U_{1}}}\cos(2\pi U_{2})\,

sarta

Z_{1}=R\sin(\Theta )={\sqrt {-2\ln U_{1}}}\sin(2\pi U_{2}).\,

Mangka Z₀ jeung Z₁ nyaéta variabel acak mandiri nu mibanda simpangan baku sarua jeung hiji dina sebaran normal.

Turunanna^[3] 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 R² jeung Θ (ditembongkeun di luhur) nu pakait jeung sistim kordinat polar ogé mandiri tur dijéntrékeun salaku

R^{2}=-2\cdot \ln U_{1}\,

jeung

\Theta =2\pi U_{2}.\,

Wanda polar

Dua nilai sebaran saragam,

u

jeung

v

dipake keur ngahasilkeun niley

s=R^{2}

, nu meh sarimbag jeung sebaran seragam. Harti sinus jeung kosinus dipake kana wanda dasar Transformasi Box-Müller dina raraga bisa ngagunakeun fungsi trigonometri.

Wanda polar ditambahkeun ku Devroye^[4] ka Marsaglia. Ieu ogé dianggap bari teu ditambahkeun dina Carter.^[5]

Ditangtukeun u jeung v, mandiri tur kasebar seragam dina interval nu deukeut [−1, +1], tina susunan s = R² = u² + v². (Jelasna $\scriptstyle R={\sqrt {s}}$ .) 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 $\scriptstyle {\sqrt {s}}$ dibagi $\scriptstyle \pi$ . Ti dieu bisa kapanggih fungsi densiti probabilitas nu mibanda nilai angger hiji dina interval (0, 1). Sarua jeung sudut θ dibagi $\scriptstyle 2\pi$ katempo jéntré kasebar sargam dina interval nu kabuka (0, 1) jeung s nu mandiri.

Saterusna nangtukeun nilai s nu mana U₁ jeung $\scriptstyle \theta /(2\pi )$ sarta U₂ dina wanda dasar. Saperti nu katempo dina gambar, nilai $\scriptstyle \cos \theta =\cos 2\pi U_{2}$ jeung $\scriptstyle \sin \theta =\sin 2\pi U_{2}$ dina wanda dasar bisa digantikeun ku babandingan $\scriptstyle \cos \theta =u/R=u/{\sqrt {s}}$ jeung $\scriptstyle \sin \theta =v/R=v/{\sqrt {s}}$ , 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.

z_{0}={\sqrt {-2\ln U_{1}}}\cos(2\pi U_{2})={\sqrt {-2\ln s}}\left({\frac {u}{\sqrt {s}}}\right)=u\cdot {\sqrt {\frac {-2\ln s}{s}}}

jeung

z_{1}={\sqrt {-2\ln U_{1}}}\sin(2\pi U_{2})={\sqrt {-2\ln s}}\left({\frac {v}{\sqrt {s}}}\right)=v\cdot {\sqrt {\frac {-2\ln s}{s}}}.

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.^[5] 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.^[6]

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

↑ G. E. P. Box and Mervin E. Müller, A Note on the Generation of Random Normal Deviates, The Annals of Mathematical Statistics (1958), Vol. 29, No. 2 pp. 610-611
↑ Kloeden and Platen, Numerical Solutions of Stochastic Differential Equations, p. 11-12
↑ Sheldon Ross, A First Course in Probability, (2002), p.279-81
↑ L. Devroye: 'Non-Uniform Random Variate Generation', Springer-Verlag, New York, 1986. Archived 2009-05-05 di Wayback Machine
↑ ^a ^b Everett F. Carter, Jr., The Generation and Application of Random Numbers, Forth Dimensions (1994), Vol. 16, No. 1 & 2.
↑ Note that the evaluation of $2\pi U_{1}$ is counted as a single multiplication because the value of $2\pi$ can be computed in advance and used repeatedly.

Tumbu luar

[1] G. E. P. Box and Mervin E. Müller, A Note on the Generation of Random Normal Deviates, The Annals of Mathematical Statistics (1958), Vol. 29, No. 2 pp. 610-611

[2] Kloeden and Platen, Numerical Solutions of Stochastic Differential Equations, p. 11-12

[3] Sheldon Ross, A First Course in Probability, (2002), p.279-81

[4] L. Devroye: 'Non-Uniform Random Variate Generation', Springer-Verlag, New York, 1986. Archived 2009-05-05 di Wayback Machine

[Carter-5] Everett F. Carter, Jr., The Generation and Application of Random Numbers, Forth Dimensions (1994), Vol. 16, No. 1 & 2.

[6] Note that the evaluation of $2\pi U_{1}$ is counted as a single multiplication because the value of $2\pi$ can be computed in advance and used repeatedly.

[1]

[2]

[3]

[4]

[5]

[6]