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.