## 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].

** Grading: **
- 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 MC^{3}

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