Markov-Ketten I 2015/16

Dozent: Dr. Anton Klimovsky
Vorlesung: Dienstag, 10:15-11.45 (@ WSC-S-U-3.03)
Übungen: Mittwoch, 10:15-11:45 (@ WSC-S-U-3.02) Johannes Fiedler
Zielgruppe: Lehramt MasterGyGe/BK, Lehramt LGyGe/LBk (nach LPO 2003), Bachelor Mathematik
Voraussetzungen: Einführung in die Stochastik.
Umfang: 2 + 1 SWS.
Beginn: 20. Oktober
Klausurtermin: 16.02.2016

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:

  1. Wiederholung einiger wichtiger Bausteinen der Stochastik.
  2. Markov-Ketten und Graphen. Klassifizierung der Zustände.
  3. Langzeitverhalten der MK. Ergodensatz. Markov-Ketten Monte-Carlo-Verfahren.

Im Sommersemester wird das zweite Teil des Kurses angeboten (MK II), in welchem die MKen in der stetigen Zeit bearbeitet werden.

Übungsbetrieb

Literatur

  • Bremaud. Markov chains. Gibbs fields, Monte Carlo simulation, and queues. 1999.
  • Durrett. Essentials of stochastic processes. [pdf, Chapter 1]
  • 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.
  • Lawler. Introduction to Stochastic Processes.
  • Levin, Peres, Wilmer. Markov Chains and Mixing Times. [pdf]
  • Lyons, Peres. Probability on Trees and Networks. [pdf]
  • Norris. Markov Chains.
  • Privault. Understanding Markov Chains.
  • Privault. Notes on Markov Chains. [pdf]