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. Dadurch spart man sich 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$, Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle v} im Intervall Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle [-1, 1]}
2. Berechne Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q=u^2+v^2} . Falls Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q = 0} oder $q\geq 1$, gehe zurück zu Schritt 1.
3. Berechne Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p = \sqrt {\frac{-2 \cdot \ln q}{q}}} .
4. Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_1=u \cdot p} und $x_{2}=v\cdot p$ sind nun zwei voneinander unabhängige, standardnormalverteilte Zufallszahlen.

Der Punkt Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle (u,v)} muss im Einheitskreis liegen ($q<1$), und es muss Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle u} und $v$ erzeugt werden.

Durch lineare Transformation lassen sich hieraus beliebige normalverteilte Zufallszahlen erzeugen: Die generierten Werte Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_i} sind Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathcal{N}(0,1)} -verteilt, somit liefert Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle a\cdot x_{i}+b} Werte, die Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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.

#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