ACM 216
Markov Chains
Discrete Stochastic Processes and Applications
Winter 2007

Emmanuel Candes
300 Firestone

Monday, Wednesday, Friday
1:30-2:30 p.m.
107 Downs

Office Hours: Friday 4-5 p.m. or by appointment






Description: The aim of this course is to introduce the basic 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: -
ACM/EE 116 or equivalent. This is not a first course in probability! Students should also be comfortable with linear algebra (undergraduate level). Some programming experience or some willingless to learn. Prior knowledge of matlab not required.


  • Finite Markov chains
  • Stationary/equilibrium distributions and convergence of Markov chains
  • Ergodicity and ergodic theorems
  • Reversible Markov chains
  • Birth and branching processes
  • Markov chain Monte Carlo
  • Metropolis Hastings algorithm
  • Coupling from the past
  • 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, simulations and scientific computing, finance.

If time allows, the course will also discuss some aspects of martingale theory.


  1. Haggstrom, O. Finite Markov Chains and Algorithmic Applications. Cambridge University Press, 2002 (required)
  2. Grimmett, G. R., and D. R. Stirzaker. Probability and Random Processes. 3rd ed. New York, NY: Oxford University Press, 2001 (required)
  3. Lawler, G. An introduction to stochastic processes; 2nd. Edition, Chapman & Hall/CRC (optional)
  4. Taylor, H. and S. Karlin. An Introduction to Stochastic Modeling; 3rd. Edition. Academic Press (optional)
  5. Taylor, H. and S. Karlin. A first Course in Stochastic Processes; 2nd. Edition, Academic Press (optional)

I will do my best to post online all the handouts given in class. By the way, Sheila Shull (217 Firestone) is a person you can contact at any time (between 9:30am and 5pm) if you need administrative information. Her phone number is 626-395-4560.

Teaching Assistant and Office Hours:

Yaniv Plan,
Tuesday 4-5 p.m. and Thursday 1:30-2:30 p.m., Firestone 212


Homework assignments: 60%
  • Homework will generally be distributed on Wednesdays and due in class the following Wednesday.
  • There will be about 5 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): 40%.