Box-Muller-Methode - LinkFang.de





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

Bei dieser Methode werden zunächst zwei unabhängige Standardzufallszahlen [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 standardnormalverteilte (stochastisch) unabhängige Zufallszahlen [math]z_1[/math] und [math]z_2[/math] erhält:

[math]z_1 = \sqrt{-2 \ln u_1} \cos ( 2 \pi u_2 )[/math]

und

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

Schreibt man das Paar [math]\!\,(z_ 1, z_2)[/math] mit Polarkoordinaten, also

[math]\!\,z_1 = r \cos \varphi[/math] und [math]\!z_2 = 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 [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_1^2+z_2^2)}\mathrm{d}z_1\mathrm{d}z_2[/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 [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\,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ürlichen Logarithmus.

Probleme

Verwendet man zur Erzeugung der [math]u_i[/math] einen linearen Kongruenzgenerator, so liegen die Paare [math]( z_1 ; z_2 )[/math] 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

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

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

  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


Kategorien: Pseudozufallszahlengenerator

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Box-Muller-Methode (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.