CS 292 A - Markov Chain Monte Carlo (MCMC) Algorithms

Fall 2021, UCSB
Mondays and Wednesdays, 11am-12:50pm, in Phelps 2510
Professor Eric Vigoda
Office hours: Tuesdays and Thursdays at 8pm (via Zoom)

Course overview: This course studies Markov Chain Monte Carlo (MCMC) algorithms. MCMC algorithms are a widely used tool for sampling from distributions defined over a huge combinatorial set. It is often easy to define a Markov chain with the desired distribution as its equilibrium distribution but it is difficult to design a chain which converges efficiently and to determine convergence. This is a theoretical course focusing on mathematical tools for analyzing the convergence rate of Markov chains. This course is appropriate for both undergraduate and graduate students with a background in the analysis of algorithms and discrete mathematics.

Textbooks: [Jerrum] Mark Jerrum's book, available here (search "ETH") and
[LPW] Markov Chains and Mixing Times by [Levin-Peres-Wilmer].

• Homeworks: 50%
• Project: 50%
All homeworks will be submitted via Gradescope.
For the project, there is a theoretical option of reading a paper and writing lecture notes on it, or
a programming option of implementing an algorithm and running simulations to test its performance.
We will discuss the options in more detail during the course.

Additional lecture notes available here.
Week 1 (9/27, 9/29): Markov Chain Basics:
Stationary distribution, ergodic, reversible, mixing time, Metropolis filter
Eric's 9/27 notes
Eric's 9/29 notes
See: [Jerrum] Chapters 3.1 and 3.3, and [LPW] Chapter 1, 4.1-4.2
HW 1 (latex)

Monday, October 4: Coupling Technique:
Coupling and variation distance, Mixing time, simple random walk examples
Eric's 10/04 notes
See: [LPW] Chapter 4.1-4.2

Wednesday, October 6: Random Colorings:
Coupling for colorings, path coupling
Eric's 10/06 notes
See: [Jerrum] Chapter 4 (and Section 4.3 for path coupling)
HW 2 (latex)

Monday, October 11: Phase transitions and the Ising model:
Phase transitions and mixing time, simulated annealing, and MC3
Eric's 10/11 notes

Wednesday, October 13: Coupling from the past
Eric's 10/13 notes
see: [LPW] Chapter 25
HW 3 (latex)

Monday, October 18 and Wednesday, October 20:
Conductance and Canonical Paths Technique:
Eric's 10/18 notes
Eric's 10/20 notes
See: [LPW] Chapter 7.2 (for conductance), and [Jerrum] Chapter 5 (for canonical paths)

Monday, October 25 and Wednesday, October 27:
Random matchings and random perfect matchings of dense graphs
Eric's 10/25 notes
Eric's 10/27 notes
See: [Jerrum] Chapter 5

Monday, November 1:
Random perfect matchings of bipartite graphs
Eric's 11/1 notes
See: Some additional notes

Wednesday, November 3:
Counting perfect matchings of planar graphs
Eric's 11/3 notes

Monday, November 8:
Random spanning trees
Eric's 11/8 notes

Wednesday, November 10:
Swendsen-Wang algorithm
Eric's 11/10 notes

Monday, November 15:
Unique stationary distribution
Eric's 11/15 notes

Wednesday, November 17:
Functional analysis and Variance
Eric's 11/17 notes

Monday, November 29:
Matroids and approx counting via sampling
Eric's 11/29 notes

Wednesday, December 1:
Random Bases of a Matroid
Guest lecture by Giorgos Mousa