Mixing Times for Markov Chains (Part I)
(7 1/2 points)
Spring 2014, 3rd reading period
(January 20th-March 7th)
Lecturers: Timo Hirscher and Jeffrey Steif
Class times and place
Wednesdays 13:15-15:00 and Fridays 8:00-9:45 in Room MVH12
The aim of the course is that the students learn various general
analyzing the mixing times of finite state Markov chains
(such as coupling and
stationary times for example) as well as learning
many of the important concepts
that arise in Markov chains,
such as hitting times and spectral gap.
This course is intended for graduate students in
mathematics, mathematical statistics
and computer science
as well as masters students with appropriate backgrounds.
(Please feel free to discuss your backround with the lecturers to see
if it is suitable).
Faculty are also of course very welcome.
In recent years, there has been a renewed interest in Markov chains with
to many areas, including
theoretical computer science and
physics. Much of this course
will deal with the mixing rate of Markov Chains
which determines how many steps one
needs to run the Markov Chain
so that it is close to equilibrium. These questions turn
out to be
related to a number of different areas.
VERY PRELIMINARY TOPICS TO BE COVERED:
Strong stationary times
Bounds in terms of isoperimetric behavior (Cheeger inequalities)
Relations to phase transitions
Coupling from the past
Reasonable experience in probability theory (feel free to come
discuss your background with us).
Main Course literature (THERE IS A NEWER VERSION WHICH YOU CAN OBTAIN
FROM ME) :
Chains and Mixing Times by Levin, Peres and Wilmer
Other literature if you want:
Reversible Markov Chains and Random Walks on Graphs by Aldous and Fill
Finite Markov Chains and Algorithmic Applications by Olle Häggström
There will be some homeworks and a final oral exam.
Jeff Steif (firstname.lastname@example.org)
Please email Jeff Steif (email@example.com) for registration.
Last modified: Tuesday December 1 10:15:34 MET DST 2013