Wahrscheinlichkeit & Statistik · Monte-Carlo-Methode

Monte-Carlo-Methode

Die Monte-Carlo-Methode schätzt eine Zahl durch zufällige Stichproben. Wirf N Punkte unabhängig und gleichverteilt in ein Einheitsquadrat. Der Anteil in einem Gebiet schätzt dessen Fläche mit einem Standardfehler proportional zu 1/√N. Beobachte, wie sich die Schätzung von π stabilisiert und wie sich ihre Unsicherheit verändert.

Die Monte-Carlo-Methode in dieser Grafik

Eine Monte-Carlo-Methode schätzt eine feste Zahl durch Zufallsstichproben. Hier geht es um eine Fläche: NN Punkte werden gleichverteilt im Einheitsquadrat gezogen, HH davon fallen in ein Gebiet. Dann schätzt H/NH/N dessen Fläche aa. Der Viertelkreis hat den Flächeninhalt π/4\pi/4, also schätzt 4H/N4H/N den Wert π\pi. Unter der Kurve y=e−x2y = e^{-x^2} wird so ein Integral ohne elementare Stammfunktion zur gleichen Art von Zählaufgabe. Die untere Grafik verfolgt die Schätzung, während NN auf eine Million wächst. Sie zeigt auch den Bereich, in den die Schätzung in etwa 95 % der Wiederholungen fallen sollte.

Warum der Anteil die Fläche schätzt

Ein im Quadrat der Fläche 1 gleichverteilter Punkt fällt mit einer Wahrscheinlichkeit in ein Gebiet, die dessen Flächeninhalt entspricht. Jeder Punkt ist ein unabhängiger Versuch mit derselben Trefferwahrscheinlichkeit. Nach dem Gesetz der großen Zahlen nähert sich der Trefferanteil daher aa. Die Form des Gebiets spielt keine Rolle, solange sich entscheiden lässt, ob ein Punkt darin liegt.

Wie genau ist die Schätzung?

Die Trefferzahl ist binomialverteilt. Der Anteil H/NH/N hat daher die Standardabweichung a(1−a)/N\sqrt{a(1-a)/N}. Der typische Fehler schrumpft wie 1/N1/\sqrt{N}: Zehnmal so viele Punkte verringern ihn etwa um den Faktor 10≈3.16\sqrt{10} \approx 3.16. Für einen zehnmal kleineren Fehler braucht man also rund hundertmal so viele Punkte. Selbst bei einer Million Punkten bleibt für π eine Unsicherheit von etwa ±0.003. Zur Abschätzung genügt es, für aa den beobachteten Anteil p^=H/N\hat p = H/N einzusetzen. So erhält man die Spanne ±1.96p^(1−p^)/N\pm 1.96\sqrt{\hat p(1-\hat p)/N} für ein näherungsweises 95-%-Konfidenzintervall, das hier ab zehn Treffern und zehn Fehlschlägen verwendet wird. Würde man den Versuch bei gleichem NN oft wiederholen, verfehlte etwa jedes zwanzigste Intervall den wahren Wert. Der blaue Trichter in der unteren Grafik zeigt den Bereich um den wahren Wert für jedes NN einzeln. Die ganze Kurve muss nicht darin bleiben. Bei einem einzelnen Durchlauf kann die Schätzung durch zusätzliche Punkte sogar etwas weiter vom wahren Wert abrücken. Zuverlässig enger wird die Fehlerspanne.

Wann lohnt es sich?

Bei einer glatten Funktion einer Variablen ist eine deterministische Regel wie die Simpsonregel (siehe numerische Integration) bei gleich vielen Funktionsauswertungen deutlich genauer. Der Vorteil von Monte Carlo liegt darin, dass der Exponent der Rate 1/N1/\sqrt{N} nicht von der Dimension abhängt. Ein Gitter mit mm Punkten pro Seite benötigt dagegen in dd Dimensionen mdm^d Punkte. In hohen Dimensionen kann Monte Carlo daher die bessere Wahl sein. Kleine Zielgebiete sind seine Schwachstelle: Der Standardfehler relativ zur Fläche beträgt (1−a)/(aN)\sqrt{(1-a)/(aN)}. Ein Gebiet von einem Hundertstel der Quadratfläche erfordert daher für dieselbe relative Genauigkeit viel mehr Punkte.

Darauf kannst du achten

  • Zufallspunkte liegen nicht in gleichmäßigen Abständen. Bei einigen Hundert Punkten sind Ansammlungen und Lücken normal.
  • Die Punkte stammen aus einem Pseudozufallsgenerator mit numerischem Startwert. Ein geteilter Link stellt dieselben Punkte wieder her. Bei einer Million beginnt „Punkte werfen“ mit dem nächsten Startwert von vorn.

Verwandte Themen