Seminar: Markov chains and mixing times
Summer semester 2021
Prof. Dr. Silke Rolles
- Time and place: weekly on Thursday, 10:15-11:45
- First talk: April 22, 2021
- Prerequisites: Einführung in die Wahrscheinlichkeitstheorie (MA1401); Markovketten (MA2404) and probability theory (MA2409) are useful.
- Content: We will discuss Markov chains and mixing times. One question of interest is how long it takes until a Markov chain approaches its stationary distribution up to a given error. An application concerns mixing a deck of cards: How long does one need to shuffle a deck of cards?
- Literature:
- David Levin, Yuval Peres and Elizabeth Wilmer: Markov chains and mixing times. Second edition. pdf ^{}
- Manfred Lehn: Wie halte ich einen Seminarvortrag ^{}
- Bachelor or Master thesis: It is possible to write a Bachelor or Master thesis on a related topic.
- Talks: Every talk is based on a chapter of the book by Levin, Peres and Wilmer.
- Chapter 1 Introduction to finite Markov chains
- Chapter 2 Classical and useful Markov chains
- Chapter 4 Introduction to Markov chain mixing
- Chapter 5 Coupling
- Chapter 6 Strong stationary times
- Chapter 7 Lower bounds on mixing times
- Chapter 8 The symmetric group and shuffling cards
- Chapter 9 Random walks on networks
- Chapter 10 Hitting times
- Chapter 11 Cover times
- Chapter 12 Eigenvalues