Hauptmenü öffnen

Monte-Carlo-Algorithmen sind randomisierte Algorithmen, die mit einer nichttrivial nach oben beschränkten Wahrscheinlichkeit ein falsches Ergebnis liefern dürfen. Dafür sind sie im Vergleich zu deterministischen Algorithmen häufig effizienter. Ihr Nachteil besteht darin, dass das berechnete Ergebnis falsch sein kann. Durch Wiederholen des Algorithmus mit unabhängigen Zufallsbits kann jedoch die Fehlerwahrscheinlichkeit gesenkt werden (Probability Amplification, weitere Einzelheiten im Artikel Randomisierter Algorithmus). Im Gegensatz zu Monte-Carlo-Algorithmen dürfen Las-Vegas-Algorithmen nur korrekte Lösungen berechnen.

Der Name Monte-Carlo hängt laut N. Metropolis 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“.[1]

Ein- und zweiseitiger FehlerBearbeiten

Monte-Carlo-Algorithmen gibt es für

  • Suchprobleme[2]
  • Entscheidungsprobleme.[3] Hier wird zwischen ein- und zweiseitigen Fehlern unterschieden:
    • Bei einem zweiseitigen Fehler darf ein Monte-Carlo-Algorithmus sowohl false Positives liefern (also die Ausgabe Ja, obwohl Nein richtig wäre), als auch 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 „falsch Negatives“ zu meinen.

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

Komplexitätsklassen für Entscheidungsprobleme mit randomisierten AlgorithmenBearbeiten

  • BPP (von englisch 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 (von englisch 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 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).

BeispielanwendungenBearbeiten

Miller-Rabin-PrimzahltestBearbeiten

Ein Beispiel für einen Monte-Carlo-Algorithmus 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.

 
Illustration zur Monte-Carlo-Bestimmung von Pi.

Probabilistische Bestimmung der Zahl PiBearbeiten

Man wählt hierzu zufällige Punkte   aus und überprüft (durch Anwendung des Satzes von Pythagoras), ob diese innerhalb des Einheitskreises liegen:

 .

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

 

Numerische IntegrationBearbeiten

 
Numerische Integration mit Monte Carlo: Die Stützstellen werden zufällig gleichverteilt auf dem Integrationsintervall gewählt. Neue Stützstellen sind dunkelblau, die alten hellblau eingezeichnet. Der Wert des Integrals nähert sich 3,32 an.

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

 

einer Funktion   berechnet werden, dann wählt man   unabhängige im Intervall   gleichverteilte Punkte   und approximiert   durch

 

Im allgemeineren Fall von höherdimensionalen Funktionen ist das Vorgehen ähnlich. Sei   eine beliebige  -dimensionale Menge und   eine integrierbare Funktion. Um den Wert

 

näherungsweise zu berechnen, wählt man zufällig in der Menge   gleichverteilte Punkte   für  . Dann approximiert

 

den Wert   in Abhängigkeit von   beliebig genau. Um wie oben vorgestellt Pi zu berechnen, muss man   und   als charakteristische Funktion des Einheitskreises wählen. Hier ist   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[4]. In diesen Fällen erlauben insbesondere MCMC-Verfahren die Erzeugung von Stichproben mit einer Verteilung die eine effiziente Berechnung solcher hochdimensionaler Integrale erlaubt.

SupercomputerBearbeiten

Heutige Supercomputer (HPC) basieren auf massivem Multiprocessing mit vielen tausend Einzelprozessoren, die parallel arbeiten. Diese Gegebenheiten lassen sich besonders gut mit solchen probabilistischen Lösungsverfahren ausnutzen.[5] Supercomputer und MC Methoden werden u. a. für die Simulation der alternden Nuklearwaffen (siehe auch Stockpile stewardship) der USA benutzt.[6][7][8][9]

Siehe auchBearbeiten

LiteraturBearbeiten

  • R. Motwani, P. Raghavan: Randomized Algorithms. Cambridge University Press, Cambridge 1995, ISBN 0-521-47465-5.
  • Thomas Müller-Gronbach, Erich Novak, Klaus Ritter: Monte Carlo-Algorithmen. Springer-Verlag, Berlin 2012, ISBN 978-3-540-89140-6.

WeblinksBearbeiten

EinzelnachweiseBearbeiten

  1. N. Metropolis: BEGINNING of the MONTE CARLO METHOD. Los Alamos Science Special Issue, 1987, S. 125–130 (fas.org [PDF]).
  2. Suchprobleme sind Aufgaben, bei denen eine Lösung zu berechnen ist.
  3. Entscheidungsprobleme sind Aufgaben, bei denen eine Ja/Nein-Frage zu beantworten ist.
  4. David MacKay: Kapitel 4.4 Typicality & Kapitel 29.1. In: Information Theory, Inference and Learning Algorithms. Cambridge University Press, 2003, ISBN 978-0-521-64298-9.
  5. Prof. A. Bachem in Interview, c't 12/2010, S. 18: So lassen sich probabilistische Lösungsverfahren zumeist weitaus besser parallelisieren als die heute üblichen deterministischen.
  6. MERCURY. Abgerufen am 13. August 2019.
  7. 2014 Jul 10: Trinity supercomputer to support nuclear stockpile simulations -. Abgerufen am 13. August 2019 (englisch).
  8. Nicole Hemsoth: NNSA Stockpile of Nuclear Security Supercomputers Continues Evolution. 16. Juli 2015, abgerufen am 13. August 2019 (amerikanisches Englisch).
  9. Stockpile Stewardship Program. Abgerufen am 13. August 2019.