Monte-Carlo-Simulation

Monte-Carlo-Methoden oder Monte-Carlo-Experimente sind eine breite Klasse von Berechnungsalgorithmen, die sich auf wiederholte Zufallsstichproben stützen, um numerische Ergebnisse zu erhalten. Das zugrunde liegende Konzept besteht darin, den Zufall zu nutzen, um Probleme zu lösen, die im Prinzip deterministisch sein könnten. Sie werden häufig bei physikalischen und mathematischen Problemen eingesetzt und sind besonders nützlich, wenn andere Ansätze schwierig oder unmöglich sind. Monte-Carlo-Methoden werden hauptsächlich in drei Problemklassen eingesetzt: Optimierung, numerische Integration und Generierung von Ziehungen aus einer Wahrscheinlichkeitsverteilung. ⓘ

Bei physikalischen Problemen sind Monte-Carlo-Methoden nützlich für die Simulation von Systemen mit vielen gekoppelten Freiheitsgraden, wie Flüssigkeiten, ungeordneten Materialien, stark gekoppelten Festkörpern und zellulären Strukturen (siehe zelluläres Potts-Modell, interagierende Teilchensysteme, McKean-Vlasov-Prozesse, kinetische Modelle von Gasen). ⓘ

Weitere Beispiele sind die Modellierung von Phänomenen mit erheblichen Unsicherheiten bei den Inputs, wie die Risikoberechnung in der Wirtschaft und in der Mathematik die Auswertung mehrdimensionaler definitiver Integrale mit komplizierten Randbedingungen. Bei der Anwendung auf systemtechnische Probleme (Raumfahrt, Ölexploration, Flugzeugbau usw.) sind Monte-Carlo-basierte Vorhersagen von Misserfolgen, Kosten- und Terminüberschreitungen regelmäßig besser als menschliche Intuition oder alternative "weiche" Methoden. ⓘ

Im Prinzip können Monte-Carlo-Methoden zur Lösung jedes Problems verwendet werden, das eine probabilistische Interpretation hat. Nach dem Gesetz der großen Zahlen können Integrale, die durch den Erwartungswert einer Zufallsvariablen beschrieben werden, durch den empirischen Mittelwert (auch bekannt als Stichprobenmittelwert) unabhängiger Stichproben der Variablen angenähert werden. Wenn die Wahrscheinlichkeitsverteilung der Variablen parametrisiert ist, verwenden Mathematiker häufig einen Markov Chain Monte Carlo (MCMC) Sampler. Die zentrale Idee besteht darin, ein vernünftiges Markov-Kettenmodell mit einer vorgegebenen stationären Wahrscheinlichkeitsverteilung zu entwerfen. Das bedeutet, dass die von der MCMC-Methode erzeugten Stichproben im Grenzfall Stichproben aus der gewünschten (Ziel-)Verteilung sein werden. Nach dem Ergodentheorem wird die stationäre Verteilung durch die empirischen Maße der Zufallszustände des MCMC-Samplers angenähert. ⓘ

Bei anderen Problemen besteht das Ziel darin, Ziehungen aus einer Folge von Wahrscheinlichkeitsverteilungen zu erzeugen, die eine nichtlineare Evolutionsgleichung erfüllen. Diese Ströme von Wahrscheinlichkeitsverteilungen können immer als die Verteilungen der Zufallszustände eines Markov-Prozesses interpretiert werden, dessen Übergangswahrscheinlichkeiten von den Verteilungen der aktuellen Zufallszustände abhängen (siehe McKean-Vlasov-Prozesse, nichtlineare Filtergleichung). In anderen Fällen ist ein Fluss von Wahrscheinlichkeitsverteilungen mit zunehmender Komplexität der Stichproben gegeben (Pfadraummodelle mit zunehmendem Zeithorizont, Boltzmann-Gibbs-Maße, die mit abnehmenden Temperaturparametern verbunden sind, und viele andere). Diese Modelle können auch als die Entwicklung des Gesetzes der Zufallszustände einer nichtlinearen Markov-Kette betrachtet werden. Ein natürlicher Weg, diese anspruchsvollen nichtlinearen Markov-Prozesse zu simulieren, besteht darin, mehrere Kopien des Prozesses zu beproben und in der Evolutionsgleichung die unbekannten Verteilungen der Zufallszustände durch die beprobten empirischen Maße zu ersetzen. Im Gegensatz zu den traditionellen Monte-Carlo- und MCMC-Methoden beruhen diese Mean-Field-Partikeltechniken auf sequentiell interagierenden Stichproben. Der Begriff "Mean Field" (mittleres Feld) spiegelt die Tatsache wider, dass jede der Stichproben (auch bekannt als Partikel, Individuen, Walker, Agenten, Lebewesen oder Phänotypen) mit den empirischen Maßen des Prozesses interagiert. Wenn die Größe des Systems gegen unendlich tendiert, konvergieren diese empirischen Zufallsmaße gegen die deterministische Verteilung der Zufallszustände der nichtlinearen Markov-Kette, so dass die statistische Interaktion zwischen den Teilchen verschwindet. ⓘ

Trotz ihrer konzeptionellen und algorithmischen Einfachheit können die mit einer Monte-Carlo-Simulation verbundenen Rechenkosten erstaunlich hoch sein. Im Allgemeinen erfordert die Methode viele Stichproben, um eine gute Annäherung zu erhalten, was zu einer beliebig langen Gesamtlaufzeit führen kann, wenn die Verarbeitungszeit für eine einzelne Stichprobe hoch ist. Obwohl dies bei sehr komplexen Problemen eine schwerwiegende Einschränkung darstellt, können diese hohen Kosten dank der peinlich parallelen Natur des Algorithmus durch parallele Berechnungsstrategien in lokalen Prozessoren, Clustern, Cloud Computing, GPU, FPGA usw. (vielleicht auf ein machbares Niveau) reduziert werden. ⓘ

Die Kreiszahl Pi wird mit der Monte-Carlo-Methode angenähert bestimmt durch das Vierfache der Wahrscheinlichkeit, mit der ein innerhalb des Quadrats zufällig gewählter Punkt in den Kreisabschnitt fällt. Aufgrund des Gesetzes der großen Zahlen sinkt mit steigender Anzahl von Experimenten die Varianz des Ergebnisses. ⓘ

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. ⓘ

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. ⓘ

Zu den Pionieren der Monte-Carlo-Methode in den 1940er Jahren gehören Stanislaw Ulam, Nicholas Metropolis und John von Neumann. Als grundlegende Veröffentlichung gilt eine Arbeit von Metropolis, Edward Teller, Augusta H. Teller, Marshall Rosenbluth und Arianna W. Rosenbluth von 1953. ⓘ

Überblick

Monte-Carlo-Methoden variieren, folgen aber in der Regel einem bestimmten Muster:

1. Definieren eines Bereichs möglicher Eingaben
2. Generierung von Eingaben nach dem Zufallsprinzip aus einer Wahrscheinlichkeitsverteilung über den Bereich
3. Durchführen einer deterministischen Berechnung mit den Eingaben
4. Aggregieren der Ergebnisse ⓘ

Anwendung der Monte-Carlo-Methode zur Annäherung an den Wert von π. ⓘ

Betrachten wir zum Beispiel einen Quadranten (Kreissektor), der in ein Einheitsquadrat eingeschrieben ist. Da das Verhältnis ihrer Flächen π/4 ist, kann der Wert von π mit Hilfe einer Monte-Carlo-Methode geschätzt werden:

1. Zeichnen Sie ein Quadrat und schreiben Sie einen Quadranten in das Quadrat ein.
2. Verteilen Sie eine bestimmte Anzahl von Punkten gleichmäßig über das Quadrat
3. Zählen Sie die Anzahl der Punkte, die innerhalb des Quadranten liegen, d. h. einen Abstand vom Ursprung von weniger als 1 haben.
4. Das Verhältnis von Innenzahl und Gesamtprobenzahl ist eine Schätzung des Verhältnisses der beiden Flächen, π/4. Multiplizieren Sie das Ergebnis mit 4, um π zu schätzen.

