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.
  1. Chapter 1 Introduction to finite Markov chains
  2. Chapter 2 Classical and useful Markov chains
  3. Chapter 4 Introduction to Markov chain mixing
  4. Chapter 5 Coupling
  5. Chapter 6 Strong stationary times
  6. Chapter 7 Lower bounds on mixing times
  7. Chapter 8 The symmetric group and shuffling cards
  8. Chapter 9 Random walks on networks
  9. Chapter 10 Hitting times
  10. Chapter 11 Cover times
  11. Chapter 12 Eigenvalues