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.
Prerequisite: 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.
Syllabus:
 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 SwendsenWang algorithm
 The ProppWilson algorithm
 Simulated annealing
Markov models are widely applicable to the study
of many "realworld" phenomena. The course will develop
applications in selected areas such as genetics, computer
science and scientific computing.
Textbooks:

Levin, D., Peres, Y. and E. Wilmer. Markov Chains and Mixing
Times. American Mathematical Society, 2009 (required)
 Haggstrom, O. Finite Markov Chains and Algorithmic
Applications. Cambridge University Press, 2002 (strongly advised)
 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:
 Victor Hu ()
Office hours T 24, 238 Sequoia Hall.
Grading (tentative):
 Homework assignments: 50%

Homework will generally be distributed on Wednesdays and
due in class the following Wednesday.
 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 exam or final project (to be
decided): 50%
Course policies:
Use of sources (people, books, internet and so on) without
citing them in homework sets results in failing grade for
course.
