Seminar: Markov-Ketten

General Information / Allgemeine Informationen

Language: German / Sprache: Deutsch

Dozenten: Prof. Christoph Richard & Prof. Torben Krüger

Zielgruppe: Studierende BSc Mathematik/Technomathematik/Wirtschaftsmathematik, BSc Data Science, Lehramt Gymnasium

Inhalt

Markov-Ketten sind spezielle stochastische Prozesse, deren zeitliche Entwicklung nur von ihrer unmittelbaren Vergangenheit bestimmt wird. Komplexe Systeme werden durch Markov-Ketten oft erstaunlich gut beschrieben. Für die Simulation solcher Systeme liefern auf Markov-Ketten basierende Algorithmen häufig die effizientesten Methoden.

Im Modul „Stochastische Modellbildung“ haben wir elementare Eigenschaften von Markov-Ketten in diskreter Zeit auf endlichen Zustandsräumen kennengelernt. Im Seminar werden wir die Konvergenzgeschwindigkeit einer Markov-Kette ins Gleichgewicht eingehend untersuchen. Außerdem besprechen wir Simulations-Methoden wie den
Metropolis-Algorithmus und den Gibbs-Sampler. Schließlich besprechen wir die Methode der simulierten Auskühlung, mit der man stochastische Näherungslösungen komplizierter Optimierungsprobleme erhalten kann. Diese Methode wurde 1983 von Kirkpatrick, Gelatt and Vecchi eingeführt und am Problem des Handlungsreisenden gestetet, siehe die Grafik rechts aus der Publikation „Optimization by Simulated Annealing“.

Grundlage für das Seminar ist das Buch „Introduction to Markov Chains“ von E. Behrends, Vieweg 2000. Bibliotheks-Signatur 18MI/mat 5.2-587.

Methode der simulierten Auskühlung für das Problem des Handlungsreisenden

Hinweise zur Teilnahme

Wenn Sie an dem Seminar teilnehmen wollen, registrieren Sie sich hierfür bitte in StudOn und Campo.

Zeitplan

Unserer erstes vorbereitendes Treffen wird am 07.02.2024 um 12:00 Uhr in Praktikumsraum 2 (Raum 00.327-128 in der Cauerstrasse 11) stattfinden. Unser zweites vorbereitendes Treffen findet am 15.04.2024 um 12:15 Uhr in Übungsraum 2 (Cauerstrasse 11) statt. Wenn Sie trotz Interesse am Seminar an diesen Terminen nicht teilnehmen können, kontaktieren Sie uns bitte per E-Mail. Das Seminar findet dann ab 29.04.2024 montags 12-14 Uhr im Übungsraum 2 während der Vorlesungszeit des SoSe 2024 statt. Zusätzlich nutzen wir am Anfang des Seminars die unten gelisteten Freitagstermine 8-10 im Übungsraum 1.

Date Topic

07. Februar Erstes vorbereitendes Treffen

15. April Zweites vorbereitendes Treffen

29. April Perron-Frobenius-Theorie

03. Mai Grundlegende Begriffe

06. Mai Transiente Zustände

13. Mai Irreduzible Ketten

17. Mai Markov-Ketten auf kommutativen Gruppen

24. Mai Satz von Krein-Rutman

27. Mai Schnelles Mischen

03. Juni Leitfähigkeit einer Markov-Kette

10. Juni Stoppzeiten und die starke Markov-Eigenschaft

17. Juni Kopplungsmethoden

24. Juni TBA

01. Juli Zufällige Markov-Felder

08. Juli Gibbs-Felder und das Ising-Modell

15. Juli Metropolis-Sampler und simuliertes Abkühlen

Teilnahmevoraussetzungen

Stochastische Modellbildung oder Wahrscheinlichkeitstheorie, Grundkenntnisse in Analysis und Linearer Algebra

Vorträge

Alle teilnehmenden Studierenden sollen einen Vortrag von ca. 60 min Länge halten, welcher ein gutes Verständnis der zugrundeliegenden Literatur reflektiert. Zusätzlich wird eine kurze Zusammenfassung (Handout) den SeminarteilnehmerInnen zur Verfügung gestellt. Der Vortrag ist bis eine Woche vor dem angekündigten Termin vollständig vorzubereiten und wird bei einem Vorbesprechungstermin Prof. Richard vorgestellt.

Lietratur

„Introduction to Markov Chains“ von E. Behrends, Vieweg 2000