Markov Chain Monte Carlo - Methoden: Herleitung, Beweis und Implementierung

Markov Chain Monte Carlo - Methoden: Herleitung, Beweis und Implementierung

Buch (Taschenbuch)

24,99 €

inkl. gesetzl. MwSt.

Markov Chain Monte Carlo - Methoden: Herleitung, Beweis und Implementierung

Ebenfalls verfügbar als:

Taschenbuch

Taschenbuch

ab 24,99 €
eBook

eBook

ab 16,99 €

Beschreibung

In seiner Arbeit beschäftigt sich der Autor mit der 'Markov Chain Monte Carlo', auch abgekürzt als MCMC. Dabei handelt es sich um eine Monte Carlo Methode. Allen Monte Carlo Methoden ist gemein, dass sie von einer mehr oder minder komplizierten Verteilung zufällige Szenarien erzeugen. Diese Szenarien werden dann genutzt um Aussagen über Erwartungswerte oder andere Kennzahlen der Verteilung zu treffen. Diese Aussagen sind natürlich nur zu gebrauchen, wenn man sehr viele zufällig erzeugte Szenarien auswertet. Die Methode kommt also immer dann zum Einsatz, wenn es nicht möglich ist, aus der Verteilung der Szenarien direkt Rückschlüsse auf die statistischen Kennzahlen der Verteilung zu ziehen, weder auf analytischem Wege, noch durch numerische Integration (bei sehr vielen Dimensionen steigt der Aufwand rapide an).
Markov Chain Monte Carlo ist nun eine spezielle Monte Carlo Methode unter Zuhilfenahme von Markovketten. Diese kommt immer dann zum Einsatz, wenn es nicht möglich ist, von einer Verteilung auf einfache Weise Szenarien zu erzeugen. Eine Markovkette fängt bei einem Zustand an und geht von einem bestimmten Zustand mit einer bestimmten Wahrscheinlichkeit zu einem anderen Zustand über. Diese Übergangswahrscheinlichkeiten stehen in einer Übergangsmatrix. Der Knackpunkt ist nun, dass diese Form der Zustandsgenerierung oft einfacher zu implementieren ist, als direkt auf eine Verteilung zurückzugreifen. In der Arbeit gibt es mehrere konkrete Beispiele für den Einsatz solcher Methoden. Quelltexte der Implementierungen sind beigefügt.

Thomas Plehn ist studierter Lehrer für Mathematik und Physik mit erstem Staatsexamen 2007 an der Universität Bielefeld. Nach einem zusätzlichen Masterstudium der Optimierung und Simulation an der FH Bielefeld ist er nun in der Softwareindustrie tätig.

Details

Einband

Taschenbuch

Erscheinungsdatum

22.05.2014

Verlag

Bachelor + Master Publishing

Seitenzahl

56

Beschreibung

Details

Einband

Taschenbuch

Erscheinungsdatum

22.05.2014

Verlag

Bachelor + Master Publishing

Seitenzahl

56

Maße (L/B/H)

22/15,5/0,3 cm

Gewicht

108 g

Sprache

Deutsch

ISBN

978-3-95684-451-5

Das meinen unsere Kund*innen

0.0

0 Bewertungen

Informationen zu Bewertungen

Zur Abgabe einer Bewertung ist eine Anmeldung im Kund*innenkonto notwendig. Die Authentizität der Bewertungen wird von uns nicht überprüft. Wir behalten uns vor, Bewertungstexte, die unseren Richtlinien widersprechen, entsprechend zu kürzen oder zu löschen.

Verfassen Sie die erste Bewertung zu diesem Artikel

Helfen Sie anderen Kund*innen durch Ihre Meinung

Erste Bewertung verfassen

Unsere Kund*innen meinen

0.0

0 Bewertungen filtern

Weitere Artikel finden Sie in

Textprobe:
Kapitel 4.1: Problemstellung in diesem Abschnitt interessieren wir uns für Algorithmen, um Zählprobleme zu lösen. Um einige generelle Techniken zu zeigen, sollten wir uns noch mal dem Beispiel mit den möglichen q-Färbungen eines Graphen aus dem letzten Abschnitt zu wenden. Insbesondere werden wir sehen, wie sich die MCMC-Technik als nützlich in diesem Kontext erweist. Wenn man naiv an das Problem herangehen würde, könnte man glauben, das Problemlösen zu können, indem man einfach alle möglichen Konfigurationen, also Elemente von {1,...,q} V, in lexikographischer Reihenfolge durch geht und dann alle davon zählt, bei denen es sich um zulässige Konfigurationen handelt. Leider handelt es sich hierbei um einen sehr zeitaufwendigen Algorithmus, denn die Elemente von {1,...,q} V wachsen exponentiell mit der Mächtigkeit von V an. Insbesondere sind wir deshalb hier interessiert, Algorithmen zu finden, die eine polynomiale Laufzeit besitzen. Das bedeutet, dass ein Polynom p (k) in der Größe k des Problems existiert, sodass die Laufzeit begrenzt ist durch p (k), für jede Instanz des Problems der Größe k. Das ist dasselbe, wie nach Algorithmen zu fragen, deren Laufzeit durch Ck begrenzt ist, für irgendwelche Konstanten C und . In vielen Fällen können wir aber noch nicht einmal das erreichen und müssen uns mit Algorithmen zufriedengeben, die die Mächtigkeit der Menge aproximieren, d.h. deren Ausgabe sich irgendwo zwischen (1 )N und (1+ ) N befindet, wenn N die wahre Mächtigkeit der Menge ist. Die Fehlertoleranz erhält der Algorithmus als Eingabe, sodass der Fehler beliebig klein werden kann, wenn man dadurch eine größere Laufzeit in kauf nimmt, die aber immer durch ein Polynom p (k) in der Größe des Problems begrenzt ist. Leider können wir in vielen Fällen aber noch nicht einmal sicherstellen, dass sich das Ergebnis des Algorithmus immer innerhalb der vorgegbenen Fehlerschranken bewegt, sondern dies nur mit einer Wahrscheinlichkeit von 23 der Fall ist. Das bedeutet, dass wenn wir dem Algorithmus als Eingabe geben, dieser folgende Eigenschaften besitzt: 1. Mit einer Wahrscheinlichkeit von mindestens 23, gibt der Algorithmus eine Antwort im Bereich (1 ) N und (1+ ) N aus, wobei N die wahre Antwort des Zählproblems darstellt. 2. Für jedes 0 existiert ein Polynom p (k) in der Größe k des Problems, sodass für jedes Auftreten des Problems der Größe k der Algorithmus in höchstens p (k) Schritten terminiert. Ein solcher Algorithmus heißt zufälliges Polynom-Zeit Approximations-Schema. Dieser Abschnittbeschäftigt sich mit der Konstruktion eines solchen Schemas für die q-Färbungen von Graphen.
  • Markov Chain Monte Carlo - Methoden: Herleitung, Beweis und Implementierung