CSE 598: Markov Chain and Monte Carlo Methods

Overview

CSE 598, Fall 2019, CIDSE, Arizona State University
Instructor: Joshua J. Daymude
Co-Instructor: Andréa W. Richa
MW 4:35pm–5:50pm, BYENG 210

We study a cohesive and elegant theory for (1) counting the size of very large sets — e.g., the set of all matchings of a large graph — and (2) randomly sampling from such sets according to a desired distribution. The course is divided into three units: Markov chain fundamentals and approximate counting, analyzing Markov chain mixing times, and applications of MCMC methods.

The syllabus is available here (last updated 8/28/19, 7:41pm).

My lecture notes (last updated 11/16/19, 7:16pm) are fairly self-contained; Counting, Sampling, and Integrating: Algorithms and Complexity by Jerrum and Markov Chains and Mixing Times by Levin-Peres-Wilmer can be used as references.

Evaluation

Course: 4.54/5. Instructor: 4.81/5.

Schedule

8/26/19: Course overview. Exact counting, part 1 of 3.
8/28/19: Exact counting, part 2 of 3.
9/2/19: Labor Day, classes excused.
9/4/19: Exact counting, part 3 of 3.
9/9/19: Approximate counting and almost-uniform sampling, part 1 of 2.
9/11/19: Approximate counting and almost-uniform sampling, part 2 of 2.
9/16/19: Introduction to Markov chains.
9/18/19: Example Markov chains, part 1 of 3. Lectures online, sign in with your @asu.edu email to access part 1 and part 2.
9/23/19: Example Markov chains, part 2 of 3. (The Metropolis process.)
9/25/19: Example Markov chains, part 3 of 3. (The Ising Model.)
9/30/19: Coupling, part 1 of 3. (The coupling lemma, random walks on the hypercube.)
10/2/19: Coupling, part 2 of 3. (Random walks on the hypercube, card shuffling, and graph coloring.)
10/7/19: Coupling, part 3 of 3. (Graph coloring.)
10/9/19: Path coupling, part 1 of 2. (Graph coloring.)
10/16/19: Review of Assignment 2.
10/21/19: Path coupling, part 2 of 2. (Graph coloring.)
10/23/19: Conductance, part 1 of 2. (Lazy random walks.)
10/28/19: Conductance, part 2 of 2. (Graph coloring.) Spectral gap methods, part 1 of 2.
10/30/19: Spectral gap methods, part 2 of 2. (Lazy random walks.)
11/4/19: Class canceled.
11/6/19: Canonical paths, part 1 of 2. (Lazy random walks.)
11/11/19: Veteran’s Day, classes excused.
11/13/19: Canonical paths, part 2 of 2 (Sampling weighted random matchings.)
11/18/19: MCMC methods for maximum likelihood estimation in phylogeny.
11/25/19–12/4/19: Project presentations.

Assignments

Assignment 1: Out August 26, Due September 4.
Assignment 2: Out September 30, Due October 11.
Assignment 3: Out November 6, Due November 27.

Project

The project description can be found here. Project proposals are due October 18, while the project report and presentation slides are due November 22.

markov-chains

Last updated on December 5, 2019