Monte-Carlo-Simulation (auch MC-Simulation oder Monte-Carlo-Studie) ist ein Verfahren aus der Stochastik bzw. Wahrscheinlichkeitstheorie, bei dem wiederholt Zufallsstichproben einer Verteilung mithilfe von Zufallsexperimenten gezogen werden.[1]
Ziel ist es, analytisch nicht oder nur aufwendig lösbare Probleme mithilfe der gezogenen Stichproben numerisch zu lösen. Als Grundlage ist vor allem das Gesetz der großen Zahlen zu sehen. Die Zufallsexperimente können entweder – etwa durch Würfeln – real durchgeführt werden oder in Computerberechnungen mittels Monte-Carlo-Algorithmen. Bei Monte-Carlo-Algorithmen werden zur Simulation von zufälligen Ereignissen Zufallszahlen oder auch Pseudozufallszahlen benutzt.
Monte-Carlo-Simulationen weisen Ähnlichkeit zu probabilistischen zellulären Automaten auf.
Das 1733 von Georges-Louis Leclerc de Buffon vor der Pariser Akademie der Wissenschaften vorgestellte Nadelproblem[2], das mit Hilfe des Zufalls die näherungsweise Bestimmung der Kreiszahl Pi ermöglicht, war eine der ersten Anwendungen einer „Monte-Carlo-Simulation“.
In den 1930er Jahren hatte der Physiker Enrico Fermi die ersten Ideen zu „Monte-Carlo-Simulationen“ mittels elektronischer Rechenmaschinen.[3] Als Vorgänger und „Rechner“ galt bis dahin der mechanische Analogrechner FERMIAC.[4] Dies geschah zur Zeit des Zweiten Weltkriegs während der Arbeiten als Teil des Manhattan-Projekts, am Los Alamos Scientific Laboratory.[5] Es ging im Rahmen der Entwicklung der amerikanischen Atombombe, nebst anderen technischen Fragestellungen und Probleme, um den Neutronentransport in nuklearen Materialien. Dabei musste in den Anfängen auch die mathematische Methode der Simulation geheim gehalten werden.
Weitere Beiträge lieferten die u. g. Personen, darunter Stanisław Marcin Ulam[6] und John von Neumann. Beide beschäftigten sich mit den ersten elektronischen (noch Röhren-basierten, also ohne Halbleitertechnologie) Rechenmaschinen, darunter der ENIAC und das Nachfolgermodell der MANIAC I.
Nach der Anfangsphase der Erforschung gilt als grundlegende Veröffentlichung die Arbeit Equation of State Calculations by Fast Computing Machines von Nicholas Metropolis[7], Marshall N. Rosenbluth und dessen Ehefrau Arianna W. Rosenbluth, Edward Teller und dessen Ehefrau Augusta H. Teller, veröffentlicht 1953 im Journal of Chemical Physics.[8]
Ziel war die Berechnung der Zustandsgleichung eines zweidimensionalen Systems starrer Kugeln als Modelle einer Flüssigkeit. Simuliert wurde mit 224 Teilchen und periodischen Randbedingungen. Jede Simulation bestand aus bis zu 48 Zyklen, in denen jeweils jedes Teilchen einen Bewegungsschritt ausführte. Ein Zyklus benötigte drei Minuten auf dem MANIAC I. Verwendet wurde eine Sampling-Methode mit Wichtung über den Boltzmannfaktor, das Herzstück des MC-Verfahrens im Metropolis-Algorithmus, wobei die Idee nach Marshall Rosenbluth von Teller gekommen sein soll.[9][10] Nach Rosenbluth leisteten er und seine Frau die Hauptarbeit für den Artikel (Metropolis hätte hauptsächlich Computerzeit zur Verfügung gestellt) und sie waren die einzigen der Autoren, die das Verfahren in anschließenden Publikationen weiterverfolgten,[11][12] sie wandten sich aber selbst ebenfalls bald darauf anderen Forschungsthemen (Plasmaphysik) zu.
Der Name Monte-Carlo wurde von Nicholas Metropolis geprägt und hängt wie folgt mit der Methode zusammen: Stan Ulam hatte einen Onkel, der sich zum Spielen immer Geld von Verwandten geliehen hatte, denn „er musste nach Monte Carlo gehen“.[13] Dies ist natürlich eine Anspielung auf die Spielbank Monte-Carlo im gleichnamigen Stadtteil des Stadtstaates Monaco.[14]
Monte-Carlo-Simulationen sind besonders geeignet, um den Erwartungswert einer Funktion zu berechnen[15].
Im Fall diskrekter Zufallsvariablen also
bzw. im Fall kontinuierlicher Zufallsvariablen
wobei hochdimensionale Integrale (Monte-Carlo-Integration) auftreten, falls ein hochdimensionaler Zufallsvektor ist.
Kern der Monte-Carlo-Simulation ist die Schätzung des Erwartungswertes anhand von Stichproben. Je nachdem, welcher Verteilung die Stichproben entstammen, kann der Schätzer des Erwartungswertes eine kleinere oder größere Varianz haben. Ist man an der praktischen Berechnung eines Mittelwertschätzers interessiert, so will man mit möglichst kleinem Stichprobenumfang einen Schätzer möglichst kleiner Varianz erlangen – dies kann durch Methoden der Varianzreduktion erreicht werden. Stichproben aus einer Wahrscheinlichkeitsverteilung können mit Markov-Chain-Monte-Carlo-Verfahren erzeugt werden.
Häufig ist der Raum so groß, dass die Summation nicht vollständig durchgeführt werden kann. Stattdessen erzeugt man eine Markow-Kette von Zuständen in , deren Häufigkeit wie das vorgegebene Gewicht verteilt ist: Bereiche des Raumes (bzw. Realisierungen) mit hoher Wahrscheinlichkeit sollen in der Markow-Kette entsprechend ihrer Wahrscheinlichkeit häufiger vertreten sein als Bereiche mit niedriger Wahrscheinlichkeit. Gelingt dies, so lassen sich die Erwartungswerte einfach als arithmetisches Mittel der Funktion ausgewertet an den Realisierungen der Markow-Kette berechnen, also als
Dieser Zusammenhang basiert auf dem Gesetz der großen Zahlen. Die Varianz wird dann durch den Standardfehler beschrieben.
Es kann schwierig sein, diese Markow-Kette zu erzeugen, beispielsweise weil die Akzeptanzwahrscheinlichkeit der neuen Zustände sehr klein ist. Insbesondere ist sicherzustellen, dass die Markow-Kette tatsächlich den gesamten Raum bedeckt und nicht nur einen Teil des Raumes abtastet. Man sagt: der Algorithmus muss ergodisch sein.
Soll die Varianz des Mittelwertschätzers verringert werden, so können die Stichproben nicht gemäß gezogen werden, sondern aus einer varianzredzuzierenden Verteilung , diese Verteilung wird im Importance Sampling auch als „biased distribution“, „proposal distribution“ oder „sample distribution“ bezeichnet.
Die Konvergenz von Monte-Carlo-Simulationen kann mit der Gelman-Rubin-Statistik bewertet werden.
Mit der Monte-Carlo-Methode können Probleme mit statistischem Verhalten simuliert werden.
Weitere Anwendungen der Monte-Carlo-Simulation sind folgende:
Zur Bestimmung von (höherdimensionalen) Integralen wird in der einfachsten Form (Simple Sampling) folgender Sachverhalt ausgenutzt: Sei eine beliebig dimensionale Menge und eine integrierbare Funktion.
Das Integral sei Wird nun als Wahrscheinlichkeitsdichte eines im Volumen gleichverteilten Zufallsvektors interpretiert, so ist
Der Schätzer des Integrals der Funktion ist somit: , falls (gleichverteilt) und approximiert den Wert mit steigender Zahl an Stichproben beliebig genau.
Für ein konkretes Beispiel siehe unten.
In der Praxis werden Monte-Carlo-Verfahren vor allem für die Berechnung hochdimensionaler Integrale verwendet. Hier sind klassische Integrationsalgorithmen stark vom Fluch der Dimensionalität betroffen und nicht mehr anwendbar. Allerdings sind speziell hochdimensionale Integranden meist stark lokalisiert[17]. In diesen Fällen erlauben insbesondere MCMC-Verfahren (siehe dort) die Erzeugung von Stichproben mit einer Verteilung die eine effiziente Berechnung solcher hochdimensionaler Integrale erlaubt.
Untersuchung der Verteilungseigenschaften von Zufallsvariablen unbekannten Verteilungstyps,
Durch Monte-Carlo-Simulationen können komplizierte Bayessche Modelle auf Daten angepasst werden (wie z. B. in Approximate Bayesian Computation) und mithilfe der Posterior predictive distribution zur Vorhersage benutzt werden.
Man wählt hierzu zufällige Punkte in der Menge gleichverteilt aus und überprüft für jeden Punkt , ob dieser innerhalb des Einheitskreises liegt, ob also die Bedingung
erfüllt ist. Dies kann formal über die Indikatorfunktion getestet werden:
Ein Wert ist die Realisierung einer Bernoulli-verteilten Zufallsvariablen , wobei der Bernoulli-Parameter der Verteilung gerade durch das Flächenverhältnis gegeben ist, d. h.
Dabei ist und bezeichnet die Kreiszahl.
Liegt eine Folge von Realisierungen von stochastisch unabhängigen und identisch verteilten Zufallsvariable vor, die jeweils Bernoulli-verteilt mit dem Bernoulli-Parameter sind, so ist die relative Häufigkeit
der übliche Schätzwert für die Wahrscheinlichkeit . Eine alternative Sichtweise ist, dass ein Schätzwert für den Erwartungswert durch das arithmetische Mittel gegeben ist.
Somit ist ein Monte-Carlo-Schätzwert für . Wegen ist ein Monte-Carlo-Schätzwert für .
Für die so erhaltene Schätzung können Konfidenzintervalle mithilfe des Standardfehlers angegeben werden, welche die Unsicherheit der Schätzung ausdrücken.
Das obige Beispiel zur Bestimmung von Pi schätzt das Flächenintegral einer Viertelkreisfläche und verwendet dazu Bernoulli-verteilte Zufallsvariablen .
Dasselbe Ergebnis kann auch durch die oben angegebene Integrationsformel mit gleichverteilten Zufallsvariablen und erreichen.
Um wie oben vorgestellt Pi mithilfe von Simple Sampling zu berechnen, muss man und als Indikatorfunktion des Einheitskreises wählen:
Dann ist die Fläche des Einheitskreises und der Schätzer wobei das Volumen ist.
Die Crofton-Formel zur Bestimmung der Bogenlänge einer Kurve kann näherungsweise mit Monte-Carlo-Simulationen ausgewertet werden.
Ein Beispiel für eine Monte-Carlo-Simulation ist der Miller-Rabin-Test, bei dem probabilistisch bestimmt wird, ob eine natürliche Zahl prim ist oder nicht. Die Ausgabe des Tests lautet entweder „sicher zusammengesetzt“ oder „wahrscheinlich prim“. Die Wahrscheinlichkeit, dass eine zusammengesetzte Zahl als „wahrscheinlich prim“ klassifiziert wird, liegt pro Durchgang unter 25 % und kann durch mehrfache Ausführung weiter gesenkt werden. Der Miller-Rabin-Test liefert keine Aussage über die Faktoren einer zusammengesetzten Zahl, ist also kein Faktorisierungsverfahren.
Hinweis. Die Liste ist als unvollständig zu betrachten, bietet aber einige bekannte Beispiel an MCS. Es existieren ebenfalls kommerzielle Codes, oder Codes die für spezielle Prozesse entwickelt wurden, usw.