Bei diesem Verfahren ist der Bereich der Eingaben das Quadrat, das den Quadranten umschreibt. Wir erzeugen zufällige Eingaben, indem wir Körner über das Quadrat streuen, und führen dann für jede Eingabe eine Berechnung durch (prüfen, ob sie in den Quadranten fällt). Die Aggregation der Ergebnisse ergibt unser Endergebnis, die Näherung von π. ⓘ

Dabei gibt es zwei wichtige Überlegungen:

1. Wenn die Punkte nicht gleichmäßig verteilt sind, wird die Annäherung schlecht sein.
2. Es gibt viele Punkte. Die Annäherung ist im Allgemeinen schlecht, wenn nur einige wenige Punkte zufällig im gesamten Quadrat verteilt sind. Im Durchschnitt wird die Annäherung besser, wenn mehr Punkte platziert werden. ⓘ

Für die Anwendung von Monte-Carlo-Methoden sind große Mengen an Zufallszahlen erforderlich, und ihre Anwendung profitierte stark von Pseudozufallszahlengeneratoren, die weitaus schneller zu verwenden waren als die Tabellen mit Zufallszahlen, die zuvor für statistische Stichproben verwendet wurden. ⓘ

Man wählt hierzu zufällige Punkte $\left(x,y|x\in \left[-1..1\right]\wedge y\in \left[-1..1\right]\right)$ aus und überprüft (durch Anwendung des Satzes von Pythagoras), ob diese innerhalb des Einheitskreises liegen:

$x^{2}+y^{2}\leq 1$. ⓘ

Über das Verhältnis der Anzahl der Punkte innerhalb und außerhalb des Kreises kann dann folgendermaßen $\ \pi$ bestimmt werden:

${\frac {{\text{Kreisfl}}\mathrm {\ddot {a}} {\text{che}}}{{\text{Quadratfl}}\mathrm {\ddot {a}} {\text{che}}}}={\frac {r^{2}\cdot \pi }{(2\cdot r)^{2}}}={\frac {\pi }{4}}={\frac {{\text{Treffer in Kreisfl}}\mathrm {\ddot {a}} {\text{che}}}{\text{generierte Punkte im Quadrat}}}=P\left({\text{Im Kreis}}\right)$ ⓘ

Geschichte

Vor der Entwicklung der Monte-Carlo-Methode wurde ein zuvor verstandenes deterministisches Problem mit Hilfe von Simulationen getestet, wobei statistische Stichproben zur Schätzung der Unsicherheiten in den Simulationen verwendet wurden. Monte-Carlo-Simulationen kehren diesen Ansatz um und lösen deterministische Probleme mit Hilfe probabilistischer Metaheuristiken (siehe Simulated Annealing). ⓘ

Eine frühe Variante der Monte-Carlo-Methode wurde entwickelt, um das Buffonsche Nadelproblem zu lösen, bei dem π durch das Fallenlassen von Nadeln auf einen Boden aus parallelen, äquidistanten Streifen geschätzt werden kann. In den 1930er Jahren experimentierte Enrico Fermi erstmals mit der Monte-Carlo-Methode, als er die Neutronendiffusion untersuchte, veröffentlichte diese Arbeit jedoch nicht. ⓘ

In den späten 1940er Jahren erfand Stanislaw Ulam die moderne Version der Markov-Ketten-Monte-Carlo-Methode, als er am Los Alamos National Laboratory an Kernwaffenprojekten arbeitete. Unmittelbar nach Ulams Durchbruch erkannte John von Neumann dessen Bedeutung. Im Jahr 1946 untersuchten Kernwaffenphysiker in Los Alamos die Neutronendiffusion im Kern einer Kernwaffe. Obwohl sie über die meisten der erforderlichen Daten verfügten, wie z. B. die durchschnittliche Entfernung, die ein Neutron in einer Substanz zurücklegen würde, bevor es mit einem Atomkern zusammenstößt, und wie viel Energie das Neutron nach einem Zusammenstoß wahrscheinlich abgeben würde, waren die Physiker in Los Alamos nicht in der Lage, das Problem mit herkömmlichen, deterministischen mathematischen Methoden zu lösen. Ulam schlug die Verwendung von Zufallsexperimenten vor. Er berichtet über seine Inspiration wie folgt:

Die ersten Gedanken und Versuche, die ich unternahm, um [die Monte-Carlo-Methode] anzuwenden, wurden durch eine Frage angeregt, die mir 1946 einfiel, als ich mich von einer Krankheit erholte und Solitär spielte. Die Frage lautete: Wie groß sind die Chancen, dass ein Canfield-Solitär mit 52 Karten erfolgreich ist? Nachdem ich viel Zeit damit verbracht hatte, sie durch rein kombinatorische Berechnungen abzuschätzen, fragte ich mich, ob eine praktischere Methode als "abstraktes Denken" nicht darin bestehen könnte, das Spiel etwa hundertmal auszulegen und einfach die Anzahl der erfolgreichen Spiele zu beobachten und zu zählen. Dies war bereits zu Beginn der neuen Ära der schnellen Computer vorstellbar, und ich dachte sofort an Probleme der Neutronendiffusion und andere Fragen der mathematischen Physik, und ganz allgemein daran, wie man Prozesse, die durch bestimmte Differentialgleichungen beschrieben werden, in eine äquivalente Form überführen kann, die als eine Folge von Zufallsoperationen interpretierbar ist. Später [1946] beschrieb ich John von Neumann die Idee, und wir begannen, konkrete Berechnungen zu planen. ⓘ

Da die Arbeit von von Neumann und Ulam geheim war, brauchte sie einen Codenamen. Ein Kollege von Neumann und Ulam, Nicholas Metropolis, schlug den Namen Monte Carlo vor, der sich auf das Casino Monte Carlo in Monaco bezieht, in dem Ulams Onkel sich von Verwandten Geld für Glücksspiele lieh. Monte-Carlo-Methoden waren für die Simulationen, die für das Manhattan-Projekt erforderlich waren, von zentraler Bedeutung, wenngleich sie durch die damaligen Berechnungswerkzeuge stark eingeschränkt waren. Von Neumann, Nicholas Metropolis und andere programmierten im Frühjahr 1948 den ENIAC-Computer so, dass er die ersten vollautomatischen Monte-Carlo-Berechnungen eines Kerns einer Spaltungswaffe durchführen konnte. In den 1950er Jahren wurden Monte-Carlo-Methoden in Los Alamos bei der Entwicklung der Wasserstoffbombe eingesetzt und fanden in den Bereichen Physik, physikalische Chemie und Operations Research Verbreitung. Die Rand Corporation und die U.S. Air Force waren zwei der wichtigsten Organisationen, die in dieser Zeit für die Finanzierung und Verbreitung von Informationen über Monte-Carlo-Methoden verantwortlich waren, und sie fanden allmählich eine breite Anwendung in vielen verschiedenen Bereichen. ⓘ

Die Theorie der anspruchsvolleren Partikel-Monte-Carlo-Methoden des Mean-Field-Typs hatte Mitte der 1960er Jahre mit der Arbeit von Henry P. McKean Jr. über Markov-Interpretationen einer Klasse nichtlinearer parabolischer partieller Differentialgleichungen aus der Strömungsmechanik begonnen. Wir zitieren auch einen früheren bahnbrechenden Artikel von Theodore E. Harris und Herman Kahn aus dem Jahr 1951, in dem Monte-Carlo-Methoden des genetischen Mittelfeldes zur Schätzung der Transmissionsenergie von Teilchen verwendet wurden. Genetische Monte-Carlo-Methoden mit mittlerem Feld werden auch als heuristische natürliche Suchalgorithmen (auch bekannt als Metaheuristik) im evolutionären Rechnen verwendet. Die Ursprünge dieser Mean-Field-Berechnungstechniken lassen sich bis in die Jahre 1950 und 1954 zurückverfolgen, als Alan Turing an genetischen Mutations-Selektions-Lernmaschinen arbeitete und Nils Aall Barricelli am Institute for Advanced Study in Princeton, New Jersey, Artikel verfasste. ⓘ

