Stochastische Simulation (oder Monte-Carlo-Simulation) beschäftigt sich mit der Nachbildung eines (zufallsbehafteten) Systems in einem
Computerprogramm um Eigenschaften des Systems zu analysieren. Vorteile sind dabei u.a.:
Geringere Kosten als bei Untersuchung des realen Systems (z.B. Crashtests)
Keine Gefahren, z.B. bei Untersuchung von Epidemien
Analytische Untersuchung oft sehr aufwändig oder gar nicht bekannt
Zu detaillierten Grundlagen zu Monte-Carlo-Simulation sei auf die Vorlesung "Stochastische Simulation" verwiesen,
hier werden wir uns vor allem um Anwendungen kümmern.
Grundlagen
Informieren Sie sich, welche Zufallszahlen-Generatoren im Standard-Matlab und in den Toolboxen zu finden sind.
Erzeugen Sie mit diesen Generatoren Zufallszahlen und stellen Sie diese in einem Histogramm dar.
Wie verhält sich der Zufallszahlengenerator beim Neustart von Matlab ?
Welche Auswirkung hat das Leeren des Workspace mit clear ?
Wie kann man den ZZ-Generator initialisieren so dass bei jedem neuen Durchlauf immer andere Folgen entstehen ?
Erzeugen Sie normalverteilte Zufallszahlen ohne Verwendung einer fertigen Matlab-Funktion. Stellen Sie diese in einem Histogramm zusammen mit der (analytischen) Dichtefunktion dar.
Dartpfeile auf Pi ;-)
Zum Start soll eine Monte-Carlo-Simulation zur Schätzung von Pi implementiert werden.
Im Algorithmus werden dazu zwei gleichverteilte Zufallszahlen x,y aus [0,1] generiert und der Versuch zählt als
Treffer, wenn gilt x^2 + y^2 <=1.
Entwickeln Sie ein Simulationsprogramm, welches insgesamt N Versuche ausführt und alle K (z.B.: K=100) Simulationen eine Statuszeile mit der aktuellen
Schätzung von Pi ausgibt.
Wie verändert sich die Anzahl korrekter Nachkommastellen von Pi in Abhängigkeit von der Versuchsanzahl N ?
Ratsimu -- Die Ratte im Labyrinth
Dies ist ein Beispiel einer klassischen Markov-Kette mit 2 Absorptionszuständen.
Eine Ratte startet in der Kammer Nummer 4 und entscheidet sich völlig zufällig für eine der
möglichen Richtungen. In der grünen Kammer Nummer 5 steht eine Futterkiste und die Ratte bleibt für alle Zeiten dort.
In der roten Kammer Nummer 6 hingegen lauert eine Schlange und die Ratte wird gefressen.
Nun die Programmieraufgabe:
Ermitteln Sie mit einer Monte-Carlo-Simulation die Wahrscheinlichkeit, dass die Ratte die Futterkiste erreicht.
Wie viele Simulationen erscheinen für eine stabile Schätzung sinnvoll ?
Ermitteln Sie die Laufzeit für 100,1000,1 Million, 10 Millionen ... Simulationen.
Welchen Schluss ziehen Sie beim Vergleich mit den Laufzeiten eines analogen C-Programmes,
welches für 100 Million Simus, ca. 10 Sekunden braucht ?
Tennis als Markovkette
Nun wollen wir ein Tennismatch, welches auch als Markovkette dargestellt werden kann, untersuchen.
Zunächst eine Skizze der Zustände und Übergänge.
Nun die Programmieraufgabe:
Programmieren Sie eine Simulation für den Ablauf eines Spieles. Sie endet , wenn A oder B gewinnt.
Erweitern Sie nun das Programm, so dass mit einer hinreichend großen Anzahl N von Simulationen
die Gewinnwahrscheinlichkeiten für Spieler A bzw. B abgeschätzt werden können.
Lassen Sie die Simulation für p_A=p_B=0.5 (d.h. gleichstarke Spieler) laufen. Es sollte auch für beide die selbe Gewinnwahrscheinlichkeit von 0.5 herauskommen. (gerechtes Spiel)
Testen Sie nun mit p_A=0.6 und p_B=0.4, welche Gewinnwahrscheinlichkeiten sich für Spieler A und B ergeben.
Stochastische Matrizen
Obige Beispiel der Ratte oder des Tennisspiels kann man auch algebraisch über die Matrix der Übergangswahrscheinlichkeiten und ihrer Eigenwerte/Eigenvektoren
analysieren. Details dazu kommen in der Vorlesung, zur Programmieraufgabe:
Implementieren Sie zum Tennis die 20x20 Matrix P mit den Übergangswahrscheinlichkeiten.
Ermitteln Sie wie sich ein Zeilenvektor s=[1,0,...,0] der Länge 20 bei fortlaufender Multiplikation s=s*P verändert.
Literatur zur Simulation
Hier eine kleine Auswahl von grundlegender und weiterführender Literatur zur Stochastischen Simulation:
M. Kolonko:
Stochastische Simulation, Springer, 2008
(online bei SpringerLink)
Müller-Gronbach, E. Novak und K. Ritter:
Monte Carlo-Algorithmen Springer, 2012
(online bei SpringerLink)
Donald E. Knuth:
The art of computer programming, Volume 2, Addison-Wesley, Amsterdam, 1997
