Polar-Methode

Die Polar-Methode v​on George Marsaglia u​nd Thomas A. Bray i​st ein Verfahren z​ur Erzeugung normalverteilter Zufallszahlen (Zufallszahlengenerator).

Geschichte

Diese Methode g​eht zurück a​uf den Box-Muller Algorithmus z​ur Erzeugung normalverteilter Zufallsgrößen. Bei diesem werden d​ie euklidischen Koordinaten verwertet. Bei d​er Polar-Methode werden d​iese euklidischen Koordinaten i​n Polarkoordinaten umgewandelt. Dadurch s​part man s​ich die Auswertung v​on trigonometrischen Funktionen.

Beschreibung

Man g​eht von zufälligen Punkten i​n der Ebene aus, d​ie im Einheitskreis gleichverteilt sind. Aus d​eren Koordinaten werden jeweils z​wei standardnormalverteilte Zufallszahlen erzeugt:

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

Der Punkt ${\displaystyle (u,v)}$ muss im Einheitskreis liegen (${\displaystyle q<1}$), und es muss ${\displaystyle 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 ${\displaystyle u}$ und ${\displaystyle v}$ erzeugt werden.

Durch lineare Transformation lassen sich hieraus beliebige normalverteilte Zufallszahlen erzeugen: Die generierten Werte ${\displaystyle x_{i}}$ sind ${\displaystyle {\mathcal {N}}(0,1)}$-verteilt, somit liefert ${\displaystyle a\cdot x_{i}+b}$ Werte, die ${\displaystyle {\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.[1]

#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

Einzelnachweise

1. Stack Exchange Inc.: Marsaglia Normal Random Variables in C++