## Markov Chain Monte Carlo Methods

Fall 2017, Georgia Tech

Tuesday and Thursday, noon-1:15pm, in Cherry Emerson room 320

*Instructors:* Eric Vigoda and Antonio Blanca

* Office hours:* Monday and Wednesday 10-11am in Klaus 2222

Textbooks:
Mark Jerrum's book
and
Markov Chains and Mixing Times by [Levin-Peres-Wilmer].

** Grading: **
Lecture notes/homeworks: 50%
Project: 50%

Here are some project ideas.

**Lectures:**
- Lectures 1-2 (8/22, 8/24):
*Classical Exact Counting Algorithm*

- Kasteleyn's poly-time algorithm for the Permanent of Planar graphs

Eric's notes and
scribe notes

- Lectures 3-4 (8/29, 8/31):
* Hardness of Exact Counting*

- Valiant's result: the Permanent is #P-complete

Eric's notes:
Part 1
and Part 2;
scribe notes

- Lectures 5-6 (9/5,9/7):
* Markov Chains and Coupling Intro*

- Eric's notes: Markov chain basics
and coupling;
scribe notes

- Lecture 7 (9/14):
* Coupling example: Colorings*

- Eric's notes;
scribe notes

- Lecture 8 (9/19):
* Conductance*

- Antonio's notes

- Lecture 9 (9/21):
* Seminar by Andreas Galanis: *
Random Walks on Small-World Networks

- Lecture 10 (9/26):
* Spectral Gap*

- Antonio's notes

- Lecture 11 (9/28):
* Canonical Paths*

- Eric's notes

- Lecture 12 (10/3):
* Random Matchings*

- Eric's notes

- Lecture 13 (10/5):
* Random Perfect Matchings of Bipartite Graphs*

- Eric's notes

- Lecture 14 (10/12):
* Spectral Gap and Mixing Time*

- Antonio's notes

- Lecture 15 (10/17):
* Phase Transitions*

- Eric's notes;
scribe notes

- Lecture 16 (10/19):
* Swendsen-Wang Algorithm*

- Antonio's notes

- Lecture 17 (10/24):
* Bayesian inference for Phylogeny*

- Eric's notes

- Lecture 18 (10/26):
* Coupling from the Past*

- Eric's notes

- Lecture 19 (10/31):
* Random Spanning Tree*

- Eric's notes

- Lecture 20 (11/2):
* Coupling for Independent Sets*

- Eric's notes

- Lecture 21 (11/7):
* Phase transitions and Fast Mixing*

- Antonio's notes

- Lecture 22 (11/9):
* Volume Computation*

- Santosh's notes and
scribe notes

- Lecture 23 (11/14):
* Analysis of Ball Walk*

- Eric's notes

- Lecture 24 (11/16):
* Approximating the Partition Function*

- Eric's notes