Box-Muller módszer

A Box-Muller módszer ( George EP Box és Mervin E. Muller, 1958) abból áll, hogy véletlenszám- párokat állít elő csökkentett központú normális eloszlású , egyenletes eloszlású véletlenszám- forrásból .

Az átalakulás általában két formát ölthet.

• Az "egyszerű" forma az egyenletesen elosztott poláris koordinátákat normál eloszlású derékszögű koordinátákká alakítja.
• A „poláris” forma az egységkörben ( elutasítással kapott ) egyenletesen elosztott derékszögű koordinátákat alakítja át normálisan elosztott koordinátákká .

Az inverz transzformációs módszer normálisan elosztott számok előállítására is használható ; a Box-Muller módszer pontosabb és gyorsabb. Fontolóra vehetjük a ziggurat módszert is , amely sokkal gyorsabb.

A poláris módszert a GCC fordító standard C ++ könyvtárában használják a normál eloszlású változók mintavételére.

Szentírás

Box-Muller transzformáció

Let és két véletlen változó független egyenletesen elosztva] 0,1]. U1{\ displaystyle U_ {1}}U2{\ displaystyle U_ {2}}

Lenni

Z0=Rkötözősaláta⁡(Θ)=-2ln⁡U1kötözősaláta⁡(2πU2){\ displaystyle Z_ {0} = R \ cos (\ Theta) = {\ sqrt {-2 \ ln U_ {1}}} \ cos (2 \ pi U_ {2}) \,}

és

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

Ekkor Z 0 és Z 1 független véletlen változó a csökkent középpontú normális eloszlás után .

Poláris módszer

Ez a módszer George Marsaglia  (en) és TA Bray miatt a következő tényen alapul: ha egy pontot egységesen választanak az egységlemezre, akkor a szegmensben egy változó és a körön egy egységes pont van kettő független. A Box-Muller-transzformáció következtében ez (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 \ Un {U}}}}

független, véletlenszerű változók, csökkent középpontú normális eloszlást követve .

A párból mintát vesznek az elutasítási módszerrel . A változók és a dolgozzák egyenletesen és egymástól függetlenül a szegmensben . Aztán kiszámoljuk . Ha vagy , akkor utasítsuk el, és válasszunk újra egy párat , amíg az nem tartozik . (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 [}

Magyarázatok

Ennek az átalakításnak az igazolása a normális törvény valószínűségi mértékének poláris koordinátákká történő átalakításából származik :

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 = \ balra ({\ frac {1} {2}} e ^ {- {\ frac {s} {2}}} \ mathrm {d} s \ right) \ left ({\ frac {1} {2 \ pi}} \ mathrm {d} \ theta \ right)}

az s = r 2 beállításával .

Így láthatjuk, hogy az S és Θ változók függetlenek (a pár sűrűsége a sűrűségek szorzata), és két különböző törvényt követnek:

• S∼E(12){\ displaystyle S \ sim {\ mathcal {E}} \ balra ({\ frac {1} {2}} \ jobbra)} : S az 1/2 paraméter exponenciális törvényét követi .
• Θ∼U([0;2π]){\ displaystyle \ Theta \ sim {\ mathcal {U}} \ left (\ left [0; 2 \ pi \ right] \ right)} : Θ követ folytonos egyenletes törvény az .[0;2π]{\ displaystyle \ left [0; 2 \ pi \ right]}

Ezután az S változót inverz transzformációs módszerrel állítják elő . Akkor csak írja be az egyenlőségeket és . x=rkötözősaláta⁡θ{\ displaystyle x = r \ cos \ theta}y=rbűn⁡θ{\ displaystyle y = r \ sin \ theta}

A két forma összehasonlítása

A poláris módszer egy elutasító mintavételi módszer , amely csak a véletlenszerű forrás által generált számok egy részét használja, de a gyakorlatban gyorsabb, mint a Box-Muller transzformáció, mert könnyebb kiszámítani:

• nem használ trigonometrikus függvényt, amely költséges az idő kiszámításához;
• az egységes véletlenszámok generálása meglehetősen gyors, ezért nem probléma elpazarolni egy részét. Átlagosan az elutasított pontok aránya (1-π / 4) ≈ 21,46%. Ezért átlagosan 4 / π ≈ 1,2732 egységes véletlen számot generálunk az egyes normál véletlenszámok megszerzéséhez.

Megjegyzések és hivatkozások

1. George EP Box, Mervin E. Muller, „A Note on the Random Normal Deviates Generation”, The Annals of Mathematical Statistics Vol. 29. szám, 2. szám (1958. jún.), Pp. 610-611 DOI : 10,1214 / aoms / 1177706645 , JSTOR : 2237361
2. "  c ++ - Hogyan alakítják a C ++ 11 osztály eloszlásai az alapgenerátort?  » , On Stack Overflow (hozzáférés : 2020. január 22. )
3. (in) G. Marsaglia és TA Bray , "  Kényelmes módszer normál változók létrehozására  " , SIAM Review , 1. évf.  6, n o  3,1964. július, P.  260–264 ( ISSN  0036-1445 és 1095-7200 , DOI  10.1137 / 1006063 , online olvasás , hozzáférés : 2020. január 22. )
4. Devroye, Luc. , Nem egységes véletlenszerű variáns generáció , Springer-Verlag ,1986, 843  p. ( ISBN  978-1-4613-8643-8 , 1-4613-8643-8 és 978-1-4613-8645-2 , OCLC  696.038.277 , olvasható online ) , p.  5. fejezet
5. Sheldon Ross, A valószínűség első tanfolyama (2002), 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;">