Monte-Carlo-Methoden sind ein Sammelbegriff für auf Zufallswürfen basierende Methoden zur Abschätzung von Werten oder zur Integrierung von schwierigen Funktionen. Der Begriff “Monte Carlo” kommt von dem Ort in Monacco und seinen Casinos – da Roulette ein einfacher Generator für Zufallszahlen ist.
Generell kamen sie unter diesem Begriff aus Los Alamos, wo sie gegen Ende des Krieges und danach entwickelt wurden, von bedeutenden Forschern wie Fermi, Ulam (dessen Onkel wohl gerne in Monte Carlo spielte…). Richtig populär wurden sie erst mit dem Aufkommen von Computern und Pseudo-Zufallszahlengeneratoren.
Die wichtigste Klasse wurden die Markov Chain Monte Carlo-Methoden zur zufallsbasierten numerischen Integration, vor allem der Metropolis-Hastings-Algorithmus sei hier genannt. Aber schon vorher wurden manchmal zufallsbasierte Methoden eingesetzt, z.B. von Fermi 1930 zur Berechnung von Eigenschaften des Neutrons. Die erste überlieferte Monte-Carlo-Methode stammt von Buffon aus dem Jahr 1777. Er ließ Nadeln auf ein Schar paralleler Linien fallen. Man kann ausrechnen, wie wahrscheinlich es ist dass die Nadel eine Gerade berührt, und in dieser Wahrscheinlichkeit steckt Pi. Wenn man nun oft die Nadel wirft, wird sie zufällig irgendwo landen, und aus dem Verhältnis wie oft sie dabei eine Gerade trifft kann man Pi abschätzen.
Hier gibt es ein nettes Java-Applet dazu. Lasst die Nadellänge bei 1 und lasst ihn werfen. Die relative Anzahl der treffenden Nadeln nähert sich 2/pi. Bei 60,5% Nadeln die eine Gerade berühren wäre die Schätzung für Pi 3.306.
Aber durch den Wikipedia-Artikel zu Monte-Carlo habe ich noch ein bessere Idee gefunden: Eine Monte-Carlo-Methode zu abschätzen von Pi zum selber durchführen, die viel einfacher ist als tausendmal eine Nadel werfen zu müssen.
Man muss nur in ein Quadrat einen Kreis genau einschreiben, ich habe es so gemacht dass ich mit einer CD auf kariertes Papier den Umriss gemalt habe und dann dank den Karos drumherum mit einem Lineal das Quadrat ergänzen konnte:
Der Verhältnis der Fläche Kreis zu Quadrat beträgt Pi/4. Man muss also die Flächen bestimmen. Das geht so: Man nimmt eine Handvoll Reiskörner und lässt sie auf das Blatt rieseln. Man sollte versuchen, sie gleichmäßig fallen zu lassen aus einiger Höhe damit sie sich einigermaßen zufällig verteilen und nicht nur in die Mitte – das ist unser Zufallsgenerator. Dann zählen wir, wieviele Reiskörner in den Flächen liegen.
Ich habe den Versuch zweimal durchgeführt. Beim ersten Mal lagen 44 im Quadrat aber nicht im Kreis und 145 nur im Kreis. Macht also (44+145)/145*4 = 3.07.
Der zweite Versuch brachte (26+88)/88*4 = 3.09.
Keine schlechten Werte. Beide nahe zusammen und etwas zu niedrig. Vermutlich ein systematischer Fehler, weil etwas zu wenig Reiskörner (müssen ja nur jeweils 1-2 sein) in den Ecken landen. Das kann dran liegen dass die a) etwas klein sind und b) dass ich beim Fallen lassen der Körner doch leicht bevorzugt über die Mitte des Kreises gehalten habe und daher einige mehr Körner dorthin gefallen sind.
Was bekommt ihr raus?
Kommentare (6)