Markov Chain Monte Carlo Methoden

ISBN-13: 9783640355129 / Niemiecki / Miękka / 2009 / 60 str.

Thomas Plehn

Opis

Masterarbeit aus dem Jahr 2007 im Fachbereich Mathematik - Stochastik, Note: 1.0, Universitat Bielefeld, Sprache: Deutsch, Abstract: Wir beginnen mit einem sehr einfachen Beispiel: Denken wir an einen zufalligen Laufer in einer sehr kleinen Stadt, die nur aus vier Straen besteht. Dabei werden die vier Straenecken wie in der untenstehenden Abbildung mit v1, v2, v3 und v4 bezeichnet. Zum Zeitpunkt 0 steht der zufallige Laufer in der Ecke v1. Zum Zeitpunkt 1 wirft er eine faire Munze und entscheidet je nach Ausfall, ob er weiter nach v2 oder v4 geht. Zum Zeitpunkt 2 wirft er wieder eine faire Munze, um zu entscheiden, zu welcher benachbarten Ecke er gehen soll. Dabei verwendet er die Entscheidungsregel, wenn die Munze Kopf zeigt, einen Schritt im Uhrzeigersinn zu gehen und andernfalls, wenn die Munze Zahl zeigt, einen Schritt gegen den Uhrzeigersinn zu gehen. Diese Prozedur wird fortgefuhrt fur die Zeiten 3, 4, usw.

Spis treści

1 Grundlagen zu Markov-Ketten 1.1 Definition 1.2 Irreduzibilität und Aperiodizität 1.3 Stationäre Verteilungen und Reversibilität 1.3.1 Existenz der stationären Verteilung 1.3.2 Reversibilität einer Verteilung 1.4 Konvergenzsatz 1.4.1 Konvergenz gegen die stationäre Verteilung 1.4.2 Eindeutigkeit der stationären Verteilung 2 Metropolis-Hastings Algorithmu 2.1 Allgemeine Beschreibung des Metropolis-Hastings Algorithmus 2.2 Implementierung des Metropolis-Algorithmus im Beispiel der Exponentialverteilung 2.3 Fehler-Abschätzung im Beispiel der Exponetialverteilung 3 Gibbs-Sampler 3.1 Allgemeine Beschreibung des Gibbs-Samplers 3.2 Implementierung des Gibbs-Sampler Beispiels 3.3 Verallgemeinerung auf q-Färbungen 4 Approximate counting 4.1 Problemstellung 4.2 Existenz-Theorem 4.3 Beweis: erster Teil 4.4 Beweis: zweiter Teil 4.5 Implementierung 5 Literatur 6 Quelltexte 6.1 Metropolis-Hastings Algorithmus 6.2 Gibbs-Sampler 6.3 Approximate-Counting Algorithmus