Markov Chains 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

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.