Stats 318
Modern Markov Chains
Spring 2012



Instructor
Emmanuel Candes
113 Sequoia Hall

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

   

Lectures
Monday and Wednesday
9:30-10:45 a.m.
200 Sequoia Hall

 

Home

Handouts

Homework


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 Swendsen-Wang algorithm
  • The Propp-Wilson algorithm
  • Simulated annealing
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.


Textbooks:

  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:

  • Victor Hu ()
    Office hours T 2--4, 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.