Sie sind hier
E-Book

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

AutorThomas Plehn
VerlagBachelor + Master Publishing
Erscheinungsjahr2015
Seitenanzahl53 Seiten
ISBN9783956849510
FormatPDF
KopierschutzWasserzeichen/DRM
GerätePC/MAC/eReader/Tablet
Preis16,99 EUR
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.

Kaufen Sie hier:

Horizontale Tabs

Leseprobe
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.
Blick ins Buch

Weitere E-Books zum Thema: Statistik - Algorhitmen

Wahrscheinlichkeitstheorie

E-Book Wahrscheinlichkeitstheorie
Format: PDF

Dieses Lehrbuch bietet eine umfassende moderne Einführung in die wichtigsten Gebiete der Wahrscheinlichkeitstheorie und ihre maßtheoretischen Grundlagen. Themenschwerpunkte sind: Ma…

Fathom 2

E-Book Fathom 2
Eine Einführung Format: PDF

Fathom 2 ist eine einzigartige dynamische Stochastik- und Datenanalysesoftware, die den besonderen Bedürfnissen der schulischen und universitären Lehre gerecht wird und die hier erstmals in deutscher…

Fathom 2

E-Book Fathom 2
Eine Einführung Format: PDF

Fathom 2 ist eine einzigartige dynamische Stochastik- und Datenanalysesoftware, die den besonderen Bedürfnissen der schulischen und universitären Lehre gerecht wird und die hier erstmals in deutscher…

Fathom 2

E-Book Fathom 2
Eine Einführung Format: PDF

Fathom 2 ist eine einzigartige dynamische Stochastik- und Datenanalysesoftware, die den besonderen Bedürfnissen der schulischen und universitären Lehre gerecht wird und die hier erstmals in deutscher…

Schwingungen mechanischer Antriebssysteme

E-Book Schwingungen mechanischer Antriebssysteme
Modellbildung, Berechnung, Analyse, Synthese Format: PDF

Das Buch stellt systematische Methoden zur Modellbildung von Antriebssystemen dar und erläutert diese sowohl grundsätzlich bei Torsions- und Biegeschwingern, als auch speziell am Beispiel von Kranen…

Schwingungen mechanischer Antriebssysteme

E-Book Schwingungen mechanischer Antriebssysteme
Modellbildung, Berechnung, Analyse, Synthese Format: PDF

Das Buch stellt systematische Methoden zur Modellbildung von Antriebssystemen dar und erläutert diese sowohl grundsätzlich bei Torsions- und Biegeschwingern, als auch speziell am Beispiel von Kranen…

Schwingungen mechanischer Antriebssysteme

E-Book Schwingungen mechanischer Antriebssysteme
Modellbildung, Berechnung, Analyse, Synthese Format: PDF

Das Buch stellt systematische Methoden zur Modellbildung von Antriebssystemen dar und erläutert diese sowohl grundsätzlich bei Torsions- und Biegeschwingern, als auch speziell am Beispiel von Kranen…

Schwingungen mechanischer Antriebssysteme

E-Book Schwingungen mechanischer Antriebssysteme
Modellbildung, Berechnung, Analyse, Synthese Format: PDF

Das Buch stellt systematische Methoden zur Modellbildung von Antriebssystemen dar und erläutert diese sowohl grundsätzlich bei Torsions- und Biegeschwingern, als auch speziell am Beispiel von Kranen…

Schwingungen mechanischer Antriebssysteme

E-Book Schwingungen mechanischer Antriebssysteme
Modellbildung, Berechnung, Analyse, Synthese Format: PDF

Das Buch stellt systematische Methoden zur Modellbildung von Antriebssystemen dar und erläutert diese sowohl grundsätzlich bei Torsions- und Biegeschwingern, als auch speziell am Beispiel von Kranen…

Schwingungen mechanischer Antriebssysteme

E-Book Schwingungen mechanischer Antriebssysteme
Modellbildung, Berechnung, Analyse, Synthese Format: PDF

Das Buch stellt systematische Methoden zur Modellbildung von Antriebssystemen dar und erläutert diese sowohl grundsätzlich bei Torsions- und Biegeschwingern, als auch speziell am Beispiel von Kranen…

Weitere Zeitschriften

FESTIVAL Christmas

FESTIVAL Christmas

Fachzeitschriften für Weihnachtsartikel, Geschenke, Floristik, Papeterie und vieles mehr! FESTIVAL Christmas: Die erste und einzige internationale Weihnachts-Fachzeitschrift seit 1994 auf dem ...

Archiv und Wirtschaft

Archiv und Wirtschaft

"Archiv und Wirtschaft" ist die viermal jährlich erscheinende Verbandszeitschrift der Vereinigung der Wirtschaftsarchivarinnen und Wirtschaftsarchivare e. V. (VdW), in der seit 1967 rund 2.500 ...

Berufsstart Bewerbung

Berufsstart Bewerbung

»Berufsstart Bewerbung« erscheint jährlich zum Wintersemester im November mit einer Auflage von 50.000 Exemplaren und ermöglicht Unternehmen sich bei Studenten und Absolventen mit einer ...

Bibel für heute

Bibel für heute

BIBEL FÜR HEUTE ist die Bibellese für alle, die die tägliche Routine durchbrechen wollen: Um sich intensiver mit einem Bibeltext zu beschäftigen. Um beim Bibel lesen Einblicke in Gottes ...

CE-Markt

CE-Markt

CE-Markt ist Pflichtlektüre in der Unterhaltungselektronik-Branche. Die Vermarktung von Home und Mobile Electronics mit den besten Verkaufsargumenten und Verkaufsstrategien gehören ebenso zum ...

IT-BUSINESS

IT-BUSINESS

IT-BUSINESS ist seit mehr als 25 Jahren die Fachzeitschrift für den IT-Markt Sie liefert 2-wöchentlich fundiert recherchierte Themen, praxisbezogene Fallstudien, aktuelle Hintergrundberichte aus ...

Eishockey NEWS

Eishockey NEWS

Eishockey NEWS bringt alles über die DEL, die DEL2, die Oberliga sowie die Regionalligen und Informationen über die NHL. Dazu ausführliche Statistiken, Hintergrundberichte, Personalities ...

FileMaker Magazin

FileMaker Magazin

Das unabhängige Magazin für Anwender und Entwickler, die mit dem Datenbankprogramm Claris FileMaker Pro arbeiten. In jeder Ausgabe finden Sie von kompletten Lösungsschritten bis zu ...