Box–Muller transformation

Visualisering av Box–Muller-transformen — de färgade punkterna i enhetskvadraten (u1, u2), ritade som cirklar, mappas till en 2D Gaussian (z0, z1), ritade som kors. Plotterna vid marginalerna är sannolikhetsfördelningsfunktionerna för z0 och z1. z0 och z1 är obundna; de verkar vara i [-2.5,2.5] på grund av valet av de illustrerade punkterna. i SVG-filen för att markera den och dess motsvarande punkt.

Box –Muller-transformen , av George Edward Pelham Box och Mervin Edgar Muller , är en slumptalssamplingsmetod för att generera par av oberoende , standard, normalfördelade (nollförväntningar , enhetsvarians ) slumptal, givet en källa till enhetligt fördelade slumptal . . Metoden nämndes faktiskt först explicit av Raymond EAC Paley och Norbert Wiener 1934.

Box-Muller-transformen uttrycks vanligtvis i två former. Grundformen som ges av Box och Muller tar två prover från den enhetliga fördelningen på intervallet [0, 1] och mappar dem till två standard, normalfördelade prov. Den polära formen tar två sampel från ett annat intervall, [−1, +1], och mappar dem till två normalfördelade sampel utan användning av sinus- eller cosinusfunktioner.

Box-Muller-transformen utvecklades som ett mer beräkningseffektivt alternativ till den inversa transformsamplingsmetoden . Ziggurat -algoritmen ger en mer effektiv metod för skalära processorer (t.ex. gamla processorer), medan Box–Muller-transformen är överlägsen för processorer med vektorenheter (t.ex. GPU:er eller moderna processorer).

Grundform

Antag att U ₁ och U ₂ är oberoende sampel valda från den enhetliga fördelningen på enhetsintervallet (0, 1). Låta

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

och

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

₀ Då är Z och Z ₁ oberoende stokastiska variabler med en standardnormalfördelning .

Härledningen är baserad på en egenskap hos ett tvådimensionellt kartesiskt system , där X- och Y-koordinater beskrivs av två oberoende och normalfördelade stokastiska variabler, de stokastiska variablerna för R ² och Θ (visas ovan) i motsvarande polära koordinater är också oberoende och kan uttryckas som

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

och

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

Eftersom R ² är kvadraten på normen för den standardmässiga bivariata normalvariabeln ( X , Y ), har den chi-kvadratfördelningen med två frihetsgrader. I specialfallet med två frihetsgrader sammanfaller chi-kvadratfördelningen med exponentialfördelningen och ekvationen för R ² ovan är ett enkelt sätt att generera den erforderliga exponentialvarianten.

Polär form

Två likformigt fördelade värden, u och v används för att producera värdet s = R ² , som likaså är likformigt fördelat. Definitionerna av sinus och cosinus tillämpas sedan på den grundläggande formen av Box–Muller-transformen för att undvika att använda trigonometriska funktioner.

Den polära formen föreslogs först av J. Bell och modifierades sedan av R. Knop. Medan flera olika versioner av den polära metoden har beskrivits kommer versionen av R. Knop att beskrivas här eftersom den är den mest använda, delvis på grund av dess inkludering i Numeriska recept .

Givet u och v , oberoende och likformigt fördelade i det slutna intervallet [−1, +1], set s = R ² = u ² + v ² . Om s = 0 eller s ≥ 1 , kasta u och v och försök med ett annat par ( u , v ). Eftersom u och v är likformigt fördelade och eftersom endast punkter inom enhetscirkeln har tillåtits, kommer värdena på s också att vara likformigt fördelade i det öppna intervallet (0, 1). Det senare kan ses genom att beräkna den kumulativa fördelningsfunktionen för s i intervallet (0, 1). Detta är arean av en cirkel med radien ${\displaystyle \scriptstyle {\sqrt {s}}} ,$ dividerat med $\scriptstyle \pi$ . Av detta finner vi att sannolikhetstäthetsfunktionen har det konstanta värdet 1 på intervallet (0, 1). Likaså är vinkeln θ dividerad med $\scriptstyle 2\pi$ jämnt fördelad i intervallet [0, 1) och oberoende av s .

Vi identifierar nu värdet på s med värdet för U ₁ och $\scriptstyle \theta /(2\pi )$ med det för U ₂ i grundformen. Som visas i figuren, värdena för $\scriptstyle \cos \theta =\cos 2\pi U_{2}$ och $\scriptstyle \sin \theta =\sin 2\pi U_{2}$ i grundformen kan ersättas med förhållandena $\scriptstyle \cos \theta =u/R=u/{\sqrt {s}}$ och $\scriptstyle \sin \theta =v/R=v/{\sqrt {s}}$ , respektive. Fördelen är att man kan undvika att beräkna de trigonometriska funktionerna direkt. Detta är användbart när trigonometriska funktioner är dyrare att beräkna än den enda divisionen som ersätter var och en.

