Monte Carlo-Algorithmen | springerprofessional.de

Springer Professional

nach oben

2012 | Buch

Kapitel lesen Erstes Kapitel lesen

Monte Carlo-Algorithmen

verfasst von: Thomas Müller-Gronbach, Erich Novak, Klaus Ritter

Verlag: Springer Berlin Heidelberg

Buchreihe : Springer-Lehrbuch

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

Der Text gibt eine Einführung in die Mathematik und die Anwendungsmöglichkeiten der Monte Carlo-Methoden und verwendet dazu durchgängig die Sprache der Stochastik. Der Leser lernt die Grundprinzipien und wesentlichen Eigenschaften dieser Verfahren kennen und wird dadurch in den Stand versetzt, dieses wichtige algorithmische Werkzeug kompetent einsetzen und die Ergebnisse interpretieren zu können. Anhand ausgewählter Fragestellungen wird er außerdem an aktuelle Forschungsfragen und -ergebnisse in diesem Bereich herangeführt. Behandelt werden die direkte Simulation, Methoden zur Simulation von Verteilungen und stochastischen Prozessen, Varianzreduktion, sowie Markov Chain Monte Carlo-Methoden und die hochdimensionale Integration. Es werden Anwendungsbeispiele aus der Teilchenphysik und der Finanz- und Versicherungsmathematik präsentiert, und anhand des Integrationsproblems wird gezeigt, wie sich die Frage nach optimalen Algorithmen formulieren und beantworten lässt.

Anzeige

Inhaltsverzeichnis

Frontmatter

1. Vorbereitungen

Zusammenfassung

Monte Carlo-Methoden sind Algorithmen, die Zufallszahlen benutzen. Neben den üblichen Befehlen (die Grundrechenarten,Vergleich von Zahlen, ein Orakel zur Berechnung von Funktionswerten) ist also zusätzlich der Aufruf eines Zufallszahlengenerators zugelassen, d. h. Befehle der Art • ” Wähle x ∈ [0,1] zufällig“ oder • ” Wähle x ∈ {0, . . . ,N −1} zufällig“ sind erlaubt. In der Literatur werden Monte Carlo-Methoden auch als stochastische oder randomisierte Algorithmen bezeichnet, und das Gebiet der Monte Carlo- Methoden heißt auch Stochastische Simulation oder Experimentelle Stochastik.Wir verwenden die Begriffe Algorithmus,Methode und Verfahren synonym.

Thomas Müller-Gronbach, Erich Novak, Klaus Ritter

2. Algorithmen, Fehler und Kosten

Zusammenfassung

In diesem Kapitel werden wir den Gegenstand unserer Betrachtungen, die Monte Carlo-Algorithmen, genauer beschreiben. Ein Grundverständnis von Algorithmen als Rechenvorschriften ist für viele Zwecke der Angewandten Mathematik unerläßlich, während eine exakte Definition des Begriffs Algorithmus oft gar nicht notwendig zu sein scheint. Spätestens, wenn man die Frage nach der Optimalität von Algorithmen für eine gegebene Problemstellung formulieren und beantworten möchte, ist eine mathematische Präzisierung des Begriffs Algorithmus jedoch unerl äßlich, da Optimalität eine Aussage über die Gesamtheit aller Algorithmen beinhaltet. Dieselbe Notwendigkeit liegt auch dann vor, wenn man klären möchte, ob Monte Carlo-Algorithmen für eine gegebene Problemstellung besser als deterministische Algorithmen sind.

Thomas Müller-Gronbach, Erich Novak, Klaus Ritter

3. Das Verfahren der direkten Simulation

Zusammenfassung

In den Abschnitten 3.1 und 3.2 untersuchen wir den Fehler, die Kosten und erste Konvergenzeigenschaften der direkten Simulation und zeigen ihre vielfältige Einsetzbarkeit. Das starke Gesetz der großen Zahlen und der zentrale Grenzwertsatz sind unmittelbar auf die direkte Simulation anwendbar und führen, wie wir in Abschnitt 3.3 zeigen, zu einem vertieften Verständnis des asymptotischen Verhaltens dieser Methode. In Abschnitt 3.4 lernen wir die Hoeffding-Ungleichung kennen, die zur Abschätzung von Fehlerwahrscheinlichkeiten eingesetzt wird. Abschnitt 3.5 behandelt Methoden der Mathematischen Statistik, mit deren Hilfe sich auf einfache Weise aus den Ergebnissen einer direkten Simulation auch Aussagen über die Güte der Approximation gewinnen lassen. Dieser Vorteil, den die direkte Simulation gegenüber deterministischen Algorithmen besitzt, sollte bei jedem Einsatz genutzt werden. Die Ergebnisse aus Abschnitt 3.6 über Stoppzeiten und Unabhängigkeit werden immer dann benötigt, wenn die Anzahl der Zufallszahlen, die in eine Simulation eingehen, erst im Laufe derselben bestimmt werden. Als Beispiel hierfür nennen wir Ruinprobleme und erinnern an Aufgabe 1.8.

