Box-Muller-Algorithmus

Box-Muller-Algorithmus
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.

Inhaltsverzeichnis

Idee

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

Erzeugung standardnormalverteilter Zufallszahlen

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

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

und

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

Hierbei wurde die Inversionsmethode zur Transformation von u1 und u2 in die Polarkoordinaten r und \varphi ausgenutzt:

 r = \sqrt{-2 \ln u_1}

und

\varphi = 2 \pi u_2.

Bei der Anwendung der Inversionsmethode wurde berücksichtigt, dass bei Polarkoordinaten \varphi einer Rechteckverteilung mit den Parametern 0 und unterliegt und r einer Exponentialverteilung mit dem Parameter \tfrac{1}{2}.

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

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

x_i = \mu + \sigma\,z_i

transformieren. In der obigen Notation steht π 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

Verwendet man zur Erzeugung der ui einen linearen Kongruenzgenerator, so liegen die Paare (z1;z2) 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 verwendet 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. siehe Kinderman, A.J. und J.R. Ramage: Computer Generation of Normal Random Numbers, Jour. Amer. Stat. Assoc., 71(356), p. 893-896 (1976)

Literatur

  • George Edward Pelham Box, Mervin Edgar Muller: A note on the generation of random normal deviates. Ann. Math. Stat. 29. 1958) 610-611.
  • Donald Ervin Knuth: The Art of Computer Programming, Sec. 3.4.1, p. 117
  • O. Moeschlin, O., E. Grycko, C. Pohl und F. Steinert: Experimental Stochastics. Springer, 1998, ISBN 3-540-14619-9, Kapitel 1.4 Generating Sample Values

Wikimedia Foundation.

Игры ⚽ Нужно решить контрольную?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Marsaglias polare Methode — Die Polar Methode von George Marsaglia ist ein Verfahren zur Erzeugung normalverteilter Zufallszahlen (Zufallszahlengenerator). Mit dieser Methode werden aus zwei gegebenen, im Intervall [0,1] gleichverteilten und voneinander unabhängigen… …   Deutsch Wikipedia

  • Polar-Marsaglia-Methode — Die Polar Methode von George Marsaglia ist ein Verfahren zur Erzeugung normalverteilter Zufallszahlen (Zufallszahlengenerator). Mit dieser Methode werden aus zwei gegebenen, im Intervall [0,1] gleichverteilten und voneinander unabhängigen… …   Deutsch Wikipedia

  • Polar-Methode — Die Polar Methode von George Marsaglia ist ein Verfahren zur Erzeugung normalverteilter Zufallszahlen (Zufallszahlengenerator). Inhaltsverzeichnis 1 Beschreibung 2 Beispielprogramm 3 Geschichte 4 …   Deutsch Wikipedia

  • Spektraltest — Der Spektraltest ist eine Methode, mit der überprüft werden kann, ob gegebene Zufallszahlen tatsächlich stochastisch voneinander unabhängig sind, oder ob das Gegenteil der Fall ist, d. h. bereits „gewürfelte“ Werte die folgenden Werte… …   Deutsch Wikipedia

  • Zufallszahlengenerator — Als Zufallszahlengenerator, gelegentlich auch zu Zufallsgenerator verkürzt, bezeichnet man ein Verfahren, das eine Folge von Zufallszahlen erzeugt. Der Bereich, aus dem die Zufallszahlen erzeugt werden, hängt dabei vom speziellen… …   Deutsch Wikipedia

  • Liste der Erfinder — Dies ist eine Liste von Erfindern, die die Welt mit ihren Erfindungen bereichert haben. Ein Erfinder ist jemand, der ein Problem erkannt hat, es gelöst und mindestens einmal damit Erfolg gehabt hat. Er muss nicht der erste gewesen sein; eine… …   Deutsch Wikipedia

  • Internet Protocol Television — Mit Internet Protocol Television (IPTV) wird allgemein der Übertragungsweg Internet für Fernsehprogramme und Filme bezeichnet im Gegensatz zu klassischem Rundfunk, Kabel oder Satellit. IPTV ist weder ein Standard noch ein Konzept und damit nur… …   Deutsch Wikipedia

  • Liste von Erfindern — Dies ist eine Liste von Erfindern, die die Welt mit ihren Erfindungen bereichert haben. Ein Erfinder ist jemand, der ein Problem erkannt hat, es gelöst und mindestens einmal damit Erfolg gehabt hat. Er muss nicht der erste gewesen sein; eine… …   Deutsch Wikipedia

  • IP-TV — Mit IPTV (Internet Protocol Television; deutsch: Internet Protokoll Fernsehen) wird die digitale Übertragung von breitbandigen Anwendungen, wie Fernsehprogrammen und Filmen, über ein digitales Datennetz bezeichnet. Hierzu wird das auch dem… …   Deutsch Wikipedia

  • IPTV — Mit IPTV (Internet Protocol Television; deutsch: Internet Protokoll Fernsehen) wird die digitale Übertragung von breitbandigen Anwendungen, wie Fernsehprogrammen und Filmen, über ein digitales Datennetz bezeichnet. Hierzu wird das auch dem… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”