Dies ist eine maschinelle Übersetzung; das englische Original ist maßgebend. Original lesen
Zufall erkauft Genauigkeit zu einem schlechten Wechselkurs
Zehnmal so viele Stichproben bringen etwa dreimal so viel Genauigkeit. Nicht zehnmal. Dieser Wechselkurs steht fest, und kein noch so kluger Kniff verhandelt ihn neu.
Das Werfen von Pfeilen auf ein Quadrat zur Bestimmung von π ist die klassische erste Demonstration von Monte-Carlo-Methoden. Man zählt den Anteil, der innerhalb des Viertelkreises landet, multipliziert mit vier und erhält einen Schätzwert.
Was die Demonstration gewöhnlich auslässt, ist, wie schlecht sie funktioniert.
Drei Voreinstellungen und was sie kosten
Monte Carlo π bietet drei Stichprobengrößen: 200, 2000 und 20000. Sie laufen mit einem festen Seed; es handelt sich also nicht um Einzelfälle, sondern jedes Mal, wenn die Seite geöffnet wird, um dieselben drei Zahlen.
- 200 Punkte ergeben 3,040000, abweichend um 1,02 × 10⁻¹
- 2000 Punkte ergeben 3,122000, abweichend um 1,96 × 10⁻²
- 20000 Punkte ergeben 3,127800, abweichend um 1,38 × 10⁻²
Der hundertfache Aufwand zwischen der ersten und der letzten Zeile, und die Antwort ist in der zweiten Nachkommastelle immer noch falsch. Sie hat sich die „3,14“, die jedes Schulkind aufsagen kann, noch nicht verdient.
Die Rate ist eins durch die Quadratwurzel
Jeder Pfeilwurf ist ein unabhängiges Ja-oder-Nein-Experiment, und der Standardfehler eines aus n Versuchen gemessenen Anteils sinkt mit 1/√n. Für diesen speziellen Schätzer ergibt sich der typische Fehler zu 0,116 bei 200 Stichproben, 0,0367 bei 2000 und 0,0116 bei 20000.
Zehnmal so viele Stichproben bringen also etwa die 3,16-fache Genauigkeit, da 3,16 die Quadratwurzel aus zehn ist. Um eine weitere Dezimalstelle – einen Genauigkeitsfaktor von zehn – zu gewinnen, benötigt man das Hundertfache an Stichproben. Um den Fehler bei 2000 Stichproben von etwa 0,037 auf 0,0037 zu senken, braucht man 200.000 Pfeile.
Das sollte man sich merken, denn es ist keine Eigenschaft von π, von Pfeilen oder von dieser Implementierung. Es ist der Zentrale Grenzwertsatz bei der Arbeit: Der Fehler des Mittelwerts unabhängiger Größen schrumpft mit der Quadratwurzel der Anzahl der gemittelten Werte, ganz gleich, worum es sich handelt. Dieselbe Arithmetik bestimmt Meinungsumfragen, Ereigniszahlen in der Teilchenphysik und jede Simulation, die durchgeführt wird.
Was ein einzelner Seed nicht verraten kann
Betrachten wir nun noch einmal diese drei Fehler der Voreinstellungen, denn sie verhalten sich nicht so, wie die Regel es gerade versprochen hat. Von 200 auf 2000 verringerte sich der Fehler um das 5,19-Fache. Von 2000 auf 20000 schrumpfte er nur um das 1,42-Fache. Beide Werte entsprechen nicht 3,16.
Es liegt kein Fehler vor. Das Quadratwurzel-Gesetz beschreibt den typischen Fehler, die Breite der Verteilung, aus der der Schätzwert stammt, und ein einzelner Durchlauf ist eine Stichprobe aus dieser Verteilung. Der Durchlauf mit 2000 Punkten lag zufällig näher am Ziel als sein typischer Fehler, etwa bei einer halben Standardabweichung. Der Durchlauf mit 20000 Punkten lag zufällig weiter außerhalb. Ihr Verhältnis sagt nahezu nichts aus.
Dies ist das häufigste Missverständnis bei einer Simulation. Ein Durchlauf mit gutem Ergebnis ist kein Beweis für eine gute Methode, und ein Durchlauf mit schlechtem Ergebnis ist kein Beweis für eine schlechte. Man kann die Rate nicht an einem einzigen Seed ablesen; man sieht sie erst durch Wiederholung und den Blick auf die Streuung – genau das beschreibt Normal Distribution, wenn diese Streuung als Kurve dargestellt wird.
Warum man sich darauf einlässt
Eine Methode, die das Hundertfache an Aufwand pro Stelle erfordert, klingt unvertretbar – und für eindimensionale Probleme ist sie das auch. Gewöhnliche numerische Integration auf einem Gitter schlägt sie mühelos.
Der Grund, warum Monte Carlo das praktische Rechnen dominiert, liegt darin, dass 1/√n die Dimension nicht erwähnt. Legt man über ein Problem in 20 Dimensionen ein Gitter mit 10 Punkten pro Achse, benötigt man 10²⁰ Auswertungen. Das Zufallsverfahren benötigt weiterhin nur das, was 1/√n für die gewünschte Genauigkeit erfordert, ganz unabhängig davon, dass 20 Achsen vorhanden sind.
Der Wechselkurs ist also schlecht, und er ist zudem konstant. In niedrigen Dimensionen sollte man ihn ablehnen. In hohen Dimensionen ist er jedoch häufig das einzige Angebot auf dem Tisch, weshalb Physik, Finanzwesen und Bildsynthese ihn gleichermaßen zahlen.
Poisson ist dieselbe Arithmetik, betrachtet von der Seite des Zählens: Wenn man seltene Ereignisse zählt, entspricht die Varianz dem Mittelwert, sodass der relative Fehler erneut mit eins durch die Quadratwurzel der Anzahl sinkt. Eine Verdopplung des Vertrauens in eine Rate bedeutet immer eine Vervierfachung der Beobachtungen.