Monte Carlo Methoden zur Berechnung der Zahl Pi – Teil 2: Quasi-Monte Carlo Methoden

26. Apr 2018 | Blog

VON Florian Nachbagauer

In meinem letzten Blogbeitrag im Jänner mit dem Titel „Monte Carlo Methoden zur Berechnung von Pi“ wollte ich die Monte Carlo Methode an einem einfachen Beispiel veranschaulichen. Nun möchte ich am selben Beispiel die Quasi-Monte Carlo Methode erläutern, was in vielen Fällen eine Verbesserung gegenüber herkömmlichen Monte Carlo Methoden darstellt.

 

Zur Erinnerung: Wir haben gleichverteilte Zufallszahlen in einem Quadrat mit Seitenlänge 1 generiert und danach die Zahl Pi mit dem vierfachen Quotienten aus der Anzahl der Punkte im Viertelkreis und der Gesamtanzahl der Punkte im Quadrat angenähert. Mit 1000 gleichverteilten Zufallszahlen sieht das beispielsweise so aus:

 

Quelle: Eigen Berechnungen

 

Dem genauen Beobachter fällt jetzt möglicherweise auf, dass die Punkte gar nicht „so“ gleichmäßig verteilt sind: Es gibt einige Stellen, wo viele Punkte nahe beieinander liegen, und einige Stellen, die nur sehr dünn besiedelt sind. Im Vergleich dazu betrachte man eine sogenannte Sobol-Folge:

 

Quelle: Eigene Berechnungen

 

Es sticht sofort ins Auge, dass die Punkte in diesem Bild viel gleichmäßiger angeordnet sind. Der große Unterschied zum ersten Bild ist, dass die Punkte keine Zufallszahlen mehr sind, denn es gibt eine deterministische Rechenvorschrift, wie jeder einzelne Punkt der Sobol Folge ermittelt wird. Verwendet man nun für unsere Pi-Annäherung die Sobol-Folge, sollten die Ergebnisse erwartungsgemäß genauer sein. Da hier keine Zufallszahlen mehr im Spiel sind, ist diese Prozedur, streng genommen, keine Monte Carlo Methode, daher nennt man derartige Verfahren „Quasi-Monte Carlo Methoden“. Wie man im nächsten Bild sehen kann, ist die Schätzung mittels Quasi-Monte Carlo (orange) um einiges näher beim tatsächlichen Wert von Pi (grün), als die Schätzung mittels herkömmlichen Monte Carlo (blau).

 

Quelle: Eigen Berechnungen

 

Im nächsten Bild ist eindeutig erkennbar, dass die Fehler bei Quasi-Monte Carlo durchwegs geringer sind, bei einer Anzahl von 10 Millionen Punkten ist die Quasi-Monte Carlo Methode sogar um 2 Nachkommastellen genauer.

 

Quelle: Eigene Berechnungen

 

Allerdings sollte man folgendes anmerken: In der Praxis kennt man den wahren Wert nicht, das heißt, man kennt auch den Fehler nicht. Bei Monte Carlo Methoden kann man den Fehler mit einem Konfidenzintervall eingrenzen (siehe die roten Linien im dritten Bild), was bei reinem Quasi Monte Carlo nicht so einfach möglich ist, da hier nichts mehr zufällig ist. Deshalb ist man dazu übergegangen, Folgen, wie die Sobol-Folge, wieder „ein bisschen“ zufällig zu machen, aber „nicht ganz so“ zufällig wie normale Zufallszahlen. Oder einfacher ausgedrückt: Man will den Zufall ins Spiel bringen und gleichzeitig die Gleichmäßigkeit bewahren. Eine derartige Methode wird „Randomized Quasi-Monte Carlo“ genannt und mithilfe dieser Methode lässt sich auch der Fehler wieder einfach mit einem Konfidenzintervall eingrenzen.

 

Wenn man bei gewissen Problemstellungen bereits Monte Carlo Methoden im Einsatz hat, kann es oft lohnend sein, dass man versucht, dieselben Probleme mittels Quasi-Monte Carlo oder Randomized Quasi-Monte Carlo zu lösen, da der Umstieg im Idealfall wenig Aufwand bedeutet und die Qualität der Ergebnisse möglicherweise stark verbessert werden kann.

 

Die Bilder und Berechnungen in diesem Beitrag (und auch in meinem letzten Beitrag) wurden in der Programmiersprache R durchgeführt. Für Interessierte kann auf Anfrage gerne der Programmcode zur Verfügung gestellt werden.

Hier können Sie den Verfasser gerne kontaktieren: florian.nachbagauer@grawe.at