Box-Muller-Methode

Die Box-Muller-Methode (nach George Edward Pelham Box u​nd Mervin Edgar Muller 1958) i​st ein Verfahren z​ur Erzeugung normalverteilter Zufallszahlen.

Graphische Veranschaulichung der Box-Muller-Methode

Definition

Visualisierung der Box-Muller-Methode. Die farbigen Punkte des Einheitsquadrats (u₁, u₂), die als Kreise gezeichnet werden, werden einem Punkt in der komplexen Zahlenebene zugeordnet, das als Kreuze gezeichnet ist. Die Darstellungen an den Rändern sind die Wahrscheinlichkeitsverteilungen von z₀ und z₁.

Bei dieser Methode werden zunächst zwei unabhängige Standardzufallszahlen ${\displaystyle u_{1}}$ und ${\displaystyle u_{2}}$ benötigt. Diese lassen sich beispielsweise mit einem Zufallszahlengenerator erzeugen. Standardzufallszahlen unterliegen einer Rechteckverteilung mit den Parametern und ${\displaystyle 1}$.

Es lässt sich zeigen, dass man nach folgendem Transformationsschritt daraus zwei standardnormalverteilte (stochastisch) unabhängige Zufallszahlen ${\displaystyle z_{0}}$ und ${\displaystyle z_{1}}$ erhält:

${\displaystyle z_{0}={\sqrt {-2\ln u_{1}}}\cos(2\pi u_{2})}$

und

${\displaystyle z_{1}={\sqrt {-2\ln u_{1}}}\sin(2\pi u_{2})}$.

Schreibt man das Paar ${\displaystyle (z_{0},z_{1})}$ mit Polarkoordinaten, also

${\displaystyle z_{0}=r\cos \varphi }$ und ${\displaystyle z_{1}=r\sin \varphi }$,

dann gilt:

${\displaystyle r={\sqrt {-2\ln u_{1}}}\ }$ und ${\displaystyle \varphi =2\pi u_{2}}$.

Anwendung der Inversionsmethode zur Transformation von ${\displaystyle u_{1}}$ und ${\displaystyle u_{2}}$ in die Polarkoordinaten ${\displaystyle r}$ und ${\displaystyle \varphi }$ zeigt, dass ${\displaystyle \varphi }$ einer Rechteckverteilung mit den Parametern und ${\displaystyle 2\pi }$ unterliegt und ${\displaystyle r^{2}}$ einer Exponentialverteilung mit dem Parameter ${\displaystyle {\tfrac {1}{2}}}$. Aus diesem Ergebnis lässt sich die gemeinsame Verteilung von ${\displaystyle z_{1}}$ und ${\displaystyle z_{2}}$ herleiten. Sie beruht auf der Beziehung:

${\displaystyle {\tfrac {1}{2}}e^{-{\frac {1}{2}}r^{2}}\mathrm {d} (r^{2}){\tfrac {1}{2\pi }}\mathrm {d} \varphi ={\tfrac {1}{2\pi }}e^{-{\frac {1}{2}}r^{2}}r\mathrm {d} r\mathrm {d} \varphi ={\tfrac {1}{2\pi }}e^{-{\frac {1}{2}}(z_{0}^{2}+z_{1}^{2})}\mathrm {d} z_{0}\mathrm {d} z_{1}}$

Die bisherigen Transformationsschritte erzeugen zwei standardnormalverteilte Zufallszahlen. Eine Standardnormalverteilung ist ein Spezialfall der Normalverteilung, nämlich mit dem Erwartungswert ${\displaystyle \mu =0}$ und der Varianz ${\displaystyle \sigma ^{2}=1}$.

Um mit der Box-Muller-Methode Normalverteilungen mit beliebigen Parametern zu erzeugen, lassen sich die erhaltenen ${\displaystyle z_{i}}$ nach dem Muster

${\displaystyle x_{i}=\mu +\sigma \cdot z_{i}}$

transformieren. In der obigen Notation steht ${\displaystyle \pi }$ wie üblich für die Kreiszahl, ${\displaystyle \sin }$ für den Sinus, ${\displaystyle \cos }$ für den Kosinus und ${\displaystyle \ln }$ für den natürlichen Logarithmus.

