Klassische Monte Carlo Verfahren

Zufallszahlen

Von Natur aus sind Computer deterministisch (Ausnahme: Spezielle Hardware, die z.B. thermisches Rauschen als Quelle von Zufall nutzt). Gesucht sind deshalb Algorithmen, die Zahlenfolgen erzeugen, die ohne Kenntnis des zugrundeliegenden Verfahrens vollkommen zufällig erscheinen.

Das am weitesten verbreitete Verfahren zur Erzeugung von gleichverteilten Pseudo-Zufallszahlen sind linear kongruente Generatoren:

ri+1 = (a ri + c) mod m

Ihre Qualität hängt von der richtigen Wahl von a,c und m ab. Ziel: Lange Periode (am besten m), und wenig Korrelationen.

Zufallszahlen, die anderen Verteilungen genügen, erhält durch direkte Umrechnung aus der Verteilungsfunktion, durch von-Neumann-Rejection, oder andere Tricks (z.B. Box-Müller Verfahren). Für weiterführende Informationen siehe Numerical Recipes.

Direkte Anwendungen

Das naheliegendste Anwendungsgebiet von Zufallszahlen ist die Simulation von Prozessen, die von Natur aus zufällig sind. Man denke etwa an radioaktiven Zerfall oder die Brownsche Bewegung.

Hochdimensionale Summen und Integrale, Statistische Physik

Weitaus wichtiger sind Monte-Carlo Verfahren aber zur Berechnung hochdimensionaler Integrale und Summen. Als einfachstes Beispiel sei die Berechnung des Volumens einer d-dimensionalen Kugel betrachtet.

Effizient werden derartige Summationen meist erst durch geeignete Wichtung. Dies ist auch die Grundlage für die in der Statistischen Physik verwendeten Verfahren zur Berechnung der Zustandssumme und von Erwartungswerten.

Importance Sampling, Local Updates, Metropolis
Der klassische Artikel von Metropolis und Mitarbeitern
Vorlesung von W. Janke (Heraeus-Sommerschule 07)
Cluster Methods
Wolff single-cluster Algorithmus
Übersichtsartikel von W. Krauth
Worm Algorithm
Worm-Algorithmus für klassische Modelle
Worm für Ising-Modell
Contents