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.
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
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.
- Finite Markov chains
- Stationary/equilibrium distributions and
convergence of Markov chains
- Ergodicity and ergodic theorems
- Markov chain mixing and mixing times
- Markov chain Monte Carlo
- Metropolis Hastings algorithm
- Gibbs sampling
- The Swendsen-Wang algorithm
- The Propp-Wilson algorithm
- Simulated annealing
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)
All handouts will be posted online.
Course assistant and office hours:
- Victor Hu ()
Office hours T 2--4, 238 Sequoia Hall.
- 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
Use of sources (people, books, internet and so on) without
citing them in homework sets results in failing grade for