imported>SweetWood: Wikicode optimiert; Wikilink eingefügt; (TeX-)Formelsatz optimiert; Tippfehler behoben; Abschnitt „Weblinks“ eingefügt

2025-06-28T15:07:29Z

Wikicode optimiert; Wikilink eingefügt; (TeX-)Formelsatz optimiert; Tippfehler behoben; Abschnitt „Weblinks“ eingefügt

Neue Seite

[[Datei:Box Muller.svg|mini|160px|Grafische Veranschaulichung der Box-Muller-Methode]]
Die '''Box-Muller-Methode''' (nach [[George Edward Pelham Box]] und [[Mervin Edgar Muller]] 1958) ist ein Verfahren zur Erzeugung [[Normalverteilung|normalverteilter]] [[Zufallszahl]]en.

== Definition ==
[[Datei:Box-Muller transform visualisation.svg|mini|Visualisierung der Box-Muller-Methode. Die farbigen Punkte des [[Einheitsquadrat]]s (''u''1, ''u''2), die als Kreise gezeichnet werden, werden einem Punkt in der [[Komplexe Zahlenebene|komplexen Zahlenebene]] zugeordnet, das als Kreuze gezeichnet ist. Die Darstellungen an den Rändern sind die [[Wahrscheinlichkeitsverteilung|Wahrscheinlichkeitsverteilungen]] von ''z''0 und ''z''1.]]
Bei dieser Methode werden zunächst zwei unabhängige [[Standardzufallszahl]]en <math>u_1</math> und <math>u_2</math> benötigt. Diese lassen sich beispielsweise mit einem [[Zufallszahlengenerator]] erzeugen. Standardzufallszahlen unterliegen einer [[Rechteckverteilung]] mit den Parametern <math>0</math> und <math>1</math>.

Es lässt sich zeigen, dass man nach folgendem Transformationsschritt daraus zwei [[Standardnormalverteilung|standardnormalverteilte]] (stochastisch) unabhängige Zufallszahlen <math>z_0</math> und <math>z_1</math> erhält:

:<math>z_0 = \sqrt{-2 \ln u_1} \cos ( 2 \pi u_2 )</math>

und

:<math>z_1 = \sqrt{-2 \ln u_1} \sin ( 2 \pi u_2 )</math>.

Schreibt man das [[Geordnetes Paar|Paar]] <math>(z_ 0, z_1)</math> in [[Polarkoordinate]]n, also

:<math>z_0 = r \cos \varphi</math> und <math>z_1 = r \sin \varphi</math>,

dann gilt:

:<math>r = \sqrt{-2 \ln u_1}\ </math> und <math>\varphi = 2 \pi u_2</math>.

Anwendung der [[Inversionsmethode]] zur Transformation von <math>u_1</math> und <math>u_2</math> in die Polarkoordinaten <math>r</math> und <math>\varphi</math> zeigt, dass <math>\varphi</math> einer [[Rechteckverteilung]] mit den Parametern <math>0</math> und <math>2 \pi</math> unterliegt und <math>r^2</math> einer [[Exponentialverteilung]] mit dem Parameter <math>\tfrac{1}{2}</math>. Aus diesem Ergebnis lässt sich die [[Gemeinsame Verteilung von Zufallsvariablen|gemeinsame Verteilung]] von <math>z_ 1</math> und <math>z_2</math> herleiten. Sie beruht auf der Beziehung:

:<math>\tfrac 12e^{-\frac 12 r^2}\mathrm{d}(r^2)\tfrac{1}{2\pi}\mathrm{d}\varphi=\tfrac{1}{2\pi}e^{-\frac 12 r^2}r\mathrm{d}r\mathrm{d}\varphi=\tfrac{1}{2\pi}e^{-\frac 12 (z_0^2+z_1^2)}\mathrm{d}z_0\mathrm{d}z_1</math>

Die bisherigen Transformationsschritte erzeugen zwei standardnormalverteilte Zufallszahlen. Eine Standardnormalverteilung ist ein Spezialfall der [[Normalverteilung]], nämlich mit dem [[Erwartungswert]] <math>\mu = 0</math> und der [[Varianz (Stochastik)|Varianz]] <math>\sigma^2 = 1</math>.

Um mit der Box-Muller-Methode Normalverteilungen mit beliebigen Parametern zu erzeugen, lassen sich die erhaltenen <math>z_i</math> nach dem Muster

:<math>x_i = \mu + \sigma\cdot z_i</math>

transformieren. In der obigen Notation steht <math>\pi</math> wie üblich für die [[Kreiszahl]], <math>\sin</math> für den [[Sinus]], <math>\cos</math> für den [[Kosinus]] und <math>\ln</math> für den [[natürlicher Logarithmus|natürlichen Logarithmus]].

Verwendet man zur Erzeugung der <math>u_i</math> einen [[Linearer Kongruenzgenerator|linearen Kongruenzgenerator]], so liegen die Paare <math>(z_0, z_1)</math> auf einer durch eine Spirale beschriebenen Kurve. Dieses Verhalten ist eng mit dem im [[Satz von Marsaglia]] beschriebenen [[Hyperebene]]nverhalten linearer Kongruenzgeneratoren verwandt.

Dieses Problem lässt sich umgehen, wenn statt des linearen Kongruenzgenerators ein [[inverser Kongruenzgenerator]] oder die [[Polar-Methode]] verwendet wird.

Die Box-Muller-Methode erzeugt zunächst zwei stochastisch unabhängige und standardnormalverteilte [[Zufallszahl]]en, die sich dann in eine [[Normalverteilung]] mit beliebigen Parametern transformieren lassen. Die Box-Muller-Methode erfordert die Auswertung von [[Logarithmus|Logarithmen]] und [[Trigonometrische Funktion|trigonometrischen Funktionen]], was auf einigen Rechnern sehr zeitaufwendig sein kann.

Weitere Möglichkeiten zur Erzeugung normalverteilter [[Zufallszahl]]en sind im Artikel [[Normalverteilung]] beschrieben. Eine Alternative ist z. B. die [[Polar-Methode]].<ref>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.</ref>

== 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 [[Zufallszahl]]en aus jeder [[Normalverteilung]] mit Erwartungswert <math>\mu</math> und [[Varianz (Stochastik)|Varianz]] <math>\sigma</math> und gibt sie auf der Konsole aus.
<syntaxhighlight lang="c++">
#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);
} while (u1 <= epsilon);
u2 = runif(rng);

// 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 standardnormalverteilten 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
}
}
</syntaxhighlight>

== Weblinks ==
* {{MathWorld|id=Box-MullerTransformation|title=Box-Muller Transformation}}

== 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 ==
<references />

[[Kategorie:Pseudozufallszahlengenerator]]

Box-Muller-Methode - Versionsgeschichte

imported>SweetWood: Wikicode optimiert; Wikilink eingefügt; (TeX-)Formelsatz optimiert; Tippfehler behoben; Abschnitt „Weblinks“ eingefügt