Transformasi Box-Muller

Ti Wikipédia, énsiklopédia bébas
Luncat ka: pituduh, sungsi
Diagram transformasi Box Müller. Buleudan kahiji, ruang sawanda asli, dipetakeun kana runtuyan sawanda sejen numana asli ieu raket jeung rohanganna ngan kasebar sacara gancang. Buleudan gede nyaeta peta keur sakabeh buleudan nu leutik tur sabalikna.

Transformasi Box-Müller (diwanohkeun ku George Edward Pelham Box jeung Mervin Edgar Müller 1958)[1] nyaeta metoda 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 nyaeta dijentrekeun 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 beda, [−1, +1], terus dipetakuen kana dua sampel sebaran normal tur teu make fungsi sinus atawa kosinus.

Nu hiji kudu make metoda sampling transformasi invers keur ngarundaykeun wilangan acak sebaran-normal; tansformasi Box-Müller geus diwangun dina metoda komputasi nu leuwih efektif.[2] Salian ti eta, algoritma Ziggurat oge bisa dipake.

Wanda dasar[édit | sunting sumber]

Anggap U1 jeung U2 ngarupakeun 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 Z0 jeung Z1 nyaeta 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 numana kordinat X jeung Y dijentrekeun ku dua variabel mandiri tur mibanda sebaran normal, variabel acak keur R2 jeung Θ (ditembongkeun di luhur) nu pakait jeung sistim kordinat polar oge mandiri tur dijentrekeun salaku

R^2 = -2\cdot\ln U_1\,

jeung

\Theta = 2\pi U_2.\,

Wanda polar[édit | sunting sumber]

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 oge dianggap bari teu ditambahkeun dina Carter.[5]

Ditangtukeun u jeung v, mandiri tur kasebar seragam dina interval nu deukeut [−1, +1], tina susunan s = R2 = u2 + v2. (Jelasna \scriptstyle R = \sqrt{s}.) Lamun s = 0 atawa s > 1, kaluarkeun u jeung v sarta coba pasangan sejen (uv). 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) oge. 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 ngabogaan nilai angger hiji dina interval (0, 1). Sarua jeung sudut θ dibagi \scriptstyle 2 \pi katempo jentre kasebar sargam dina interval nu kabuka (0, 1) jeung s nu mandiri.

Saterusna nangtukeun nilai s numana U1 jeung \scriptstyle \theta/(2 \pi) sarta U2 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 nyaeta itungan fungsi trigonometri bisa langsung dipake. Hal ieu kacida ngabantu lamun ngabandingkeun leuwih loba bagian tur digantikeun ku nu sejenna .

Saperti wanda dasar ngahasilkeun dua simpangan normal standar, mangka hal ieu ngarupakeun alternatif itungan sejen.

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[édit | sunting sumber]

Metoda polar beda jeung metoda dasar nyaeta dina nolak nyokot sampel. Cara nyokotna sababara rundayan wilangan normal, sacara tipikal leuwih gancang tinimbanf metoda dasar, hal ieu sabab cara ngitungna nu leuwih sederhana (geus ditembongkeun yen ngarundaykeun wilangan acak leuwih gancang) sarta sacara numerik leuwih tegep.[5] Hal ieu bisa ngagunakeun fungsi trigonometri, numana mindeng dipake dina kaperluan komputasi. Ieu nyokot 1 − π/4 ≈ 21.46% tina sakabeh 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 proses kakalian, hiji logaritma, hiji akar kuadrat sarta tilu fungsi trigonometri keur unggal variasi normal.[6]

Wanda polar merlukeun dua kali proses 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[édit | sunting sumber]

Rujukan[édit | sunting sumber]

  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.
  5. a b 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.

Tumbu luar[édit | sunting sumber]