|
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.
Syllabus:
-
- 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.
Textbooks:
- Haggstrom, O. Finite Markov Chains and Algorithmic Applications. Cambridge University Press, 2002 (required)
- Grimmett, G. R., and D. R. Stirzaker. Probability and Random Processes. 3rd ed. New York, NY: Oxford University Press, 2001 (required)
- Lawler, G. An introduction to stochastic processes; 2nd. Edition, Chapman & Hall/CRC
(optional)
- Taylor, H. and S. Karlin. An Introduction to Stochastic Modeling; 3rd. Edition. Academic Press
(optional)
- Taylor, H. and S. Karlin. A first Course in Stochastic Processes;
2nd. Edition, Academic Press (optional)
Handouts: 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, plan@acm.caltech.edu
Tuesday 4-5 p.m. and Thursday 1:30-2:30 p.m., Firestone 212
Grading:
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%.
|