Markov Ketten & Random sampling -- Wintersemester 2008/09

<-- Diese Seite --------- http://page.math.tu-berlin.de/~felsner/Lehre/semMK08.html -->

Seminar
Ausgewählte Kapitel der Graphentheorie:
Markov Ketten & Random Sampling

Wintersemester 2008/09
Prof. Stefan Felsner
Sprechstunde n.V.

LV-Nr.: 0230 L 316

$Zeichnung$

Seminarwochenende: 6.-9. Februar 2009

Blitzvorträge: Fr. 5. Dez., 14:15 Raum MA 550

Thema:

Wir beschäftigen uns mit Markov Ketten die es ermöglichen ein zufälliges Element aus einer großen kombinatorischen Menge zu erzeugen (random sampling). Beispiele für solche kombinatorischen Mengen sind:

Menge der aufspannenden Bäume eines Graphen (siehe Bild).
Menge der perfekten Matchings eines Graphen.
Menge der linearen Erweiterungen einer Ordnung.

Meistens ist es nicht schwer eine Markov Kette anzugeben die wenn man sie lange genug laufen läßt ein zufälliges Element ausgibt. Interessant ist die mathematische Behandlung der Frage, was ist lange genug. Dafür gibt es Techniken wie Kanonische Wege und Couplings. Dies und die Zusammenhänge mit approximativem Zählen sind Thema des Seminars.

Vorträge:

Thema	Vortragende	Quelle	Betreuung
Basics on Probability and Markov Chains	>>> Eigenlektüre <<<	OH 1-15
Fundamentals of Markov Chains	Tillmann Miltzow	OH 23-43	Felsner
Coupling and Linear Extensions	Josef Levant	Jer.Kap4 & Bubley-Dyer	Massow
The Propp-Wilson Algorithm	Laura Buhmann	OH 76-98	Massow
Canonical Paths and Matching	Julia Rucker	Jer.Kap5	Heldt
Sampling Knapsack Solutions	Adrian Raeder	Morris-Sinclair & Guruswami (Survey)	Ueckerdt
Sampling and Counting - Inapproximability	Sofia Börner	Jer.Kap3+7	Ueckerdt
Markov Chains for Lattice Paths	Tobias Friedel	Luby-Randall-Sinclair & Martin-Randall	Ueckerdt
Markov Chains for Spanning Trees	Kolja Knauer	Wilson & Propp-Wilson
Conductance and the Volume of a Convex Body	Ingo Spiegelberg	Jer.Kap6 & Karzanov-Khachian	Felsner Massow
The Mixing Rate of the Triangulation Walk	Laura Traverso	McShine-Tetali	Felsner
Eulerian Orientations of the Triangular Lattice	Bernhard Schmidt	Creed	Felsner
Shuffling a Deck of Cards	Gregor Myrach	Mann	Heldt

Literatur:

Mark Jerrum: Counting, Sampling and Intergration: Algorithms and Complexity, Birkhäuser 2003. (Elektronische Kopie von Mark Jerrum -- Direktzugriff)
Olle Häggström: Finite Markov Chains and Algorithmic Applications, Cambr. Univ. Press, 2002. (Elektronische Kopie at King Fahd University)
Kapitel aus Motwani-Rhagavan und Mitzenmacher-Upfal.
Originalarbeiten.

Termine:

Wir werden das Seminar als Blockseminar im Umland durchzuführen: Seminarwochenende: 6.-9. Februar 2009, KiEZ Frauensee
Weitere Termine sind:

Vorbesprechung: Montag 13. Okt. 16:00, MA 641.
Blitzvorträge: Fr. 5. Dez., 14:15 Raum MA 550

Zielgruppe:

Studentinnen und Studenten der Mathematik, Techno- und Wirtschaftsmathematik im Hauptstudium.
Dieses Seminar wird im Rahmen des Studienschwerpunkts Diskrete Strukturen empfohlen.

Zuletzt bearbeitet 12. Nov. 2008