Stats 318
Modern Markov Chains
Spring 2020

Emmanuel Candes
144 Sequoia Hall

Office Hours: M 1:30-2:30
or by appointment


Tuesday anf Thursday
3:00-4:20 p.m.
Online (see below)





Logistics: The course will be offered online. We will have live lectures on Zoom at the times indicated above. Please go to Canvas to retrieve the links to the lectures.

Because of recent evidence of Zoom-bombing activities, you are not permitted to share the video links with anyone.

Description: The aim of this course is to introduce the theory of Markov chains and to develop applications to a number of randomized algorithms. I will also do my best to offer a glimpse of some of the current research problems.

Probability theory at the level of Stats 217 and 218, and if possible Stats 310AB. Students should also be very comfortable with linear algebra. Some programming experience or some willingless to learn.


  • Finite Markov chains
  • Stationary/equilibrium distributions and convergence of Markov chains
  • Ergodicity and ergodic theorems
  • Markov chain mixing and mixing times
  • Coupling
  • Markov chain Monte Carlo
  • Metropolis Hastings algorithm
  • Gibbs sampling
  • The Swendsen-Wang algorithm
  • The Propp-Wilson algorithm
  • Simulated annealing
  • Hidden Markov models
Markov models are widely applicable to the study of many "real-world" phenomena. The course will develop applications in selected areas such as genetics, computer science and scientific computing.


  1. Levin, D., Peres, Y. and E. Wilmer. Markov Chains and Mixing Times. American Mathematical Society, 2009 (required)
  2. Haggstrom, O. Finite Markov Chains and Algorithmic Applications. Cambridge University Press, 2002 (strongly advised)
  3. J. Liu. Monte Carlo Strategies in Scientific Computing. Springer Verlag, New York, 2001 (optional)

Handouts: All handouts will be posted online.

Course assistant and office hours:

  • Stephen Bates ()
    Office hours F 1--3 p.m., Zoom (online).
  • Michael Celentano ()
    Office hours W 9-11 a.m., Zoom (online).

Grading (tentative):

  • Homework assignments: 50%
    • Homework will generally be distributed on Thursdays and due the following Friday.
    • There will be about 6 assignments, and your lowest score will be dropped in the final grade.
    • Late homeworks will NOT be accepted for grading (medical emergencies excepted with proof).

  • Final project: 50%

Course policies: Use of sources (people, books, internet and so on) without citing them in homework sets results in failing grade for course.