Box-Muller-Methode

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Graphische Veranschaulichung der Box-Muller-Methode

Die Box-Muller-Methode (nach George Edward Pelham Box und Mervin Edgar Muller 1958) ist ein Verfahren zur Erzeugung normalverteilter Zufallszahlen.

Erzeugung standardnormalverteilter Zufallszahlen[Bearbeiten]

Bei dieser Methode werden zunächst zwei unabhängige Standardzufallszahlen u_1 und u_2 benötigt. Diese lassen sich beispielsweise mit einem Zufallszahlengenerator erzeugen. Standardzufallszahlen unterliegen einer Rechteckverteilung mit den Parametern 0 und 1.

Es lässt sich zeigen, dass man nach folgendem Transformationsschritt daraus zwei standardnormalverteilte (stochastisch) unabhängige Zufallszahlen z_1 und z_2 erhält:

z_1 = \sqrt{-2 \ln u_1} \cos ( 2 \pi u_2 )

und

z_2 = \sqrt{-2 \ln u_1} \sin ( 2 \pi u_2 ).

Schreibt man das Paar \!\,(z_ 1, z_2) mit Polarkoordinaten, also

\!\,z_1 = r \cos \varphi und \!z_2 = r \sin \varphi,

dann gilt:

\!\, r = \sqrt{-2 \ln u_1}\ und \!\; \varphi = 2 \pi u_2.

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

\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_1^2+z_2^2)}\mathrm{d}z_1\mathrm{d}z_2


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

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

x_i = \mu + \sigma\,z_i

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

Probleme[Bearbeiten]

Verwendet man zur Erzeugung der u_i einen linearen Kongruenzgenerator, so liegen die Paare ( z_1 ; z_2 ) 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 sich umgehen, wenn statt des linearen Kongruenzgenerators ein inverser Kongruenzgenerator oder die Polar-Methode verwendet wird.

Fazit[Bearbeiten]

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

Alternativen[Bearbeiten]

Weitere Möglichkeiten zur Erzeugung normalverteilter Zufallszahlen sind im Artikel Normalverteilung beschrieben. Eine Alternative ist z.B. die Polar-Methode.[1]

Quellen und Fußnoten[Bearbeiten]

  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.

Literatur[Bearbeiten]