Monte-Carlo-Verfahren


Mathematische Näherungsverfahren

Bei gewöhnlichen (deterministischen) Näherungsverfahren ist die Angabe eines Fehlers für eine Näherung von entscheidender Bedeutung. Der Fehler ε ist die Abweichung des exakten Wertes A von der Näherung Näh_A. Das kann mathematisch in folgender Weise geschrieben werden

|A - Näh_A| = ε.

Ein Beispiel für ein deterministisches Näherungsverfahren ist die Näherung eines bestimmten Integrals durch einen Wert zwischen einer Rechteckobersumme und einer Rechteckuntersumme. Der Fehler der Näherung ist dann sicher nicht gößer als die Differenz der beiden Summen.

Bei guten Näherungsverfahren kann ein (kleiner) Fehler vorgegeben werden und das Näherungsverfahren kann so fortgeführt werden, dass dieser vorgebene Fehler unterschritten wird. Hierfür kann der Rechenaufwand allerdings stark ansteigen. Im Idealfall kann sogar erreicht werden, dass die Näherung schließlich den exakten Wert liefert. Beim bestimmten Integral ist dieser exakte Wert erreicht, wenn Ober- und Unterumme denselben Grenzwert haben.

Monte-Carlo-Verfahren sind stochastische Näherungsverfahren. Auch für diese Näherungsverfahren gilt die obige Gleichung für den Fehler.
Bei deterministischen Verfahren bedeutet die Angabe eines (maximalen) Fehlers, dass die Näherung mit Sicherheit keine größere Abweichung vom exakten Wert hat. Bei Monte-Carlo-Verfahren ist das nicht mehr so. Hier gilt nur, dass der Fehler mit einer großen Wahrscheinlichkeit, der Sicherheitswahrscheinlichkeit, nicht überschritten wird. Durch Fortführung des stochastischen Näherungsverfahrens kann erreicht werden, dass der Fehler kleiner und/oder die Sicherheitswahrscheinlichkeit größer wird. Allerdings kann man prinzipiell nicht erreichen, dass das Näherungsverfahren mit Sicherheit (Sicherheitswahrscheinlichkeit 1) den exakten Wert ergibt.

Die Grundidee eines Monte-Carlo-Verfahrens beruht auf der stochastischen Konvergenz der relativen Häufigkeit X/n einer Bernoulliverteilung gegen den Parameter p. Die relative Häufigkeit nähert mit wachsendem n den Parameter p immer besser an. Die Streuungsungleichung liefert Möglichkeiten zur Bewertung dieser Näherung.

Die Kunst der Anwendung eines Monte-Carlo-Verfahrens besteht darin, das gegebene Problem so zu interpretieren, dass daraus die Aufgabe wird, den Parameter p einer Bernoulliverteilung durch einen experimentell gefundenen Wert x/n zu schätzen.

Beispiel

Näherunsweise Bestimmung einer Fläche B


(Auch) Derive kann den Flächeninhalt von B nicht exakt bestimmen.


Vor der Anwendung eines Monte-Carlo-Verfahrens steht die Interpretation des gegebenen Problems als Schätzproblem für den Parameter p einer Bernoulliverteilung. Dafür benutzt man hier sogenannte geometrische Wahrscheinlichkeiten.

Wird ein Punkte zufällig (d.h. gleichverteilt) in eine Fläche A geworfen, die eine Unterfläche B enthält, so gilt für die Wahrscheinlichkeit p, dass der Punkt in B fällt    |B|/|A| = p    . Werden n Punkte geworfen, so fallen x Punkte davon in dieTeilfläche B. Es liegt ein Bernoulli-Experiment vor und x/n schätzt p. Es gilt also für große n    |B| ≈ |A|*x/n    . Wird mit der Streuungsungleichung der Fehler |x/n - p| abgeschätzt, so kann damit auch der Fehler für |B| abgeschätzt werden.

Nach der Streuungsungleichung gilt   P(|x/n - p| ≤ ε) ≥ 1 - 1/(4nε)   . ε ist also eine obere Schranke für den Fehler |x/n - p| und 1 - 1/(4nεε) ist eine untere Schranke für die Sicherheitswahrscheinlichkeit, dass der Fehler ε nicht überschritten wird.

Derive-Programm zur näherunsweisen Bestimmung des Inhalts von B

Zur 'mathematischen' Durchführung des Experiments, n Punkte zufällig in A zu werfen, wird ein Derive-Programm geschrieben. Da bei dem gegebenen Problem die Fläche A das Einheitsquadrat ist, ist |B| ≈ x/n - ein besonders einfacher Fall. Bei jedem Wurf muss entscheidbar sein, ob der Punkt in B liegt. Falls das der Fall ist, wird x um 1 erhöht. Es ergibt sich das folgende Programm:

Es gilt also |B| ≈ 0,9466.

Fehlerbetrachtung für n=10000:

Es kann entweder ε oder die Sicherheitswahrscheinlichkeit vorgegeben werden. Sei ε = 0,1 gewählt. Dann ergibt sich für die untere Schranke der Sicherheitswahrscheinlichkeit    1 - 1/(4*10000*0,1*0,1) = 0,9975.
Die Genauigkeit der Schätzung von |B| mit einem maximalen Fehler von 0,1 wird also mit einer Sicherheitswahrscheinlichkeit von von mindestens 0,9975 eingehalten.

Würde man eine größere Genauigkeit fordern, etwa   ε = 0,01  , so ergibt sich eine Sicherheitswahrscheinlichkeit von   1 - 1/(4*10000*0,01*0,01) = 0,75  . Die Sicherheit dafür, dass dieser Fehler eingehalten wird, ist also wesentlich kleiner.

Für die Angabe der Güte einer Schätzung mit Monte-Carlo müssen also immer beide Angaben vorliegen: ein Fehlerwert ε und die dazu gehörende Sicherheitswahrscheinlichkeit.

Falls sowohl ε wie die Sicherheitswahrscheinlichkeit vorgegeben werden, kann man das (mindestens) erforderliche n errechnen.
Beispiel: ε = 0,01 und Sicherheitswahrscheinlichkeit ≥ 0,9 ergibt mit    0,9 = 1 - 1/(4*n*0,01*0,01)   n = 25000. Es sind also mindestens 25000 Punkte zu werfen.