Precis som grundformen ger två standardnormalavvikelser, så gör denna alternativa beräkning.

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}}}

och

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}}}.

Att kontrastera de två formerna

Den polära metoden skiljer sig från den grundläggande genom att den är en typ av avslagsprovtagning . Den kasserar några genererade slumptal, men kan vara snabbare än den grundläggande metoden eftersom den är enklare att beräkna (förutsatt att slumptalsgeneratorn är relativt snabb) och är mer numeriskt robust. Att undvika användningen av dyra trigonometriska funktioner förbättrar hastigheten jämfört med grundformen. Den kastar bort 1 − $π$ /4 ≈ 21,46 % ω . $av$ de totala inmatade likformigt fördelade slumptalsparen som genereras, dvs kasserar 4/ $π$ − 1 ≈ 27,32 % likformigt fördelade slumptalspar per genererat Gaussiskt slumptalspar, vilket kräver 2/732 slumptal per utgående slumptal.

Grundformen kräver två multiplikationer, 1/2 logaritm, 1/2 kvadratrot och en trigonometrisk funktion för varje normalvariant. På vissa processorer kan cosinus och sinus för samma argument beräknas parallellt med en enda instruktion. Särskilt för Intel-baserade maskiner kan man använda fsincos assembler-instruktionen eller expi-instruktionen (vanligtvis tillgänglig från C som en inneboende funktion ) för att beräkna komplex

\exp(iz)=e^{iz}=\cos z+i\sin z,\,

och bara separera de verkliga och imaginära delarna.

Obs: För att explicit beräkna den komplexa polära formen använd följande ersättningar i den allmänna formen,

Låt $r={\sqrt {-2\ln(u_{1})}}$ och $z=2\pi u_{2}.$ Sedan

re^{iz}={\sqrt {-2\ln(u_{1})}}e^{i2\pi u_{2}}={\sqrt {-2\ln(u_{1} )}}\vänster[\cos(2\pi u_{2})+i\sin(2\pi u_{2})\höger].

Den polära formen kräver 3/2 multiplikationer, 1/2 logaritm, 1/2 kvadratrot och 1/2 division för varje normalvariant. Effekten är att ersätta en multiplikation och en trigonometrisk funktion med en enkel division och en villkorsslinga.

Svans trunkering

När en dator används för att producera en enhetlig slumpmässig variabel kommer den oundvikligen att ha vissa felaktigheter eftersom det finns en nedre gräns för hur nära siffror kan vara 0. Om generatorn använder 32 bitar per utdatavärde, är det minsta icke-nolltal som kan som genereras är $2^{-32}$ . När $U_{1}$ och $U_{2}$ är lika med detta ger Box-Muller-transformen en normal slumpmässig avvikelse lika med $\delta ={\sqrt {-2\ln(2^{-32})}}\cos(2\pi 2^{-32})\approx 6.660$ . Detta innebär att algoritmen inte kommer att producera slumpvariabler mer än 6 660 standardavvikelser från medelvärdet. Detta motsvarar en andel av $2(1-\Phi (\delta ))\simeq 2,738\ gånger 10^{-11}$ förlorade p.g.a. trunkeringen, där $\Phi (\delta )$ är den kumulativa standardfördelningen. Med 64 bitar skjuts gränsen till $\delta =9,419$ standardavvikelser, för vilka $2(1-\Phi (\ delta ))<5\ gånger 10^{-21}$ .

Genomförande

