|
Logistics: The course will be
offered online. We will have live lectures on Zoom at
the times indicated above. Please go to Canvas to
retrieve the links to the lectures.
Because of recent evidence of Zoom-bombing activities,
you are not permitted to share the video links with
anyone.
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
- Hidden Markov models
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:
-
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:
- Stephen Bates ()
Office hours F 1--3 p.m., Zoom (online).
- Michael Celentano ()
Office hours W 9-11 a.m., Zoom (online).
Grading (tentative):
- Homework assignments: 50%
-
Homework will generally be distributed on Thursdays and
due the following Friday.
- 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 project: 50%
Course policies:
Use of sources (people, books, internet and so on) without
citing them in homework sets results in failing grade for
course.
|