Thomas Müller-Gronbach, Erich Novak, Klaus Ritter

4. Simulation von Verteilungen

Zusammenfassung

Bei der Analyse von Monte Carlo-Verfahren gehen wir meist davon aus, daß wir mit Hilfe eines Zufallszahlengenerators Realisierungen einer unabhängigen Folge von auf [0,1] gleichverteilten Zufallsvariablen erzeugen können, siehe Abschnitt 1.3. In vielen Anwendungen möchte man jedoch weitere Verteilungen zur Verfügung haben, und man studiert deshalb Abbildungen, die diese Folge von Zufallsvariablen in eine unabhängige Folge von identisch verteilten Zufallsvariablen oder -vektoren mit einer gewünschten anderen Verteilung transformieren.

Thomas Müller-Gronbach, Erich Novak, Klaus Ritter

5. Varianzreduktion

Zusammenfassung

Wie Korollar 3.3 zeigt, wird die Güte einer direkten Simulation durch das Produkt aus Kosten und Varianz des Basisexperiments bestimmt. Es gibt nun zahlreiche Techniken der Varianzreduktion, mit denen man das Basisexperiment so zu ändern versucht, daß dieses Produkt verkleinert wird. Wir diskutieren hier vier solche Techniken, nämlich antithetic sampling, control variates, stratified sampling und importance sampling, in allgemeiner Form und illustrieren ihren Einsatz insbesondere bei der numerischen Integration.Wir zeigen ferner, wie sich bei der numerischen Integration durch geeignete VarianzreduktionMonte Carlo-Methoden konstruieren lassen, deren Konvergenzordnung größer als 1/2 ist. Ausführliche Darstellungen von Methoden zur Varianzreduktion findet man bei Asmussen, Glynn [5], Fishman [55, Chap. 4] und, mit Anwendungen auf finanzmathematische Probleme, bei Glasserman [70, Chap. 4]. Die englischsprachigen Bezeichnungen der Varianzreduktionsmethoden finden auch in der deutschsprachigen Literatur Verwendung, und wir benutzen sie hier aus Gründen der Einheitlichkeit.

Thomas Müller-Gronbach, Erich Novak, Klaus Ritter

6. Die Markov Chain Monte Carlo-Methode

Zusammenfassung

Der Einsatz der direkten Simulation setzt voraus, daß ein Algorithmus zur Simulation der Verteilung des Basisexperiments zur Verfügung steht. Tatsächlich ist die Simulation einer Wahrscheinlichkeitsverteilung ein eigenständiges Problem, für das wir in Kapitel 4 einige grundlegende Techniken kennengelernt haben.Oft besitzt das Basisexperiment in natürlicherWeise die Struktur Y = f (X), und simuliert wird die Verteilung P(X) von X.

Thomas Müller-Gronbach, Erich Novak, Klaus Ritter

7. Numerische Integration

Zusammenfassung

Im Vergleich mit Konvergenzordnungen, die sich in der Dimension d = 1 zum Beispiel mit der Trapezregel oder mit Gauß-Formeln erreichen lassen, ist die Ordnung 1/2 in der Tat wenig beeindruckend. Bei dieser Sichtweise werden jedoch die Voraussetzungen an den Integranden außer acht gelassen. So erreicht die Trapezregel die Konvergenzordnung eins für Lipschitz-stetige Integranden und zwei für zweimal stetig differenzierbare Integranden, während bei der klassischen Monte Carlo-Methode zur Integration die quadratische Integrierbarkeit des Integranden ausreicht, um die Ordnung 1/2 zu erhalten.

Thomas Müller-Gronbach, Erich Novak, Klaus Ritter

Backmatter

Titel: Monte Carlo-Algorithmen
verfasst von: Thomas Müller-Gronbach
Erich Novak
Klaus Ritter
Copyright-Jahr: 2012
Verlag: Springer Berlin Heidelberg
Electronic ISBN: 978-3-540-89141-3
Print ISBN: 978-3-540-89140-6
DOI: https://doi.org/10.1007/978-3-540-89141-3