0 Standard Box–Muller-transformen genererar värden från standardnormalfördelningen ( dvs standardnormalavvikelser ) med medelvärde och standardavvikelse 1 . Implementeringen nedan i standard C++ genererar värden från vilken normalfördelning som helst med medelvärde $\mu$ och varians $\sigma ^{2}$ . Om $Z$ är en standardnormalavvikelse så kommer $X=Z\sigma +\mu$ att ha en normalfördelning med medelvärde $\mu$ och standardavvikelse $\sigma$ . Slumptalsgeneratorn har såddats för att säkerställa att nya, pseudoslumpmässiga värden kommer att returneras från sekventiella anrop till funktionen generGaussianNoise .

 
 
 
 

     

        
          

    
       
       

    
      
    
    
          
    
       
      

    
           
              
              

      
 #include  <cmath>  #include  <limits>  #include  <random>  #include  <utility>  std  ::  par  <  double  ,  double  >  generGaussianNoise  (  double  mu  ,  double  sigma  )  {  constexpr  double  epsilon  =  std  ::  numeric_limits  <  double  >: :  epsilon  ();  constexpr  double  two_pi  =  2,0  *  M_PI  ;  //initiera generatorn för slumpmässiga enhetliga tal (runif) i intervallet 0 till 1  static  std  ::  mt19937  rng  (  std  ::  random_device  {}());  // Standard mersenne_twister_engine seeded med rd()  static  std  ::  uniform_real_distribution  <>  runif  (  0.0  ,  1.0  );  //skapa två slumpmässiga tal, se till att u1 är större än epsilon  double  u1  ,  u2  ;  gör  {  u1  =  runif  (  rng  );  }  while  (  u1  <=  epsilon  );  u2  =  runif  (  rng  );  //beräkna z0 och z1  auto  mag  =  sigma  *  sqrt  (  -2.0  *  log  (  u1  ));  auto  z0  =  mag  *  cos  (  two_pi  *  u2  )  +  mu  ;  auto  z1  =  mag  *  sin  (  two_pi  *  u2  )  +  mu  ;  return  std  ::  make_pair  (  z0  ,  z1  );  }

Se även

Invers transformsampling
Marsaglia polära metod , liknande transformation till Box–Muller, som använder kartesiska koordinater, istället för polära koordinater

Howes, Lee; Thomas, David (2008). GPU Gems 3 - Effektiv generering av slumptal och tillämpning med CUDA . Pearson Education, Inc. ISBN 978-0-321-51526-1 .

^ Box, GEP; Muller, Mervin E. (1958). "En anteckning om genereringen av slumpmässiga normala avvikelser" . The Annals of Mathematical Statistics . 29 (2): 610–611. doi : 10.1214/aoms/1177706645 . JSTOR 2237361 .
^ Raymond EAC Paley och Norbert Wiener Fourier förvandlar i den komplexa domänen, New York: American Mathematical Society (1934) §37.
^ Kloeden och Platen, Numeriska lösningar av stokastiska differentialekvationer, s. 11–12
^ Howes & Thomas 2008 .
^ Sheldon Ross, A First Course in Probability , (2002), s. 279–281
^ ^a ^b Bell, James R. (1968). "Algorithm 334: Normal slumpmässig avvikelse" . Kommunikation från ACM . 11 (7): 498. doi : 10.1145/363397.363547 .
^ Knop, R. (1969). "Anmärkning om algoritm 334 [G5]: Normal slumpmässig avvikelse" . Kommunikation från ACM . 12 (5): 281. doi : 10.1145/362946.362996 .
^ Everett F. Carter jr., Generationen och tillämpningen av slumpmässiga siffror , Forth Dimensions (1994), Vol. 16, nr 1 och 2.
^ Utvärderingen av 2 $π$ U ₁ räknas som en multiplikation eftersom värdet på 2 $π$ kan beräknas i förväg och användas upprepade gånger.

externa länkar

[1] Box, GEP; Muller, Mervin E. (1958). "En anteckning om genereringen av slumpmässiga normala avvikelser" . The Annals of Mathematical Statistics . 29 (2): 610–611. doi : 10.1214/aoms/1177706645 . JSTOR 2237361 .

[2] Raymond EAC Paley och Norbert Wiener Fourier förvandlar i den komplexa domänen, New York: American Mathematical Society (1934) §37.

[3] Kloeden och Platen, Numeriska lösningar av stokastiska differentialekvationer, s. 11–12

[4] Howes & Thomas 2008 .

[5] Sheldon Ross, A First Course in Probability , (2002), s. 279–281

[Bell68-6] Bell, James R. (1968). "Algorithm 334: Normal slumpmässig avvikelse" . Kommunikation från ACM . 11 (7): 498. doi : 10.1145/363397.363547 .

[7] Knop, R. (1969). "Anmärkning om algoritm 334 [G5]: Normal slumpmässig avvikelse" . Kommunikation från ACM . 12 (5): 281. doi : 10.1145/362946.362996 .

[Carter-8] Everett F. Carter jr., Generationen och tillämpningen av slumpmässiga siffror , Forth Dimensions (1994), Vol. 16, nr 1 och 2.

[9] Utvärderingen av 2 $π$ U ₁ räknas som en multiplikation eftersom värdet på 2 $π$ kan beräknas i förväg och användas upprepade gånger.