Read Simulation von Zufallszahlen text version

Simulation von Zufallszahlen

Franziska Kohl, Nadja Harner

Computerintensive Methoden Miniprojekt WiSe 05/06 7. Februar 2006

Franziska Kohl, Nadja Harner

Simulation von Zufallszahlen

Simulation von Zufallszahlen

Allgemeines Zufallszahlengenerator f¨r U(0, 1)-Zufallszahlen vorausgesetzt u Ergebnis sind unabh¨ngige Zufallszahlen a Verfahren zum Ziehen aus eindimensionalen Verteilungen Inversionsverfahren Rejection Sampling / Adaptive Rejection Sampling Sampling-Importance-Resampling (SIR)-Algorithmus Anwendung Ziehen aus einer multivariaten Verteilung

Franziska Kohl, Nadja Harner

Simulation von Zufallszahlen

Inversionsverfahren

Prinzip: Erzeugung von Zufallszahlen mit Verteilungsfunktion F durch Transformation von U(0, 1)-Zufallszahlen U Vorgehen: Da F (X ) U(0, 1) gilt, erh¨lt man Zufallszahlen X mit Verteilungsfunktion F durch a X = F -1 (U) Beispiel: Exponentialverteilung F (x) = 1 - exp(-x), x > 0 log (1 - x) F -1 (x) = - log (U) X = -

Franziska Kohl, Nadja Harner Simulation von Zufallszahlen

Rejection Sampling

Prinzip: Erzeugung von Zufallszahlen X mit Dichte fX (x) unter Verwendung von Zufallszahlen Y mit Dichte fY (y )

0.5 Zieldichte Vorschlagsdichte Envelope 0.4 0.1 0.2 0.3

-4

-2

0 y

2

4

Franziska Kohl, Nadja Harner

Simulation von Zufallszahlen

Rejection Sampling

Algorithmus 1 : Rejection Sampling

1

(Vorschlag) Erzeuge Zufallszahl Y aus fY (y ) (Rejection-Schritt) Berechne (Y ) = fX (Y ) , M · fY (Y ) M = sup

x

2

fX (x) fY (x)

Erzeuge von Y unabh¨ngige Zufallszahl U mit U U(0, 1) a Falls U (Y ) akzeptiere Y als Zufallszahl aus der Dichte fX Wiederholung beider Schritte bis zur Akzeptanz eines Vorschlags

Franziska Kohl, Nadja Harner

Simulation von Zufallszahlen

Erweiterungen / Alternativen

Rejection Sampling mit zus¨tzlicher Squeeze-Funktion a Versuch, mit vereinfachter Berechnung der Akzeptanzwahrscheinlichkeit auszukommen (falls fX schwierig zu berechnen) Adaptive Rejection Sampling Nach jeder Akzeptanz eines Wertes werden Envelope und Squeeze angepasst Sampling-Importance-Resampling (SIR)-Algorithmus Aus m (unabh¨ngig gezogenen) Vorschlagswerten Y1 , ..., Ym a mit Dichte g werden n Werte mit Zur¨cklegen gezogen und u damit als Werte aus der Zieldichte akzeptiert. Die Auswahlf wahrscheinlichkeiten sind dabei proportional zu g (Yii ) . (Y )

Franziska Kohl, Nadja Harner

Simulation von Zufallszahlen

Ziehen aus einer multivariaten Verteilung

Problem: Es stehen nur Algorithmen zur Simulation von Zufallsvariablen aus eindimensionalen Verteilungen zur Verf¨gung. u Da f (x1 , ..., xn ) = f (x1 ) · f (x1 |x2 ) · ... · f (xn |x1 , ..., xn-1 ) gilt, kann sequentiell aus den (eindimensionalen) bedingten Dichten gezogen werden. MCMC-Verfahren erm¨glichen es, direkt Zufallszahlen aus einer o mehrdimensionalen Verteilung zu ziehen.

Franziska Kohl, Nadja Harner

Simulation von Zufallszahlen

Information

Simulation von Zufallszahlen

7 pages

Report File (DMCA)

Our content is added by our users. We aim to remove reported files within 1 working day. Please use this link to notify us:

Report this file as copyright or inappropriate

519658


You might also be interested in

BETA
Simulation von Zufallszahlen