imported>Punkgioy: /* growthexperiments-addlink-summary-summary:1|0|0 */

2025-06-10T13:59:57Z

growthexperiments-addlink-summary-summary:1|0|0

Neue Seite

'''Monte-Carlo-Algorithmen''' sind [[Randomisierter Algorithmus|randomisierte Algorithmen]], die mit einer nichttrivial nach oben beschränkten Wahrscheinlichkeit ein falsches Ergebnis liefern. Dafür sind sie im Vergleich zu deterministischen Algorithmen häufig effizienter. Durch Wiederholen des Algorithmus mit unabhängigen Zufallszahlen kann jedoch die [[Fehler 1. Art|Fehlerwahrscheinlichkeit]] gesenkt werden (''Probability Amplification'', weitere Einzelheiten im Artikel [[Randomisierter Algorithmus]]). Im Gegensatz zu Monte-Carlo-Algorithmen dürfen [[Las-Vegas-Algorithmus|Las-Vegas-Algorithmen]] nur korrekte Lösungen berechnen.

Monte-Carlo-Algorithmen dienen als Basis für [[Monte-Carlo-Simulation]]en.

== Ein- und zweiseitiger Fehler ==
Monte-Carlo-Algorithmen gibt es für
* [[Suchproblem]]e<ref>Suchprobleme sind Aufgaben, bei denen eine Lösung zu berechnen ist.</ref>
* [[Entscheidbar|Entscheidungsprobleme]].<ref>Entscheidungsprobleme sind Aufgaben, bei denen eine Ja/Nein-Frage zu beantworten ist.</ref> Hier wird zwischen ein- und zweiseitigen Fehlern unterschieden:
** Bei einem zweiseitigen Fehler darf ein Monte-Carlo-Algorithmus sowohl ''[[Falsch positiv|false Positives]]'' liefern (also die Ausgabe Ja, obwohl Nein richtig wäre), als auch ''[[Falsch negativ|false Negatives]]'' (also die Ausgabe Nein, obwohl Ja richtig wäre).
** Bei einseitigem Fehler ist nur eine der beiden Fehlermöglichkeiten erlaubt. Eine häufige Vereinbarung besteht darin, von einem einseitigen Fehler zu sprechen und damit „false Negatives“ zu meinen.
* die [[Numerische Integration#Monte-Carlo-Integration|Numerische Integration]]

Diese Konzepte werden im folgenden Abschnitt verdeutlicht, in dem [[Komplexitätsklasse]]n für Probleme mit Monte-Carlo-Algorithmen definiert werden.

== Komplexitätsklassen für Entscheidungsprobleme mit randomisierten Algorithmen ==
* ''[[BPP (Komplexitätsklasse)|BPP]]'' (von {{enS|bounded error probabilistic polynomial time}}) ist die Menge der Entscheidungsprobleme, für die es einen polynomiell zeitbeschränkten randomisierten Algorithmus mit den folgenden Eigenschaften gibt: Wenn die korrekte Ausgabe Ja (Nein) lautet, beträgt die Wahrscheinlichkeit, dass der Algorithmus Ja (oder Nein) ausgibt, mindestens 2/3.
* ''[[RP (Komplexitätsklasse)|RP]]'' (von {{enS|randomized polynomial time}}) ist die Menge der Entscheidungsprobleme, für die es einen polynomiell zeitbeschränkten randomisierten Algorithmus mit den folgenden Eigenschaften gibt: Wenn die korrekte Ausgabe Ja lautet, beträgt die Wahrscheinlichkeit, dass der Algorithmus Ja ausgibt, mindestens 1/2. Wenn die korrekte Ausgabe Nein lautet, beträgt die Wahrscheinlichkeit, dass der Algorithmus Nein ausgibt, 1.
* ''co-RP'' ist die Menge der Entscheidungsprobleme, für die es einen polynomiell zeitbeschränkten randomisierten Algorithmus mit den folgenden Eigenschaften gibt: Wenn die korrekte Ausgabe Ja lautet, beträgt die Wahrscheinlichkeit, dass der Algorithmus Ja ausgibt, 1; wenn die korrekte Ausgabe Nein lautet, beträgt die Wahrscheinlichkeit, dass der Algorithmus Nein ausgibt, mindestens 1/2. Damit enthält co-RP die [[Komplement (Mengenlehre)|Komplemente]] der Probleme in RP.

Die angegebenen Schranken für die Wahrscheinlichkeiten müssen jeweils für alle Eingaben gelten; die Wahrscheinlichkeiten beziehen sich jeweils nur auf die vom Algorithmus verwendeten Zufallsbits (und nicht auf die Eingabe, die Eingabe wird also nicht als zufällig aufgefasst). Mit Hilfe von Probability Amplification kann man zeigen, dass die Konstante 2/3 aus der Definition von BPP durch jede andere Konstante aus dem Intervall (1/2,1) ersetzt werden kann, ohne die Menge BPP zu ändern; ebenso kann in den Definitionen von RP und co-RP die Konstante 1/2 durch jede Konstante aus dem Intervall (0,1) ersetzt werden.

Obwohl BPP und RP Mengen von Problemen sind, werden im allgemeinen Sprachgebrauch häufig Begriffe wie BPP-Algorithmen oder RP-Algorithmen benutzt, um Algorithmen mit den oben definierten Eigenschaften zu bezeichnen.

Zur Verdeutlichung der Definition von RP: Wenn ein RP-Algorithmus die Ausgabe Ja liefert, wissen wir mit Sicherheit, dass die Ausgabe Ja korrekt ist (da die Definition sicherstellt, dass bei korrekter Ausgabe Nein dies auf jeden Fall auch ausgegeben wird). Wenn dagegen ein RP-Algorithmus die Ausgabe Nein liefert, wissen wir nichts über die korrekte Ausgabe (da nach der Definition die Ausgabe Nein möglich ist, wenn Ja oder Nein korrekt wäre).

== Methoden ==
=== MCMC-Verfahren ===
{{Hauptartikel|MCMC-Verfahren}}
Häufig ist der Raum <math>\Omega</math> so groß, dass die Summation nicht vollständig durchgeführt werden kann.
Stattdessen erzeugt man eine [[Markow-Kette]] <math>x_1,x_2,x_3,\ldots</math> von Zuständen in <math>\Omega</math>, deren Häufigkeit wie das vorgegebene Gewicht <math>P</math> verteilt ist: <math>X_i\sim P</math>
Bereiche des Raumes <math>\Omega</math> (bzw. Realisierungen) mit hoher Wahrscheinlichkeit <math>P</math> 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 <math>f</math> ausgewertet an den Realisierungen der Markow-Kette berechnen, also als

: <math>\hat{E}_X[f(X)]= \frac{1}{N}\sum_{i=1}^N f(x_i).</math>

Dieser Zusammenhang basiert auf dem [[Gesetz der großen Zahlen]].
Die Varianz <math>Var[\hat{E}_X[f(X)]]</math> 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 <math>\Omega</math> bedeckt und nicht nur einen Teil des Raumes abtastet. Man sagt: der Algorithmus muss ''[[Ergodizität|ergodisch]]'' sein.

Alle folgenden Algorithmen gehören zu den [[MCMC-Verfahren|Markov-Chain-Monte-Carlo-Verfahren]] (MCMC).

==== Metropolis-Algorithmus ====
{{Hauptartikel|Metropolis-Algorithmus}}
Der von Nicholas Metropolis publizierte Metropolis-Algorithmus zur Untersuchung [[Statistische Mechanik|statistisch-mechanischer]] Systeme mittels [[Computersimulation]] leitet sich von der Monte-Carlo-Integration ab. Ein Spezialfall des Algorithmus ist das [[Gibbs-Sampling]].

==== Sequenzielle Monte-Carlo-Methode (SMC) ====
{{Hauptartikel|Sequenzielle Monte-Carlo-Methode}}
Sequenzielle Monte-Carlo-Methoden eignen sich zur [[Bayessche Statistik|Bayesschen]] Zustandsschätzung von dynamischen Systemen. Ziel ist es, den Systemzustand als Funktion der Zeit auf Basis einer Reihe von Beobachtungen des Systems und [[A priori|A-priori-Kenntnissen]] der Systemdynamik zu schätzen. Dazu wird die komplizierte Wahrscheinlichkeitsdichte des Zustandes diskret durch eine Menge von Partikeln approximiert. Sequentielle Monte-Carlo-Methoden werden auch Partikelfilter genannt.

==== Quanten-Monte-Carlo-Methoden (QMC) ====
{{Hauptartikel|Quanten-Monte-Carlo-Methode}}
[[Quanten-Monte-Carlo-Methode]]n werden zur Berechnung physikalischer Observablen in [[Quantenfeldtheorie|quantenfeldtheoretischen]] Modellen benutzt. Beispiele sind Modelle aus der theoretischen [[Festkörperphysik]] wie das [[Hubbard-Modell]] oder das [[tJ-Modell]].

==== Kinetische Monte-Carlo-Methode ====
{{Hauptartikel|Quanten-Monte-Carlo-Methode}}
Die [[kinetische Monte-Carlo-Methode]] erlaubt es den zeitlichen Fortschritt eines Systems zu simulieren.

==== Cluster-Algorithmen ====
Cluster-Algorithmen sind nicht-lokale Verfahren. Hierzu zählen der [[Swendsen-Wang-Algorithmus]] und der [[Wolff-Algorithmus]].

==== Hybrid-Monte-Carlo-Algorithmus ====
{{Hauptartikel|Hybrid-Monte-Carlo-Algorithmus}}
Der Hybrid-Monte-Carlo-Algorithmus ist ein Monte-Carlo-Algorithmus zur Erzeugung von Systemen im kanonischen Zustand. Das Verfahren ist eine Kombination aus Molekulardynamik und Monte-Carlo Methoden her: neue Konfigurationen werden mithilfe von Molekulardynamik vorgeschlagen, jedoch müssen die vorgeschlagenen Konfigurationen z. B. durch das Akzeptanzkriterium akzeptiert werden.

==== Quasi-Monte-Carlo ====
Quasi-Monte-Carlo-Simulationen verwenden keine [[Pseudozufallszahl]]en, sondern eine [[Sequenz mit geringer Diskrepanz]] (zum Beispiel eine [[Sobol-Sequenz]]) um [[Varianzreduktion]] zu erreichen.

== Importance Sampling ==
{{Hauptartikel|Importance Sampling}}
Soll die Varianz des Mittelwertschätzers verringert werden, so können die Stichproben nicht gemäß <math>X_i\sim P</math> gezogen werden, sondern aus einer [[Varianzreduktion|varianzreduzierenden]] Verteilung <math>Y_i\sim W</math>, diese Verteilung <math>W</math> wird im [[Importance Sampling]] auch als „biased distribution“, „proposal distribution“ oder „sample distribution“ bezeichnet.

== Siehe auch ==
* [[Liste von Algorithmen]]

== Literatur ==
{{Siehe auch|Monte-Carlo-Simulation|MCMC-Verfahren}}

=== Fachbücher ===
* {{Literatur |Autor=Rajeev Motwani, Prabhakar Raghavan |Titel=Randomized Algorithms |Auflage=1 |Verlag=Cambridge University Press |Datum=1995 |Sprache=en |ISBN=978-0-521-47465-8 |DOI=10.1017/CBO9780511814075}}
* {{Literatur |Autor=[[Thomas Müller-Gronbach]], [[Erich Novak]], [[Klaus Ritter (Mathematiker, 1961)|Klaus Ritter]] |Titel=Monte Carlo-Algorithmen |Verlag=Springer Berlin Heidelberg |Ort=Berlin, Heidelberg |Datum=2012 |Reihe=Springer-Lehrbuch |ISBN=978-3-540-89140-6 |DOI=10.1007/978-3-540-89141-3}}
* {{Literatur |Autor=Adrian Barbu, Song-Chun Zhu |Titel=Monte Carlo Methods |Verlag=Springer Singapore |Ort=Singapore |Datum=2020 |Sprache=en |ISBN=9789811329708 |DOI=10.1007/978-981-13-2971-5}}

== Einzelnachweise ==
<references />

[[Kategorie:Algorithmus]]
[[Kategorie:Computerchemie]]
[[Kategorie:Computerphysik]]

Monte-Carlo-Algorithmus - Versionsgeschichte

imported>Punkgioy: /* growthexperiments-addlink-summary-summary:1|0|0 */