Seminar on Markov Chains and Mixing Times, Fall 16/17

Haim Kaplan

We will follow some chapters of the book on Markov Chain and Mixing Times  by Levin, Peres, and Wilmer. For lectures 6,7,8,9 you may also use the relevant parts in references [1] and [2] and for lectures 11 and 12 use the relevant parts of references [3] and [4]. You may also use other material available (like lecture notes etc) that covers the topic of your chapter.

Please read chapter one. I will not cover all of it in the first lecture.

Tentative schedule

1. (Nov 2) An introductory lecture

2. (Nov 9) Chapter 2: Classical and useful Markov Chains. Tomer Haimovitch

3. (Nov 16) Chapter 3: Markov Chain Monte Carlo : Metropolis and Glauber Chains. Yael Golan

4. (Nov 23) Chapter 4 (part 1): Introduction to Markov Chain Mixing. Dan Dorfman

5. (Nov 30) Chapter 4 (part 2): Introduction to Markov Chain Mixing. Omer Zentner

6. (Dec 7) Chapter 5 (part 1): Coupling. Jay Tenenbaum

7. (Dec 14) Chapter 5 (part 2): Coupling. Guy Oren

8. (Dec 21) Chapter 14 (part 1): Path Coupling. Oleg Zlydenko

9. (Dec 28) Chapter 14 (part 2): Path Coupling. Tomer Loterman

10. (Jan 4) Chapter 6: Strong Stationary Times. Yizhak Elboher

11. (Jan 11) Chapter 22 (part1): Coupling from the past, part 1 Noam Mor, part 2 Elad Katz

12. (Friday Jan 20, 10:12:30, instead of Jan 18) Chapter 22 (part 2): Coupling from the past, Elad Katz and Random Walks on graphs and cover times, Ravid Cohen

13. (Jan 25) Chapter 7: Lower bounds on Mixing times. Yonatan Nakar

References :

1.    Mathematical foundations of Markov chain Monte Carlo method, by M. Jerrum.

2.    Chapter 4 of lectures notes by Mark Jerrum (link is at the bottom of the page).

3.    The original paper by Propp and Wilson.

4.    The following page contains many references regarding the Propp Wilson algorithm. In particular look at the relevant chapters in the book by Haggastorm.