Quanten-Monte-Carlo-Methoden, insbesondere Diffusions-Monte-Carlo-Methoden, können auch als Mean-Field-Partikel-Monte-Carlo-Näherung der Feynman-Kac-Pfadintegrale interpretiert werden. Die Ursprünge der Quanten-Monte-Carlo-Methoden werden häufig Enrico Fermi und Robert Richtmyer zugeschrieben, die 1948 eine Mean-Field-Particle-Interpretation von Neutronenkettenreaktionen entwickelten, aber der erste heuristikähnliche und genetische Partikelalgorithmus (auch bekannt als Der erste heuristisch-ähnliche und genetische Teilchenalgorithmus (auch bekannt als Resampled- oder Reconfiguration-Monte-Carlo-Methode) zur Schätzung der Grundzustandsenergien von Quantensystemen (in reduzierten Matrixmodellen) geht auf Jack H. Hetherington im Jahr 1984 zurück. In der Molekularchemie kann die Verwendung genetischer, heuristisch-ähnlicher Teilchenmethoden (auch bekannt als Pruning- und Enrichment-Strategien) bis 1955 mit der bahnbrechenden Arbeit von Marshall N. Rosenbluth und Arianna W. Rosenbluth zurückverfolgt werden. Rosenbluth. ⓘ

Die Verwendung von Sequential Monte Carlo in der fortgeschrittenen Signalverarbeitung und Bayes'schen Inferenz ist jüngeren Datums. Im Jahr 1993 veröffentlichten Gordon et al. in ihrer bahnbrechenden Arbeit die erste Anwendung eines Monte-Carlo-Resampling-Algorithmus in der Bayes'schen Statistik. Die Autoren nannten ihren Algorithmus "den Bootstrap-Filter" und zeigten, dass ihr Bootstrap-Algorithmus im Vergleich zu anderen Filtermethoden keine Annahmen über den Zustandsraum oder das Rauschen des Systems erfordert. Wir zitieren auch einen weiteren bahnbrechenden Artikel auf diesem Gebiet von Genshiro Kitagawa über einen verwandten "Monte-Carlo-Filter" und die Artikel von Pierre Del Moral und Himilcon Carvalho, Pierre Del Moral, André Monin und Gérard Salut über Partikelfilter, die Mitte der 1990er Jahre veröffentlicht wurden. Partikelfilter wurden auch in der Signalverarbeitung in den Jahren 1989-1992 von P. Del Moral, J. C. Noyer, G. Rigal und G. Salut im LAAS-CNRS in einer Reihe von eingeschränkten und geheimen Forschungsberichten mit STCAN (Service Technique des Constructions et Armes Navales), der IT-Firma DIGILOG und dem LAAS-CNRS (dem Labor für Analyse und Architektur von Systemen) zu Problemen der Radar-/Sonar- und GPS-Signalverarbeitung entwickelt. Diese sequentiellen Monte-Carlo-Methoden können als Akzeptanz-Verwerfungs-Sampler interpretiert werden, der mit einem interaktiven Recycling-Mechanismus ausgestattet ist. ⓘ

Von 1950 bis 1996 wurden in allen Veröffentlichungen über sequenzielle Monte-Carlo-Methoden, einschließlich der in der Computerphysik und Molekularchemie eingeführten Pruning- und Resample-Monte-Carlo-Methoden, natürliche und heuristisch anmutende Algorithmen vorgestellt, die auf verschiedene Situationen angewandt wurden, ohne dass ein einziger Beweis für ihre Konsistenz erbracht wurde und ohne dass eine Diskussion über die Verzerrung der Schätzungen und über Algorithmen auf der Grundlage von Genealogie und Stammbäumen geführt wurde. Die mathematischen Grundlagen und die erste strenge Analyse dieser Partikelalgorithmen wurden 1996 von Pierre Del Moral verfasst. ⓘ

Ende der 90er Jahre wurden von Dan Crisan, Jessica Gaines und Terry Lyons sowie von Dan Crisan, Pierre Del Moral und Terry Lyons auch Partikelmethoden des Verzweigungstyps mit unterschiedlichen Populationsgrößen entwickelt. Weitere Entwicklungen auf diesem Gebiet wurden im Jahr 2000 von P. Del Moral, A. Guionnet und L. Miclo entwickelt. ⓘ

Das 1733 von Georges-Louis Leclerc de Buffon vor der Pariser Akademie der Wissenschaften vorgestellte Nadelproblem, das mit Hilfe des Zufalls die näherungsweise Bestimmung der Kreiszahl Pi ermöglicht, war eine der ersten Anwendungen einer Monte-Carlo-Simulation. (→Probabilistische Bestimmung der Zahl Pi) ⓘ

Als grundlegende Veröffentlichung gilt eine Arbeit von Nicholas Metropolis, 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. 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 Computer des Los Alamos National Laboratory. 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. 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, sie wandten sich aber selbst ebenfalls bald darauf anderen Forschungsthemen (Plasmaphysik) zu. ⓘ

Definitionen

Es besteht kein Konsens darüber, wie Monte Carlo definiert werden sollte. Ripley beispielsweise definiert die meisten probabilistischen Modellierungen als stochastische Simulationen, wobei Monte Carlo für die Monte-Carlo-Integration und statistische Monte-Carlo-Tests reserviert ist. Sawilowsky unterscheidet zwischen einer Simulation, einer Monte-Carlo-Methode und einer Monte-Carlo-Simulation: Eine Simulation ist eine fiktive Darstellung der Realität, eine Monte-Carlo-Methode ist eine Technik, die zur Lösung eines mathematischen oder statistischen Problems verwendet werden kann, und eine Monte-Carlo-Simulation verwendet wiederholte Stichproben, um die statistischen Eigenschaften eines Phänomens (oder Verhaltens) zu erhalten. Beispiele:

• Simulation: Das Ziehen einer pseudozufälligen, gleichförmigen Variablen aus dem Intervall [0,1] kann verwendet werden, um den Wurf einer Münze zu simulieren: Wenn der Wert kleiner oder gleich 0,50 ist, wird das Ergebnis als Kopf bezeichnet, wenn der Wert jedoch größer als 0,50 ist, wird das Ergebnis als Zahl bezeichnet. Es handelt sich um eine Simulation, aber nicht um eine Monte-Carlo-Simulation.
• Monte-Carlo-Methode: Eine Schachtel mit Münzen auf einen Tisch zu legen und dann das Verhältnis von Kopf zu Zahl zu berechnen, ist eine Monte-Carlo-Methode, um das Verhalten von wiederholten Münzwürfen zu bestimmen, aber keine Simulation.
• Monte-Carlo-Simulation: Das Ziehen einer großen Anzahl pseudozufälliger gleichförmiger Variablen aus dem Intervall [0,1] zu einem Zeitpunkt oder einmal zu vielen verschiedenen Zeitpunkten und das Zuweisen von Werten kleiner oder gleich 0,50 als Kopf und größer als 0,50 als Zahl ist eine Monte-Carlo-Simulation des Verhaltens bei wiederholtem Werfen einer Münze. ⓘ

Kalos und Whitlock weisen darauf hin, dass solche Unterscheidungen nicht immer leicht zu treffen sind. Die Emission von Strahlung aus Atomen ist zum Beispiel ein natürlicher stochastischer Prozess. Er kann direkt simuliert werden, oder sein durchschnittliches Verhalten kann durch stochastische Gleichungen beschrieben werden, die ihrerseits mit Monte-Carlo-Methoden gelöst werden können. "In der Tat kann derselbe Computercode gleichzeitig als 'natürliche Simulation' oder als Lösung der Gleichungen durch natürliche Stichproben betrachtet werden. ⓘ

Monte Carlo und Zufallszahlen

Der Grundgedanke dieser Methode ist, dass die Ergebnisse auf der Grundlage wiederholter Zufallsstichproben und statistischer Analysen berechnet werden. Bei der Monte-Carlo-Simulation handelt es sich in der Tat um Zufallsexperimente, wobei die Ergebnisse dieser Experimente nicht genau bekannt sind. Monte-Carlo-Simulationen sind in der Regel durch viele unbekannte Parameter gekennzeichnet, von denen viele nur schwer experimentell zu ermitteln sind. Monte-Carlo-Simulationsmethoden erfordern nicht immer echte Zufallszahlen, um nützlich zu sein (obwohl für einige Anwendungen, wie z. B. die Primzahlprüfung, Unvorhersehbarkeit unerlässlich ist). Viele der nützlichsten Techniken verwenden deterministische, pseudozufällige Sequenzen, die das Testen und Wiederholen von Simulationen erleichtern. Die einzige Eigenschaft, die in der Regel für gute Simulationen erforderlich ist, besteht darin, dass die Pseudo-Zufallssequenz in einem bestimmten Sinne "zufällig genug" erscheint. ⓘ

Was dies bedeutet, hängt von der jeweiligen Anwendung ab, aber in der Regel sollten sie eine Reihe von statistischen Tests bestehen. Zu den einfachsten und gängigsten Tests gehört die Prüfung, ob die Zahlen gleichmäßig verteilt sind oder einer anderen gewünschten Verteilung folgen, wenn eine ausreichend große Anzahl von Elementen der Sequenz betrachtet wird. Schwache Korrelationen zwischen aufeinanderfolgenden Stichproben sind ebenfalls oft wünschenswert/notwendig. ⓘ

Sawilowsky listet die Merkmale einer hochwertigen Monte-Carlo-Simulation auf:

• der (Pseudo-Zufalls-)Zahlengenerator weist bestimmte Merkmale auf (z. B. eine lange "Periode", bevor sich die Sequenz wiederholt)
• der (Pseudo-Zufalls-)Zahlengenerator erzeugt Werte, die Tests auf Zufälligkeit bestehen
• es gibt genügend Stichproben, um genaue Ergebnisse zu gewährleisten
• die richtige Stichprobentechnik verwendet wird
• der verwendete Algorithmus ist für das zu modellierende Phänomen geeignet
• er simuliert das betreffende Phänomen. ⓘ

Pseudo-Zufallszahlen-Stichprobenalgorithmen werden verwendet, um gleichmäßig verteilte Pseudo-Zufallszahlen in Zahlen umzuwandeln, die gemäß einer bestimmten Wahrscheinlichkeitsverteilung verteilt sind. ⓘ

Sequenzen mit geringer Diskrepanz werden häufig anstelle von Zufallsstichproben aus einem Raum verwendet, da sie eine gleichmäßige Abdeckung gewährleisten und normalerweise eine schnellere Konvergenzordnung aufweisen als Monte-Carlo-Simulationen mit Zufalls- oder Pseudozufallssequenzen. Methoden, die auf ihrer Verwendung beruhen, werden Quasi-Monte-Carlo-Methoden genannt. ⓘ

Um die Auswirkungen der Qualität von Zufallszahlen auf die Ergebnisse von Monte-Carlo-Simulationen zu bewerten, testeten astrophysikalische Forscher kryptografisch sichere Pseudozufallszahlen, die mit Intels RDRAND-Befehlssatz erzeugt wurden, im Vergleich zu solchen, die aus Algorithmen wie dem Mersenne-Twister abgeleitet wurden, in Monte-Carlo-Simulationen von Radioeruptionen aus braunen Zwergen. RDRAND ist der Pseudozufallszahlengenerator, der einem echten Zufallszahlengenerator am nächsten kommt. Bei Versuchen, die aus der Erzeugung von 10⁷ Zufallszahlen bestehen, wurde kein statistisch signifikanter Unterschied zwischen Modellen, die mit typischen Pseudo-Zufallszahlengeneratoren erzeugt wurden, und RDRAND festgestellt. ⓘ

Monte-Carlo-Simulation versus "Was wäre wenn"-Szenarien

Es gibt Möglichkeiten der Verwendung von Wahrscheinlichkeiten, die definitiv keine Monte-Carlo-Simulationen sind - zum Beispiel die deterministische Modellierung unter Verwendung von Ein-Punkt-Schätzungen. Jeder unsicheren Variablen innerhalb eines Modells wird eine "bestmögliche" Schätzung zugewiesen. Für jede Eingabevariable werden Szenarien (z. B. der beste, schlechteste oder wahrscheinlichste Fall) ausgewählt und die Ergebnisse aufgezeichnet. ⓘ

Im Gegensatz dazu werden bei Monte-Carlo-Simulationen Stichproben aus einer Wahrscheinlichkeitsverteilung für jede Variable gezogen, um Hunderte oder Tausende von möglichen Ergebnissen zu erhalten. Die Ergebnisse werden analysiert, um die Wahrscheinlichkeiten für das Auftreten verschiedener Ergebnisse zu ermitteln. Ein Vergleich eines Tabellenkalkulationsmodells für Baukosten, das mit herkömmlichen "Was-wäre-wenn"-Szenarien durchgeführt wurde, mit einer Monte-Carlo-Simulation und dreieckigen Wahrscheinlichkeitsverteilungen zeigt, dass die Monte-Carlo-Analyse einen engeren Bereich aufweist als die "Was-wäre-wenn"-Analyse. Das liegt daran, dass bei der "Was-wäre-wenn"-Analyse alle Szenarien gleich gewichtet werden (siehe Quantifizierung der Unsicherheit in der Unternehmensfinanzierung), während bei der Monte-Carlo-Methode in den sehr unwahrscheinlichen Regionen kaum Stichproben gezogen werden. Die Stichproben in solchen Regionen werden als "seltene Ereignisse" bezeichnet. ⓘ

Anwendungen

Monte-Carlo-Methoden sind besonders nützlich für die Simulation von Phänomenen mit erheblichen Unsicherheiten bei den Inputs und Systemen mit vielen gekoppelten Freiheitsgraden. Zu den Anwendungsgebieten gehören: ⓘ

Physikalische Wissenschaften

Monte-Carlo-Methoden sind in der Computerphysik, der physikalischen Chemie und verwandten Anwendungsgebieten sehr wichtig und finden vielfältige Anwendung, von komplizierten Berechnungen der Quantenchromodynamik über die Konstruktion von Hitzeschilden und aerodynamischen Formen bis hin zur Modellierung des Strahlungstransports für Berechnungen der Strahlendosimetrie. In der statistischen Physik ist die Monte-Carlo-Molekularmodellierung eine Alternative zur rechnerischen Molekulardynamik, und Monte-Carlo-Methoden werden zur Berechnung statistischer Feldtheorien einfacher Teilchen- und Polymersysteme verwendet. Quanten-Monte-Carlo-Methoden lösen das Vielteilchenproblem für Quantensysteme. In der Strahlungsmaterialwissenschaft basiert die binäre Kollisionsannäherung zur Simulation der Ionenimplantation in der Regel auf einem Monte-Carlo-Ansatz zur Auswahl des nächsten kollidierenden Atoms. In der experimentellen Teilchenphysik werden Monte-Carlo-Methoden eingesetzt, um Detektoren zu entwerfen, ihr Verhalten zu verstehen und experimentelle Daten mit der Theorie zu vergleichen. In der Astrophysik werden sie auf so unterschiedliche Weise eingesetzt, dass sie sowohl die Entwicklung von Galaxien als auch die Übertragung von Mikrowellenstrahlung durch eine raue Planetenoberfläche modellieren. Monte-Carlo-Methoden werden auch in den Ensemble-Modellen verwendet, die die Grundlage für moderne Wettervorhersagen bilden. ⓘ

Technik

Monte-Carlo-Methoden werden in der Technik häufig für Sensitivitätsanalysen und quantitative Wahrscheinlichkeitsanalysen bei der Prozessgestaltung eingesetzt. Die Notwendigkeit ergibt sich aus dem interaktiven, kolinearen und nichtlinearen Verhalten typischer Prozesssimulationen. Ein Beispiel,

• In der Mikroelektronik werden Monte-Carlo-Methoden eingesetzt, um korrelierte und unkorrelierte Schwankungen in analogen und digitalen integrierten Schaltungen zu analysieren.
• In der Geostatistik und Geometallurgie untermauern Monte-Carlo-Methoden den Entwurf von Fließschemata der Mineralienverarbeitung und tragen zur quantitativen Risikoanalyse bei.
• Bei der Analyse von Windenergieerträgen wird der voraussichtliche Energieertrag eines Windparks während seiner Lebensdauer unter Berücksichtigung verschiedener Unsicherheitsgrade (P90, P50 usw.) berechnet.
• Die Auswirkungen der Umweltverschmutzung werden simuliert und Diesel mit Benzin verglichen.
• In der Fluiddynamik, insbesondere in der Dynamik verdünnter Gase, wird die Boltzmann-Gleichung für Fluidströmungen mit endlicher Knudsenzahl mit Hilfe der Monte-Carlo-Methode der direkten Simulation in Kombination mit hocheffizienten Rechenalgorithmen gelöst.
• In der autonomen Robotik kann mit der Monte-Carlo-Lokalisierung die Position eines Roboters bestimmt werden. Sie wird häufig auf stochastische Filter wie den Kalman-Filter oder den Partikelfilter angewandt, der das Herzstück des SLAM-Algorithmus (Simultaneous Localization and Mapping) bildet.
• In der Telekommunikation muss bei der Planung eines drahtlosen Netzes nachgewiesen werden, dass das Design für eine Vielzahl von Szenarien funktioniert, die hauptsächlich von der Anzahl der Nutzer, ihren Standorten und den Diensten abhängen, die sie nutzen wollen. In der Regel werden Monte-Carlo-Methoden verwendet, um diese Benutzer und ihre Zustände zu generieren. Anschließend wird die Leistung des Netzes bewertet, und wenn die Ergebnisse nicht zufriedenstellend sind, wird das Netzdesign einem Optimierungsprozess unterzogen.
• In der Zuverlässigkeitstechnik wird die Monte-Carlo-Simulation verwendet, um die Reaktion auf Systemebene anhand der Reaktion auf Komponentenebene zu berechnen. Bei einem Verkehrsnetz, das einem Erdbeben ausgesetzt ist, kann die Monte-Carlo-Simulation beispielsweise dazu verwendet werden, die k-Terminal-Zuverlässigkeit des Netzes anhand der Ausfallwahrscheinlichkeit seiner Komponenten, z. B. Brücken, Fahrbahnen usw., zu bewerten. Ein weiteres wichtiges Beispiel ist die Anwendung der Monte-Carlo-Methode zur Lösung der G-Renewal-Gleichung des verallgemeinerten Erneuerungsprozesses.
• In der Signalverarbeitung und der Bayes'schen Inferenz sind Partikelfilter und sequentielle Monte-Carlo-Techniken eine Klasse von Mean-Field-Partikel-Methoden zur Abtastung und Berechnung der posterioren Verteilung eines Signalprozesses bei einigen verrauschten und partiellen Beobachtungen unter Verwendung interagierender empirischer Maße.
• Bei der Grundwassermodellierung werden Monte-Carlo-Methoden eingesetzt, um eine große Anzahl von Realisierungen eines heterogenen Parameterfeldes zur Quantifizierung der Modellunsicherheit oder zur Parameterinversion zu erzeugen. ⓘ

Klimawandel und Strahlungsantrieb

Der Zwischenstaatliche Ausschuss für Klimaänderungen (Intergovernmental Panel on Climate Change) setzt Monte-Carlo-Methoden bei der Analyse der Wahrscheinlichkeitsdichtefunktion des Strahlungsantriebs ein. ⓘ

Wahrscheinlichkeitsdichtefunktion (PDF) des ERF aufgrund des gesamten Treibhausgas-, Aerosol- und des gesamten anthropogenen Treibhausgases. Die Treibhausgase bestehen aus WMGHG, Ozon und stratosphärischem Wasserdampf. Die PDFs werden auf der Grundlage der in Tabelle 8.6 angegebenen Unsicherheiten erstellt. Die Kombination der einzelnen HF-Agenten zur Ableitung des Gesamtantriebs über das Industriezeitalter erfolgt durch Monte-Carlo-Simulationen und basiert auf der Methode in Boucher und Haywood (2001). Die PDF des ERF aus Änderungen der Oberflächenalbedo und kombinierten Kondensstreifen und Kondensstreifen-induzierten Zirren sind im gesamten anthropogenen Antrieb enthalten, werden aber nicht als separate PDF dargestellt. Für einige Antriebsmechanismen liegen uns derzeit keine ERF-Schätzungen vor: Ozon, Landnutzung, Sonneneinstrahlung usw. ⓘ

Computergestützte Biologie

Monte-Carlo-Methoden werden in verschiedenen Bereichen der Computerbiologie eingesetzt, zum Beispiel für Bayes'sche Schlussfolgerungen in der Phylogenie oder für die Untersuchung biologischer Systeme wie Genome, Proteine oder Membranen. Je nach gewünschter Genauigkeit können die Systeme im grobkörnigen oder im ab initio-Rahmen untersucht werden. Computersimulationen ermöglichen es uns, die lokale Umgebung eines bestimmten Moleküls zu überwachen, um zu sehen, ob zum Beispiel eine chemische Reaktion stattfindet. In Fällen, in denen die Durchführung eines physikalischen Experiments nicht möglich ist, können Gedankenexperimente durchgeführt werden (z. B. das Aufbrechen von Bindungen, die Einführung von Verunreinigungen an bestimmten Stellen, die Änderung der lokalen/globalen Struktur oder die Einführung externer Felder). ⓘ

Computergrafik

Path Tracing, gelegentlich auch als Monte-Carlo-Ray-Tracing bezeichnet, rendert eine 3D-Szene durch zufällige Verfolgung von Stichproben möglicher Lichtpfade. Durch wiederholte Abtastung eines beliebigen Pixels konvergiert der Durchschnitt der Abtastwerte schließlich zur korrekten Lösung der Rendering-Gleichung, was diese Methode zu einer der physikalisch genauesten 3D-Grafik-Rendering-Methoden macht. ⓘ

Angewandte Statistik

Die Standards für Monte-Carlo-Experimente in der Statistik wurden von Sawilowsky gesetzt. In der angewandten Statistik können Monte-Carlo-Methoden für mindestens vier Zwecke eingesetzt werden:

1. Zum Vergleich konkurrierender Statistiken für kleine Stichproben unter realistischen Datenbedingungen. Obwohl der Fehler vom Typ I und die Potenzeigenschaften von Statistiken für Daten berechnet werden können, die aus klassischen theoretischen Verteilungen (z. B. Normalkurve, Cauchy-Verteilung) für asymptotische Bedingungen (d. h. unendlich kleiner Stichprobenumfang und unendlich kleiner Behandlungseffekt) gezogen wurden, weisen reale Daten häufig keine solchen Verteilungen auf.
2. Bereitstellung von Implementierungen von Hypothesentests, die effizienter sind als exakte Tests, wie z. B. Permutationstests (die oft nicht berechnet werden können), und gleichzeitig genauer sind als kritische Werte für asymptotische Verteilungen.
3. Bereitstellung einer Zufallsstichprobe aus der Posterior-Verteilung bei der Bayes'schen Inferenz. Diese Stichprobe approximiert und fasst alle wesentlichen Merkmale des Posteriors zusammen.
4. Sie liefern effiziente Zufallsschätzungen der Hessian-Matrix der negativen Log-Likelihood-Funktion, die gemittelt werden können, um eine Schätzung der Fisher-Informationsmatrix zu bilden. ⓘ

Monte-Carlo-Methoden sind auch ein Kompromiss zwischen approximativer Randomisierung und Permutationstests. Ein approximativer Randomisierungstest basiert auf einer bestimmten Teilmenge aller Permutationen (was eine potenziell enorme Verwaltung der berücksichtigten Permutationen nach sich zieht). Der Monte-Carlo-Ansatz basiert auf einer bestimmten Anzahl von zufällig gezogenen Permutationen (wobei ein geringer Präzisionsverlust, wenn eine Permutation zweimal - oder häufiger - gezogen wird, gegen die Effizienz eingetauscht wird, dass man nicht nachverfolgen muss, welche Permutationen bereits ausgewählt wurden). ⓘ

Künstliche Intelligenz für Spiele

Monte-Carlo-Methoden wurden zu einer Technik namens Monte-Carlo-Baumsuche weiterentwickelt, die für die Suche nach dem besten Zug in einem Spiel nützlich ist. Mögliche Züge werden in einem Suchbaum organisiert und viele Zufallssimulationen werden verwendet, um das langfristige Potenzial jedes Zuges abzuschätzen. Ein Blackbox-Simulator stellt die Züge des Gegners dar. ⓘ

Die Monte-Carlo-Baumsuche (MCTS) besteht aus vier Schritten:

1. Ausgehend vom Wurzelknoten des Baums werden optimale Unterknoten ausgewählt, bis ein Blattknoten erreicht wird.
2. Erweitern Sie den Blattknoten und wählen Sie eines seiner Kinder.
3. Spielen Sie ein simuliertes Spiel, das mit diesem Knoten beginnt.
4. Verwenden Sie die Ergebnisse dieses simulierten Spiels, um den Knoten und seine Vorgänger zu aktualisieren. ⓘ

Der Nettoeffekt ist, dass sich der Wert eines Knotens, der einen Zug repräsentiert, im Laufe vieler simulierter Spiele erhöht oder verringert, was hoffentlich der Tatsache entspricht, ob dieser Knoten einen guten Zug repräsentiert oder nicht. ⓘ

Die Monte-Carlo-Baumsuche wurde bereits erfolgreich bei Spielen wie Go, Tantrix, Battleship, Havannah und Arimaa eingesetzt. ⓘ

Design und visuelle Darstellung

Monte-Carlo-Methoden sind auch effizient bei der Lösung von gekoppelten integralen Differentialgleichungen von Strahlungsfeldern und Energietransport. Daher wurden diese Methoden bei Berechnungen zur globalen Beleuchtung eingesetzt, die fotorealistische Bilder von virtuellen 3D-Modellen erzeugen, die in Videospielen, Architektur, Design, computergenerierten Filmen und Spezialeffekten im Kino Anwendung finden. ⓘ

Suche und Rettung

Die US-Küstenwache setzt Monte-Carlo-Methoden in ihrer Computermodellierungssoftware SAROPS ein, um die wahrscheinlichen Positionen von Schiffen bei Such- und Rettungsaktionen zu berechnen. Jede Simulation kann bis zu zehntausend Datenpunkte erzeugen, die auf der Grundlage vorgegebener Variablen zufällig verteilt werden. Auf der Grundlage von Extrapolationen dieser Daten werden dann Suchmuster generiert, um die Eindämmungswahrscheinlichkeit (POC) und die Entdeckungswahrscheinlichkeit (POD) zu optimieren, die zusammen eine Gesamterfolgswahrscheinlichkeit (POS) ergeben. Letztlich dient dies als praktische Anwendung der Wahrscheinlichkeitsverteilung, um die schnellste und zweckmäßigste Rettungsmethode zu finden, die sowohl Leben als auch Ressourcen spart. ⓘ

Finanzen und Wirtschaft

Die Monte-Carlo-Simulation wird häufig verwendet, um das Risiko und die Ungewissheit zu bewerten, die das Ergebnis verschiedener Entscheidungsoptionen beeinflussen würden. Die Monte-Carlo-Simulation ermöglicht es dem Unternehmensrisikoanalysten, die Gesamtauswirkungen der Ungewissheit von Variablen wie Umsatzvolumen, Rohstoff- und Arbeitspreisen, Zinssätzen und Wechselkursen sowie die Auswirkungen bestimmter Risikoereignisse wie die Kündigung eines Vertrags oder die Änderung eines Steuergesetzes zu berücksichtigen. ⓘ

Monte-Carlo-Methoden im Finanzwesen werden häufig zur Bewertung von Investitionen in Projekte auf Geschäftsfeld- oder Unternehmensebene oder für andere finanzielle Bewertungen eingesetzt. Sie können zur Modellierung von Projektzeitplänen verwendet werden, wobei die Simulationen Schätzungen für den schlimmsten Fall, den besten Fall und die wahrscheinlichste Dauer für jede Aufgabe zusammenfassen, um die Ergebnisse für das Gesamtprojekt zu bestimmen.[1] Monte-Carlo-Methoden werden auch bei der Optionsbewertung und der Analyse des Ausfallrisikos eingesetzt. Außerdem können sie verwendet werden, um die finanziellen Auswirkungen medizinischer Eingriffe abzuschätzen. ⓘ

Recht

Mit Hilfe eines Monte-Carlo-Ansatzes wurde der potenzielle Wert eines vorgeschlagenen Programms bewertet, das Antragstellerinnen in Wisconsin helfen soll, ihre Anträge auf Unterlassungsanordnungen wegen Belästigung und häuslicher Gewalt erfolgreich zu stellen. Das Programm sollte Frauen helfen, ihre Anträge erfolgreich zu stellen, indem es ihnen mehr Unterstützung bietet und so das Risiko von Vergewaltigungen und körperlichen Übergriffen verringert. Dabei spielten jedoch viele Variablen eine Rolle, die nicht genau abgeschätzt werden konnten, wie z. B. die Wirksamkeit von einstweiligen Verfügungen, die Erfolgsquote von Antragstellern mit und ohne Beistand und viele andere. Im Rahmen der Studie wurden Versuche durchgeführt, bei denen diese Variablen variiert wurden, um zu einer Gesamtschätzung des Erfolgs des vorgeschlagenen Programms als Ganzes zu gelangen. ⓘ

Bibliothekswissenschaft

Die Monte-Carlo-Methode wurde auch verwendet, um die Anzahl der Buchveröffentlichungen in Malaysia auf der Grundlage des Buchgenres zu simulieren. Bei der Monte-Carlo-Simulation wurden die Daten früherer nationaler Buchveröffentlichungen und die Buchpreise je nach Buchgattung auf dem lokalen Markt verwendet. Die Monte-Carlo-Ergebnisse wurden verwendet, um festzustellen, welche Art von Buchgenre die Malaysier bevorzugen, und um die Buchveröffentlichungen zwischen Malaysia und Japan zu vergleichen. ⓘ

Berechnung von Integralen

• Bestimmung von (höherdimensionalen) Integralen, siehe Beispiel ⓘ

Resampling

Untersuchung der Verteilungseigenschaften von Zufallsvariablen unbekannten Verteilungstyps,

• Beispiel: die Ermittlung der nichtzentralen Verteilung des Korrelationskoeffizienten. Mit Hilfe von Zufallszahlen wird die Realisierung beliebig vieler Korrelationskoeffizienten simuliert. Eine Zusammenfassung der Koeffizienten in eine Häufigkeitstabelle ergibt eine empirische Verteilungsfunktion oder ein Histogramm.
• die Eigenschaften von Schätzfunktionen bei Vorliegen von Ausreißern in Daten. Mit Hilfe der Simulation kann gezeigt werden, dass das arithmetische Mittel nicht mehr ein bester Schätzer für den Erwartungswert ist.
• die Schätzung von Verteilungsparametern. ⓘ

Nachbildung von komplexen Prozessen

• Produktionsprozesse in einem Fertigungsunternehmen, um Engpässe und Opportunitäten in der Produktion aufzudecken
• Klimamodelle
• Rekonstruktionsverfahren in der Nuklearmedizin.
• Risikoaggregation zur Bestimmung des Gesamtrisikoumfangs eines Unternehmens im Risikomanagement
• Ableitung von Bewertungen in der Wertermittlung, z. B. bei der Unternehmensbewertung oder Immobilienwirtschaft. Bepreisung komplexer Finanzkontrakte wie „exotische“ Optionen, bei denen keine analytische Formel für die Bewertung eines Finanzproduktes bekannt ist.
• räumliche Verteilung des energieabhängigen Neutronenflusses in einem heterogenen Medium, etwa im Blanket eines Kernfusionsreaktors.
• Supercomputer und MC Methoden werden u. a. für die Simulation der alternden Nuklearwaffen (siehe auch Stockpile stewardship) der USA benutzt.
• Wege eines einzelnen Regentropfens simulieren, der mit zufällig verteilten anderen Tropfen kollidiert. Nach der Simulation mehrerer konkreter Tropfen sind Aussagen über die durchschnittliche Tropfengröße möglich oder auch zu Temperatur und Tröpfchendichte, bei denen Schnee oder Hagel entstehen.
• Verteilung der Kugeln auf die Fächer beim Galtonbrett. ⓘ

Anwendung in der Mathematik

Im Allgemeinen werden Monte-Carlo-Methoden in der Mathematik verwendet, um verschiedene Probleme zu lösen, indem geeignete Zufallszahlen erzeugt werden (siehe auch Zufallszahlengenerierung) und der Teil der Zahlen beobachtet wird, der eine oder mehrere Eigenschaften erfüllt. Die Methode ist nützlich, um numerische Lösungen für Probleme zu erhalten, die zu kompliziert sind, um sie analytisch zu lösen. Die häufigste Anwendung der Monte-Carlo-Methode ist die Monte-Carlo-Integration. ⓘ

Integration

Bei der Monte-Carlo-Integration werden zufällige Punkte mit dem Wert der Funktion verglichen. ⓘ

Fehler reduzieren sich um einen Faktor von $\scriptstyle 1/{\sqrt {N}}$ ⓘ

Deterministische numerische Integrationsalgorithmen funktionieren gut bei einer geringen Anzahl von Dimensionen, stoßen aber auf zwei Probleme, wenn die Funktionen viele Variablen haben. Erstens steigt die Anzahl der benötigten Funktionsauswertungen schnell mit der Anzahl der Dimensionen. Wenn beispielsweise 10 Auswertungen eine ausreichende Genauigkeit in einer Dimension bieten, werden für ¹⁰⁰ Dimensionen 10100 Punkte benötigt - viel zu viele, um berechnet zu werden. Dies wird als Fluch der Dimensionalität bezeichnet. Zweitens kann die Grenze einer mehrdimensionalen Region sehr kompliziert sein, so dass es unter Umständen nicht möglich ist, das Problem auf ein iteratives Integral zu reduzieren. 100 Dimensionen sind keineswegs ungewöhnlich, denn bei vielen physikalischen Problemen ist eine "Dimension" gleichbedeutend mit einem Freiheitsgrad. ⓘ

Monte-Carlo-Methoden bieten einen Ausweg aus diesem exponentiellen Anstieg der Berechnungszeit. Solange sich die fragliche Funktion einigermaßen gut verhält, kann sie geschätzt werden, indem man zufällig Punkte im 100-dimensionalen Raum auswählt und eine Art Durchschnitt der Funktionswerte an diesen Punkten bildet. Nach dem zentralen Grenzwertsatz zeigt diese Methode $\scriptstyle 1/{\sqrt {N}}$ Konvergenz, d. h. eine Vervierfachung der Anzahl der Stichprobenpunkte halbiert den Fehler, unabhängig von der Anzahl der Dimensionen. ⓘ

Eine Verfeinerung dieser Methode, die in der Statistik als Wichtigkeitssampling bekannt ist, besteht darin, die Punkte nach dem Zufallsprinzip zu samplen, aber häufiger, wenn der Integrand groß ist. Um dies genau zu tun, müsste man das Integral bereits kennen, aber man kann das Integral durch ein Integral einer ähnlichen Funktion annähern oder adaptive Routinen wie stratified sampling, recursive stratified sampling, adaptive umbrella sampling oder den VEGAS-Algorithmus verwenden. ⓘ

Ein ähnlicher Ansatz, die Quasi-Monte-Carlo-Methode, verwendet Sequenzen mit geringer Diskrepanz. Diese Sequenzen "füllen" das Gebiet besser aus und nehmen die wichtigsten Punkte häufiger auf, so dass Quasi-Monte-Carlo-Methoden oft schneller zum Integral konvergieren können. ⓘ

Eine andere Klasse von Methoden zur Stichprobennahme von Punkten in einem Volumen besteht darin, zufällige Spaziergänge über das Volumen zu simulieren (Markov chain Monte Carlo). Zu diesen Methoden gehören der Metropolis-Hastings-Algorithmus, das Gibbs-Sampling, der Wang- und Landau-Algorithmus und interaktive MCMC-Methoden wie die sequentiellen Monte-Carlo-Sampler. ⓘ

Das obige Beispiel zur Bestimmung von Pi bildet praktisch das Flächenintegral einer Viertelkreisfläche. Entsprechend kann man das Flächenintegral allgemeiner, auch höherdimensionaler Funktionen nach dieser Methode berechnen. Soll das Integral ⓘ

$S(f)=\int _{0}^{1}f(x)\,dx$ ⓘ

einer Funktion $f$ berechnet werden, dann wählt man $m$ unabhängige im Intervall $[0,1]$ gleichverteilte Punkte $x_{1},\dots ,x_{m}$ und approximiert $S(f)$ durch ⓘ

Im allgemeineren Fall von höherdimensionalen Funktionen ist das Vorgehen ähnlich. Sei $K\subset \mathbb {R} ^{n}$ eine beliebige $n$-dimensionale Menge und $f\colon K\rightarrow \mathbb {R}$ eine integrierbare Funktion. Um den Wert ⓘ

$S(f)=\int _{K}f(x)\,dx$ ⓘ

näherungsweise zu berechnen, wählt man zufällig in der Menge $K$ gleichverteilte Punkte $x_{i}$ für $i=1,\dots ,m$. Dann approximiert ⓘ

den Wert $S(f)$ in Abhängigkeit von $m$ beliebig genau. Um wie oben vorgestellt Pi zu berechnen, muss man $K:=[-1,1]^{2}$ und $f:=\chi _{\mathrm {Kreis} }$ als charakteristische Funktion des Einheitskreises wählen. Hier ist $S(\chi _{\mathrm {Kreis} })=\pi$ gerade die Fläche des Einheitskreises. ⓘ

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. In diesen Fällen erlauben insbesondere MCMC-Verfahren die Erzeugung von Stichproben mit einer Verteilung die eine effiziente Berechnung solcher hochdimensionaler Integrale erlaubt. ⓘ

Simulation und Optimierung

Eine weitere leistungsstarke und sehr beliebte Anwendung für Zufallszahlen in der numerischen Simulation ist die numerische Optimierung. Das Problem besteht darin, Funktionen eines Vektors, der oft viele Dimensionen hat, zu minimieren (oder zu maximieren). Viele Probleme lassen sich auf diese Weise formulieren: Bei einem Computerschachprogramm könnte man zum Beispiel versuchen, die Menge von, sagen wir, 10 Zügen zu finden, die am Ende die beste Bewertungsfunktion ergibt. Beim Problem des Handelsreisenden besteht das Ziel darin, die zurückgelegte Strecke zu minimieren. Es gibt auch Anwendungen für die technische Planung, wie z. B. die multidisziplinäre Planungsoptimierung. Es wurde mit quasi-eindimensionalen Modellen angewandt, um Probleme der Partikeldynamik durch effiziente Erkundung eines großen Konfigurationsraums zu lösen. Die Referenz ist eine umfassende Übersicht über viele Themen im Zusammenhang mit Simulation und Optimierung. ⓘ

Das Traveling-Salesman-Problem ist ein so genanntes konventionelles Optimierungsproblem. Das heißt, alle Fakten (Entfernungen zwischen den einzelnen Zielpunkten), die zur Bestimmung des optimalen Weges benötigt werden, sind mit Sicherheit bekannt, und das Ziel ist es, die möglichen Reiseoptionen durchzugehen, um diejenige mit der geringsten Gesamtentfernung zu finden. Nehmen wir jedoch an, dass wir nicht die Gesamtentfernung für jedes gewünschte Ziel minimieren wollen, sondern die Gesamtzeit, die für das Erreichen jedes Ziels benötigt wird. Dies geht über die herkömmliche Optimierung hinaus, da die Reisezeit von Natur aus unsicher ist (Staus, Tageszeit usw.). Um den optimalen Weg zu finden, sollten wir daher eine Simulationsoptimierung durchführen, um zunächst den Bereich möglicher Fahrzeiten von einem Punkt zum anderen zu ermitteln (in diesem Fall durch eine Wahrscheinlichkeitsverteilung und nicht durch eine bestimmte Entfernung dargestellt) und dann unsere Reiseentscheidungen zu optimieren, um den besten Weg unter Berücksichtigung dieser Unsicherheit zu finden. ⓘ

Inverse Probleme

Die probabilistische Formulierung von inversen Problemen führt zur Definition einer Wahrscheinlichkeitsverteilung im Modellraum. Diese Wahrscheinlichkeitsverteilung kombiniert vorherige Informationen mit neuen Informationen, die durch die Messung einiger beobachtbarer Parameter (Daten) gewonnen wurden. Da die Theorie, die die Daten mit den Modellparametern verknüpft, im Allgemeinen nichtlinear ist, kann die posteriore Wahrscheinlichkeit im Modellraum nicht einfach zu beschreiben sein (sie kann multimodal sein, einige Momente können nicht definiert sein usw.). ⓘ

Bei der Analyse eines inversen Problems reicht es in der Regel nicht aus, ein Maximum-Likelihood-Modell zu erhalten, da wir normalerweise auch Informationen über das Auflösungsvermögen der Daten haben möchten. Im allgemeinen Fall können wir viele Modellparameter haben, und eine Untersuchung der interessierenden Randwahrscheinlichkeitsdichten kann unpraktisch oder sogar nutzlos sein. Es ist jedoch möglich, pseudozufällig eine große Sammlung von Modellen gemäß der posterioren Wahrscheinlichkeitsverteilung zu erzeugen und die Modelle so zu analysieren und darzustellen, dass dem Betrachter Informationen über die relativen Wahrscheinlichkeiten der Modelleigenschaften vermittelt werden. Dies kann mit Hilfe einer effizienten Monte-Carlo-Methode erreicht werden, selbst in Fällen, in denen keine explizite Formel für die A-priori-Verteilung verfügbar ist. ⓘ

Die bekannteste Methode des Wichtigkeitssamplings, der Metropolis-Algorithmus, kann verallgemeinert werden, wodurch eine Methode entsteht, die die Analyse von (möglicherweise hochgradig nichtlinearen) inversen Problemen mit komplexen a priori Informationen und Daten mit einer beliebigen Rauschverteilung ermöglicht. ⓘ

Philosophie

Eine populäre Darstellung der Monte-Carlo-Methode wurde von McCracken vorgenommen. Die allgemeine Philosophie der Methode wurde von Elishakoff und Grüne-Yanoff und Weirich diskutiert. ⓘ

Mathematik

Mathematisch ist das System ein wahrscheinlichkeitsgewichteter Weg im Phasenraum (allgemein Zustandsraum). Monte-Carlo-Simulationen sind besonders geeignet, um statistische Mittelwerte einer Größe ${\mathcal {A}}$, ⓘ

$\left\langle {\mathcal {A}}\right\rangle =\sum _{x\in \Omega }P(x)\,{\mathcal {A}}(x),$ ⓘ

oder hochdimensionale Integrale (Monte-Carlo-Integration) wie ⓘ

$\int _{x\in \Omega }\!\!P(x)\,{\mathcal {A}}(x)\;\mathrm {d} ^{n}x$ ⓘ

zu berechnen. $P(x)$ soll in diesem Zusammenhang ein normiertes statistisches Gewicht (etwa ein Boltzmanngewicht) sein. ${\mathcal {A}}(x)$ ist der Wert der Größe ${\mathcal {A}}$ im Zustand $x$. Die Summation bzw. Integration verläuft hier über einen Raum $\Omega$, also der Phasenraum der Teilchen im System. ⓘ

Häufig ist der Raum $\Omega$ so groß, dass die Summation nicht vollständig durchgeführt werden kann. Stattdessen erzeugt man nun eine Markow-Kette $x_{1},x_{2},x_{3},\ldots$ von Zuständen in $\Omega$, deren Häufigkeit wie das vorgegebene Gewicht $P(x)$ verteilt ist. Bereiche des Raumes $\Omega$ mit hohem Gewicht sollen also häufiger in der Markow-Kette vertreten sein als Bereiche mit niedrigem Gewicht. Man spricht hier von Importance Sampling. Gelingt dies, so lassen sich die Erwartungswerte einfach als arithmetisches Mittel der Größe ${\mathcal {A}}$ zu diesen Zuständen der Markow-Kette berechnen, also als ⓘ

$\left\langle {\mathcal {A}}\right\rangle \approx {\frac {1}{N}}\sum _{i=1}^{N}{\mathcal {A}}(x_{i}).$ ⓘ

Dieser Zusammenhang basiert auf dem Gesetz der großen Zahlen. Je nach physikalischem System kann es schwierig sein, diese Markow-Kette zu erzeugen. Insbesondere ist sicherzustellen, dass die Markow-Kette tatsächlich den gesamten Raum $\Omega$ bedeckt und nicht nur einen Teil des Raumes abtastet. Man sagt: der Algorithmus muss ergodisch sein. ⓘ

Quasi-Monte-Carlo-Simulationen verwenden keine Pseudozufallszahlen, sondern eine Sequenz mit geringer Diskrepanz (zum Beispiel eine Sobol-Sequenz). ⓘ

Beispiele

Illustration zur Monte-Carlo-Bestimmung von Pi. ⓘ

Miller-Rabin-Primzahltest

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. ⓘ

Programmpakete (Auswahl)

• MCNP, der Monte-Carlo N-Particle Transport Code, ist ein prototypisches, weltweit verbreitetes reaktorphysikalisches Programm, das sehr häufig angewendet wird, auch in der Kerntechnik und der Kernfusionstechnik. Die aktuelle Version ist MCNP6.2. Auf der MCNP-Webseite sind Handbücher und Release Notes als Internetdokumente zu finden, zum Beispiel der Band I des MCNP-Handbuchs Overview and Theory. ⓘ

• PYTHIA ist ein Simulationsprogramm für die Teilchenphysik und simuliert Kollisionen und dabei entstehende Teilchen. ⓘ

• SPICE ist ein Simulationsprogramm für analoge, digitale und gemischte elektronische Schaltungen. Mit der Monte-Carlo-Simulation ist es möglich, die Auswirkungen der Streuung der Bauteilewerte innerhalb der angegebenen Toleranz zu berechnen. ⓘ