Verwendet man zur Erzeugung der ${\displaystyle u_{i}}$ einen linearen Kongruenzgenerator, so liegen die Paare ${\displaystyle (z_{0},z_{1})}$ auf einer durch eine Spirale beschriebenen Kurve. Dieses Verhalten ist eng mit dem im Satz von Marsaglia beschriebenen Hyperebenenverhalten linearer Kongruenzgeneratoren verwandt.

Dieses Problem lässt s​ich umgehen, w​enn statt d​es linearen Kongruenzgenerators e​in inverser Kongruenzgenerator o​der die Polar-Methode verwendet wird.

Die Box-Muller-Methode erzeugt zunächst z​wei stochastisch unabhängige u​nd standardnormalverteilte Zufallszahlen, d​ie sich d​ann in e​ine Normalverteilung m​it beliebigen Parametern transformieren lassen. Die Box-Muller-Methode erfordert d​ie Auswertung v​on Logarithmen u​nd trigonometrischen Funktionen, w​as auf einigen Rechnern s​ehr zeitaufwendig s​ein kann.

Weitere Möglichkeiten z​ur Erzeugung normalverteilter Zufallszahlen s​ind im Artikel Normalverteilung beschrieben. Eine Alternative i​st z. B. d​ie Polar-Methode.[1]

Programmierung

Die Standard-Box-Muller-Methode erzeugt Werte aus der Standardnormalverteilung mit Erwartungswert 0 und Standardabweichung 1. Die folgende Implementierung in der Programmiersprache C++ generiert 10 Paare von standardnormalverteilten Zufallszahlen aus jeder Normalverteilung mit Erwartungswert μ und Varianz σ und gibt sie auf der Konsole aus.

#define _USE_MATH_DEFINES
#include <random>
#include <iostream>
using namespace std;

// Diese Funktion berechnet zwei standardnormalverteilte Zufallszahlen z0 und z1
pair<double, double> generateGaussianNoise(double mu, double sigma)
{
    constexpr double epsilon = numeric_limits<double>::epsilon();

    // Initialisiert den Zufallszahlengenerator im Bereich von 0 bis 1
    static mt19937 rng(random_device{}()); // Standard Mersenne-Twister
    static uniform_real_distribution<> runif(0, 1);

    double u1, u2; // Deklaration der lokalen Variablen für die Zufallszahlen u1 und u2
    do // Diese do-while-Schleife erzeugt solange Zufallszahlen bis u1 > epsilon ist
    {
        u1 = runif(rng);
        u2 = runif(rng);
    } while (u1 <= epsilon);

    // Berechnet z0 und z1
    auto magnitude = sigma * sqrt(-2.0 * log(u1));
    auto z0 = magnitude * cos(2.0 * M_PI * u2) + mu;
    auto z1 = magnitude * sin(2.0 * M_PI * u2) + mu;
    return make_pair(z0, z1);
}

// Hauptfunktion die das Programm ausführt
void main()
{
    double mu = 0; // Deklaration der lokalen Variablen
    double sigma = 1;
    for (int i = 0; i < 10; i++) // Diese for-Schleife berechnet 10 Paare von standardnormalverteilte Zufallszahlen und gibt sie auf der Konsole aus
    {
        pair<double, double> gaussianNoise = generateGaussianNoise(mu, sigma); // Aufruf der Funktion
        cout << gaussianNoise.first << "," << gaussianNoise.second << endl; // Ausgabe auf der Konsole
    }
}

Literatur

• George Edward Pelham Box, Mervin Edgar Muller: A note on the generation of random normal deviates. In: Annals of Mathematical Statistics, Jg. 29 (1958), Heft 2, ISSN 0003-4851, S. 610–611.
• Donald Ervin Knuth: The Art of Computer Programming, Sec. 3.4.1, S. 117.
• Otto Moeschlin, Eugen Grycko, Claudia Pohl, Frank Steinert: Kapitel 1.4 Generating Sample Values. In: Diess.: Experimental Stochastics. Springer, Berlin u. a. 1998, ISBN 3-540-14619-9.

Einzelnachweise

1. Vgl. Albert J. Kinderman und John G. Ramage: Computer Generation of Normal Random Numbers. In: Journal of the American Statistical Association, Jg. 71 (1976), Heft 356, S. 893–896.