Box – Muller transform - Box–Muller transform

Visualisering av Box-Muller-transformasjonen - de fargede punktene i enhetsfeltet (u1, u2), tegnet som sirkler, er kartlagt til en 2D-gaussisk (z0, z1), tegnet som kryss. Tomtene ved marginene er sannsynlighetsfordelingsfunksjonene til z0 og z1. Merk at z0 og z1 er ubegrenset; de ser ut til å være i [-2.5,2.5] på grunn av valget av de illustrerte punktene. I SVG-filen holder du markøren over et punkt for å markere det og dets tilsvarende punkt.

Den Box-Muller transform , av George Edward Pelham Box og Mervin Edgar Muller , er et tilfeldig tall prøvetaking metode for generering av par av uavhengig , standard, normalfordelt (null forventning , enhet varians ) tilfeldige tall, gitt en kilde av jevnt fordelte tilfeldige tall . Metoden ble faktisk først nevnt eksplisitt av Raymond EAC Paley og Norbert Wiener i 1934.

Box-Muller-transformasjonen uttrykkes ofte i to former. Den grunnleggende skjemaet gitt av Box og Muller tar to prøver fra den jevne fordelingen i intervallet [0, 1] og kartlegger dem til to standardprøver som normalt distribueres. Polarformen tar to prøver fra et annet intervall, [−1, +1], og kartlegger dem til to normalt distribuerte prøver uten bruk av sinus- eller cosinusfunksjoner.

Box-Muller transformasjonen ble utviklet som et mer beregningseffektivt alternativ til metoden for invers transformasjon . The Ziggurat algoritme gir en mer effektiv metode for skalar-prosessorer (f.eks gammel CPU), mens den Box-Muller transform er overlegen for prosessorer med vektor-enheter (f.eks GPU'er eller moderne CPU).

Grunnleggende skjema

Anta at U ₁ og U ₂ er uavhengige prøver valgt fra den jevne fordelingen på enhetsintervallet (0, 1). La

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

og

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

Deretter Z ₀ og Z ₁ er uavhengige tilfeldige variable med en standard normalfordeling .

Utledningen er basert på en egenskap ved et to-dimensjonalt kartesisk system , hvor X- og Y-koordinatene er beskrevet ved hjelp av to uavhengige og normalfordelt tilfeldige variable, de tilfeldige variable for R ² og Θ (vist ovenfor) i de tilsvarende polarkoordinater er også uavhengig og kan uttrykkes som

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

og

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

Fordi R ² er kvadratet av normen av standard bivariate normal variabel ( X ,  Y ), har den khikvadratfordeling med to frihetsgrader. I det spesielle tilfellet med to frihetsgrader, det khikvadratfordeling faller sammen med eksponensiell fordeling , og likningen for R ² ovenfor er en enkel måte å generere de nødvendige eksponensiell variate.

Polarform

To jevnt fordelte verdier, u og v er brukt for å fremstille verdi s = R ² , som likeledes er jevnt fordelt. Definisjonene av sinus og cosinus blir deretter brukt på den grunnleggende formen for Box-Muller-transformasjonen for å unngå å bruke trigonometriske funksjoner.

Polarformen ble først foreslått av J. Bell og deretter modifisert av R. Knop. Mens flere forskjellige versjoner av den polare metoden er beskrevet, vil versjonen av R. Knop bli beskrevet her fordi den er den mest brukte, delvis på grunn av dens inkludering i Numerical Recipes .

Gitt u og v , uavhengig og jevnt fordelt i det lukkede intervallet [−1, +1], sett s = R ² = u ² + v ² . Hvis s = 0 eller s ≥ 1 , kast u og v , og prøv et annet par ( u ,  v ). Fordi u og v er jevnt fordelt og fordi bare punkter i enhetssirkelen er tillatt, vil verdiene til s også være jevnt fordelt i det åpne intervallet (0, 1). Sistnevnte kan sees ved å beregne den kumulative fordelingsfunksjonen for s i intervallet (0, 1). Dette er området til en sirkel med radius , delt på . Fra dette finner vi sannsynlighetstetthetsfunksjonen til å ha den konstante verdien 1 på intervallet (0, 1). Like så er vinkelen θ delt på jevnt fordelt i intervallet [0, 1) og uavhengig av s . ${\ displaystyle \ scriptstyle {\ sqrt {s}}}$${\ displaystyle \ scriptstyle \ pi}$${\ displaystyle \ scriptstyle 2 \ pi}$

Vi identifiserer nå verdien av s med U ₁ og med U ₂ i grunnformen. Som vist i figuren kan verdiene til og i grunnformen erstattes med forholdstallene og henholdsvis. Fordelen er at direkte beregning av trigonometriske funksjoner kan unngås. Dette er nyttig når trigonometriske funksjoner er dyrere å beregne enn den enkeltdelingen som erstatter hver enkelt. ${\ displaystyle \ scriptstyle \ theta / (2 \ pi)}$${\ displaystyle \ scriptstyle \ cos \ theta = \ cos 2 \ pi U_ {2}}$${\ displaystyle \ scriptstyle \ sin \ theta = \ sin 2 \ pi U_ {2}}$${\ displaystyle \ scriptstyle \ cos \ theta = u / R = u / {\ sqrt {s}}}$${\ displaystyle \ scriptstyle \ sin \ theta = v / R = v / {\ sqrt {s}}}$

Akkurat som grunnformen produserer to standardnormale avvik, gjør også denne alternative beregningen.

${\ displaystyle 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}}}}$

og

${\ displaystyle 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}}}.}$

Kontrasterer de to formene

