**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.**