Box-Muller-metoden

Den Box-Muller-metoden ( George EP boks og Mervin E. Muller, 1958) består i å generere par av tilfeldige tall med redusert sentrert normalfordeling , fra en kilde for tilfeldige tall i jevn fordeling .

Transformasjonen tar ofte to former.

• Den "enkle" formen forvandler jevnt fordelte polare koordinater til normalt distribuerte kartesiske koordinater.
• Den "polare" formen forvandler kartesiske koordinater jevnt fordelt i enhetssirkelen (oppnådd ved avvisning ) til normalt distribuerte koordinater .

Den omvendte transformasjonsmetoden kan også brukes til å generere normalt fordelte tall; Box-Muller-metoden er mer presis og raskere. Vi kan også vurdere ziggurat-metoden , som er mye raskere.

Den polare metoden er den som brukes av standard C ++ - biblioteket til GCC- kompilatoren for å prøve normalfordelingsvariabler.

Skriftene

Box-Muller transformasjon

La og to tilfeldige variabler uavhengig fordelt jevnt i] 0,1]. U1{\ displaystyle U_ {1}}U2{\ displaystyle U_ {2}}

Være

Z0=Rcos⁡(Θ)=-2ln⁡U1cos⁡(2πU2){\ displaystyle Z_ {0} = R \ cos (\ Theta) = {\ sqrt {-2 \ ln U_ {1}}} \ cos (2 \ pi U_ {2}) \,}

og

Z1=Rsynd⁡(Θ)=-2ln⁡U1synd⁡(2πU2).{\ displaystyle Z_ {1} = R \ sin (\ Theta) = {\ sqrt {-2 \ ln U_ {1}}} \ sin (2 \ pi U_ {2}). \,}

Deretter Z 0 og Z 1 er uavhengige tilfeldige variabler etter en redusert sentrert normalfordeling .

Polar metode

Denne metoden, på grunn av George Marsaglia  (en) og TA Bray, er basert på følgende faktum: hvis er et punkt valgt ensartet på enhetsdisken, så er en ensartet variabel på segmentet , og et ensartet punkt på sirkelen, alt to uavhengige. Det følger av Box-Muller-transformasjonen at (X,Y){\ displaystyle (X, Y)}U=X2+Y2{\ displaystyle U = X ^ {2} + Y ^ {2}}[0,1]{\ displaystyle [0,1]}(XU,YU){\ displaystyle ({\ tfrac {X} {\ sqrt {U}}}, {\ tfrac {Y} {\ sqrt {U}}})}

Z0=X⋅-2ln⁡UU,Z1=Y⋅-2ln⁡UU{\ displaystyle Z_ {0} = X \ cdot {\ sqrt {\ frac {-2 \ ln U} {U}}}, \ quad Z_ {1} = Y \ cdot {\ sqrt {\ frac {-2 \ i U} {U}}}}

er uavhengige tilfeldige variabler som følger en redusert sentrert normalfordeling .

Paret samples etter avvisningsmetoden . Variablene og er tegnet jevnt og uavhengig på segmentet . Så beregner vi . Hvis eller , la oss avvise det og velge et par igjen , til tilhører . (X,Y){\ displaystyle (X, Y)}X{\ displaystyle X}Y{\ displaystyle Y}[-1,1]{\ displaystyle [-1,1]}U=X2+Y2{\ displaystyle U = X ^ {2} + Y ^ {2}}U≥1{\ displaystyle U \ geq 1}U=0{\ displaystyle U = 0}(X,Y){\ displaystyle (X, Y)}U{\ displaystyle U}]0,1[{\ displaystyle] 0.1 [}

Forklaringer

Begrunnelsen for denne transformasjonen kommer fra transformasjonen av sannsynligheten til normal lov til polarkoordinater:

12π2e-x2+y22dxdy=12πe-r22rdrdθ=(12e-s2ds)(12πdθ){\ displaystyle {\ frac {1} {{\ sqrt {2 \ pi}} ^ {2}}} e ^ {- {\ frac {x ^ {2} + y ^ {2}} {2}}} \, \ mathrm {d} x \, \ mathrm {d} y = {\ frac {1} {2 \ pi}} e ^ {- {\ frac {r ^ {2}} {2}}} r \ , \ mathrm {d} r \, \ mathrm {d} \ theta = \ left ({\ frac {1} {2}} e ^ {- {\ frac {s} {2}}} \ mathrm {d} s \ høyre) \ venstre ({\ frac {1} {2 \ pi}} \ mathrm {d} \ theta \ høyre)}

ved å sette s = r 2 .

Vi ser således at variablene S og Θ er uavhengige (tettheten til paret er produktet av tettheten) og følger to forskjellige lover:

• S∼E(12){\ displaystyle S \ sim {\ mathcal {E}} \ left ({\ frac {1} {2}} \ right)} : S følger en eksponentiell lov av parameter 1/2.
• Θ∼U([0;2π]){\ displaystyle \ Theta \ sim {\ mathcal {U}} \ venstre (\ venstre [0; 2 \ pi \ høyre] \ høyre)} : Θ følger en kontinuerlig enhetlig lov om .[0;2π]{\ displaystyle \ left [0; 2 \ pi \ right]}

Variabelen S genereres deretter ved hjelp av den inverse transformasjonsmetoden . Så er det bare å skrive likhetene og . x=rcos⁡θ{\ displaystyle x = r \ cos \ theta}y=rsynd⁡θ{\ displaystyle y = r \ sin \ theta}

Sammenligning mellom de to formene

Den polare metoden er en avvisningssamplingsmetode , som bare bruker en del av tallene generert av den tilfeldige kilden, men det er i praksis raskere enn Box-Muller-transformasjonen fordi det er lettere å beregne:

• den bruker ikke en trigonometrisk funksjon, som er kostbar når det gjelder beregningstid;
• genereringen av enhetlige tilfeldige tall er ganske rask, så det er ikke noe problem å kaste bort noe av det. I gjennomsnitt er andelen avviste poeng (1-π / 4) ≈ 21,46%. Vi genererer derfor i gjennomsnitt 4 / π ≈ 1.2732 enhetlige tilfeldige tall for å oppnå hvert normale tilfeldige tall.

Merknader og referanser

1. George EP Box, Mervin E. Muller, “A Note on the Generation of Random Normal Deviates”, The Annals of Mathematical Statistics Vol. 29, nr. 2 (jun. 1958), s. 610-611 DOI : 10.1214 / aoms / 1177706645 , JSTOR : 2237361
2. "  c ++ - Hvordan transformerer distribusjoner av C ++ 11-klassen den underliggende generatoren?  » , On Stack Overflow (åpnet 22. januar 2020 )
3. (in) G. Marsaglia og TA Bray , "  A Convenient Method for Generating Normal Variables  " , SIAM Review , Vol.  6, n o  3,Juli 1964, s.  260–264 ( ISSN  0036-1445 og 1095-7200 , DOI  10.1137 / 1006063 , leses online , åpnes 22. januar 2020 )
4. Devroye, Luc. , Ikke-enhetlig generasjon av tilfeldige variasjoner , Springer-Verlag ,1986, 843  s. ( ISBN  978-1-4613-8643-8 , 1-4613-8643-8 og 978-1-4613-8645-2 , OCLC  696038277 , les online ) , s.  Kapittel 5
5. Sheldon Ross, A First Course in Probability , (2002), s.279-81

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">