Polar-Methode

Die Polar-Methode von George Marsaglia und Thomas A. Bray ist ein Verfahren zur Erzeugung normalverteilter Zufallszahlen (Zufallszahlengenerator).

Geschichte

Diese Methode geht zurück auf den Box-Muller-Algorithmus zur Erzeugung normalverteilter Zufallsgrößen. Bei diesem werden die euklidischen Koordinaten verwertet. Bei der Polar-Methode werden diese euklidischen Koordinaten in Polarkoordinaten umgewandelt. Das erspart die Auswertung von trigonometrischen Funktionen.

Beschreibung

Man geht von zufälligen Punkten in der Ebene aus, die im Einheitskreis gleichverteilt sind. Aus deren Koordinaten werden jeweils zwei standardnormalverteilte Zufallszahlen erzeugt:

1. Erzeuge zwei voneinander unabhängige, gleichverteilte Zufallszahlen $u$, $v$ im Intervall $[-1,1]$
2. Berechne $q=u^{2}+v^{2}$. Falls $q=0$ oder $q\geq 1$, gehe zurück zu Schritt 1.
3. Berechne $p={\sqrt {\frac {-2\cdot \ln q}{q}}}$.
4. $x_{1}=u\cdot p$ und $x_{2}=v\cdot p$ sind nun zwei voneinander unabhängige, standardnormalverteilte Zufallszahlen.

Der Punkt $(u,v)$ muss im Einheitskreis liegen ($q<1$), und es muss $q>0$ gelten, da in den reellen Zahlen der Logarithmus von Null und die Division durch Null nicht definiert sind. Anderenfalls müssen zwei neue Zahlen $u$ und $v$ erzeugt werden.

Durch lineare Transformation lassen sich hieraus beliebige normalverteilte Zufallszahlen erzeugen: Die generierten Werte $x_{i}$ sind ${\mathcal {N}}(0,1)$-verteilt, somit liefert $a\cdot x_{i}+b$ Werte, die ${\mathcal {N}}(b,a^{2})$-verteilt sind.

Implementierung

Pseudocode

Prozedur ErzeugeNormalverteilteZufallszahlen (Referenzparameter x1, x2)
  Wiederhole
    u = 2 * Zufallszahl - 1  // "Zufallszahl" liefert in [0,1)
    v = 2 * Zufallszahl - 1  //   gleichverteilte Werte
    q = u * u + v * v
  Solange bis (0 < q) und (q < 1)
  p = Wurzel (-2 * ln(q) / q)
  x1 = u * p
  x2 = v * p  // Rückgabe durch die Referenzparameter x1, x2
Ende

C++

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

#include <iostream>
using namespace std;

// Diese Funktion berechnet eine standardnormalverteilte Zufallszahl
double generateGaussian(double mu, double sigma)
{
    double u, v, q, p; // Deklaration der lokalen Variablen
    do // Diese do-while-Schleife erzeugt Zufallszahlen u und v im Intervall [-1, 1] mit 0 < u² + v² < 1
    {
        u = (rand() / ((double)RAND_MAX)) * 2 - 1;
        v = (rand() / ((double)RAND_MAX)) * 2 - 1;
        q = u * u + v * v;
    } while (q >= 1 || q == 0);
    p = sqrt(-2 * log(q) / q);
    return mu + sigma * u * p;
}

// 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 standardnormalverteilte Zufallszahlen und gibt sie auf der Konsole aus
    {
        double gaussian = generateGaussian(mu, sigma); // Aufruf der Funktion
        cout << gaussian << endl; // Ausgabe auf der Konsole
    }
}

Siehe auch

• Erzeugung normalverteilter Zufallszahlen

Literatur

• G. Marsaglia, T. A. Bray: A Convenient Method For Generating Normal Variables. In: SIAM Review, Vol. 6, No. 3, Juli 1964, S. 260–264