Markov-Ketten I 2016/17
Dozent: Dr. Anton Klimovsky
Vorlesung: Dienstag, 10:15-11.45 (@ WSC-S-U-3.03)
Übungen: Mittwoch, 10:15-11:45 (@ WSC-N-U-4.05)
Zielgruppe: Master-Studiengang mit Lehramtsoption Gymnasium/Gesamtschule, Wirtschaftsmathematik (Bachelor), Technomathematik (Bachelor), Mathematik (Bachelor)
Voraussetzungen: Einführung in die Stochastik
Umfang: 2 + 1 SWS
Beginn: 18.10.2016
Klausurtermin: 07.02.2017
Einsicht:
* Freitag, 10.02.2017 13:00-14:00;
* Montag, 13.02.2017, 14:00-15:00.
Inhalt
Nach Andrey Markov genannt bilden die Markov-Ketten (MK) eine wichtige und gut studierte Klasse der abhängigen Zufallsvariablen. In der jungsten Zeit haben sich MK zu einem wichtigen Modellierungsbaustein in allen Wissenschaften (Informatik, Physik, Chemie, Biologie, Soziologie, Wirtschaft, usw.) entwickelt.
In dieser Vorlesung werden wir die grundlegende Begriffe und Ergebnisse über MK in diekreter Zeit kennen lernen. Der Stoff wird mit vielen Beispielen illustriert wie z.B. PageRank-Algorithmus (die urspüngliche Basis der Google Inc.-Suche), Monopoly-Spiel, usw.
Sei $\mathbb{Z}+ = { 0, 1, 2, \ldots } $ eine diskrete Zeitachse. Eine (zeitdiskrete) MK ist eine Folge der Zufallsvariablen ${X_n}{n \in \mathbb{Z}_+}$ mit der folgenden charakteristischen Eigenschaft:
- Für jeden Zeitpunkt $n \in \mathbb{Z}+$ hängt die Zukunft $ { X{k} }{k > n} $ der MK nur von der Gegenwart $X_n$ und nicht von der Vergangenheit ${ X_0, X_1, \ldots, X{n-1}}$ ab.
Die MKen sind also eine natürliche stochastische Version des analytischen Begriffs "dynamisches System".
Die folgenden Themen werden in der Vorlesung bearbeitet:
- Wiederholung einiger wichtiger Bausteinen der Stochastik.
- Markov-Ketten und Graphen. Klassifizierung der Zustände.
- Langzeitverhalten der MK. Ergodensatz.
N.B.! Das Modul Markov-Ketten besteht aus zwei Teilen (MK I und II) die insgesamt 9 ECTS Punkte bringen. Diese Vorlesung ist das erste Teil. Das zweite Teil wird im Sommersemester 2017 angeboten, in welchem Markov-Ketten Monte-Carlo-Verfahren, Mischungszeiten und die MKen in der stetigen Zeit bearbeitet werden.
Übungsbetrieb
- Übungsblätter und aktuellen Informationen sind in Moodle.
- Allgemeine Informationen.
- Die Übungen beginnen am 1.11.2016 und finden in alle zwei Wochen statt.
Literatur
- Privault. Notes on Markov Chains. [pdf]
- Lawler. Introduction to Stochastic Processes.
- Durrett. Essentials of stochastic processes. [pdf, Chapter 1]
Weitere Quellen:
* Bremaud. Markov chains. Gibbs fields, Monte Carlo simulation, and queues. 1999.
Doyle, Snell. Random Walks and Electric Networks. [pdf]
Grinstead and Snell. Introduction to Probability. [pdf, Chapter 11]
Grimmett, Stirzaker. Probability and Random processes.
Häggström. Finite Markov Chains and Algorithmic Applications.
Häggström. Streifzüge durch die Wahrscheinlichkeitstheorie.
Levin, Peres, Wilmer. Markov Chains and Mixing Times. [pdf]
Lyons, Peres. Probability on Trees and Networks. [pdf]
Norris. Markov Chains.
* Privault. Understanding Markov Chains.