Polarmetoden skiller seg fra den grunnleggende metoden ved at den er en type avvisningssampling . Det forkaster noen genererte tilfeldige tall, men kan være raskere enn den grunnleggende metoden fordi det er enklere å beregne (forutsatt at tilfeldig tallgenerator er relativt rask) og er mer numerisk robust. Å unngå bruk av dyre trigonometriske funksjoner forbedrer hastigheten i forhold til grunnformen. Den forkaster 1 - π / 4 ≈ 21,46% av det totale inngående jevnt fordelte tilfeldige antall par som genereres, dvs. kasseres 4 / π - 1 ≈ 27,32% jevnt fordelt tilfeldig antall par per Gaussisk tilfeldig tallpar generert, og krever 4 / π ≈ 1.2732 inngang tilfeldige tall per tilfeldig nummer.

Den grunnleggende formen krever to multiplikasjoner, 1/2 logaritme, 1/2 kvadratrot og en trigonometrisk funksjon for hver normale variat. På noen prosessorer kan cosinus og sinus for det samme argumentet beregnes parallelt ved hjelp av en enkelt instruksjon. Spesielt for Intel-baserte maskiner, kan man bruke de fsincos assembler instruksjon eller expi instruksjon (vanligvis tilgjengelig fra C som en iboende funksjon ), for å beregne kompleks

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

og bare skille de virkelige og imaginære delene.

Merk: For å eksplisitt beregne den komplekspolære formen, bruk følgende erstatninger i den generelle formen,

La og deretter ${\ displaystyle r = {\ sqrt {-2 \ ln (u_ {1})}}}$${\ displaystyle z = 2 \ pi u_ {2}.}$

${\ displaystyle re ^ {iz} = {\ sqrt {-2 \ ln (u_ {1})}} e ^ {i2 \ pi u_ {2}} = {\ sqrt {-2 \ ln (u_ {1} )}} \ venstre [\ cos (2 \ pi u_ {2}) + i \ sin (2 \ pi u_ {2}) \ høyre].}$

Polarformen krever 3/2 multiplikasjoner, 1/2 logaritme, 1/2 kvadratrot og 1/2 divisjon for hver normale variat. Effekten er å erstatte en multiplikasjon og en trigonometrisk funksjon med en enkelt divisjon og en betinget sløyfe.

Haler avkorting

Når en datamaskin brukes til å produsere en jevn tilfeldig variabel, vil den uunngåelig ha noen unøyaktigheter fordi det er en nedre grense for hvor nær tall kan være 0. Hvis generatoren bruker 32 bits per utgangsverdi, det minste ikke-null tallet som kan genereres er . Når og er like dette, gir Box – Muller-transformasjonen et normalt tilfeldig avvik lik . Dette betyr at algoritmen ikke vil produsere tilfeldige variabler mer enn 6.660 standardavvik fra gjennomsnittet. Dette tilsvarer en andel av tapt på grunn av avkuttingen, hvor er standard kumulativ normalfordeling. Med 64 bits skyves grensen til standardavvik, for hvilke . ${\ displaystyle 2 ^ {- 32}}$${\ displaystyle U_ {1}}$${\ displaystyle U_ {2}}$${\ displaystyle \ delta = {\ sqrt {-2 \ ln (2 ^ {- 32})}} \ cos (2 \ pi 2 ^ {- 32}) \ ca 6.660}$${\ displaystyle 2 (1- \ Phi (\ delta)) \ simeq 2.738 \ times 10 ^ {- 11}}$${\ displaystyle \ Phi (\ delta)}$${\ displaystyle \ delta = 9.419}$${\ displaystyle 2 (1- \ Phi (\ delta)) <5 \ ganger 10 ^ {- 21}}$

Gjennomføring

Standard Box – Muller transform genererer verdier fra standard normalfordeling ( dvs. standard normalavvik ) med gjennomsnitt 0 og standardavvik 1 . Implementeringen nedenfor i standard C ++ genererer verdier fra normalfordeling med gjennomsnitt og varians . Hvis er et standard normalavvik, så vil det ha en normalfordeling med gjennomsnitt og standardavvik . Merk at tilfeldige tallgenerator har blitt sådd for å sikre at nye, pseudo-tilfeldige verdier blir returnert fra sekvensielle anrop til funksjonen. ${\ displaystyle \ mu}$${\ displaystyle \ sigma ^ {2}}$${\ displaystyle Z}$${\ displaystyle X = Z \ sigma + \ mu}$${\ displaystyle \ mu}$${\ displaystyle \ sigma}$generateGaussianNoise

#include <cmath>
#include <limits>
#include <random>
#include <utility>

std::pair<double, double> generateGaussianNoise(double mu, double sigma)
{
    constexpr double epsilon = std::numeric_limits<double>::epsilon();
    constexpr double two_pi = 2.0 * M_PI;

    //initialize the random uniform number generator (runif) in a range 0 to 1
    static std::mt19937 rng(std::random_device{}()); // Standard mersenne_twister_engine seeded with rd()
    static std::uniform_real_distribution<> runif(0.0, 1.0);

    //create two random numbers, make sure u1 is greater than epsilon
    double u1, u2;
    do
    {
        u1 = runif(rng);
        u2 = runif(rng);
    }
    while (u1 <= epsilon);

    //compute z0 and 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 også

• Invers transformasjonsprøvetaking
• Marsaglia polar metode , lignende transformasjon til Box – Muller, som bruker kartesiske koordinater, i stedet for polare koordinater

Referanser

• Howes, Lee; Thomas, David (2008). GPU Gems 3 - Effektiv tilfeldig nummergenerering og applikasjon ved bruk av CUDA . Pearson Education, Inc. ISBN   978-0-321-51526-1 .

Eksterne linker

• Weisstein, Eric W. "Box-Muller Transformation" . MathWorld .
• Hvordan konvertere en enhetlig distribusjon til en gaussisk distribusjon (C-kode)