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


Homeworks:

Assignment 1
Assignment 2
Assignment 3

COURSE GOALS:
The aim of the course is that the students learn various general techniques for
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.

INTENDED AUDIENCE:
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.

Course Description
In recent years, there has been a renewed interest in Markov chains with connections
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:
  • Introduction
  • Mixing times
  • Coupling Methods
  • Strong stationary times
  • Bounds in terms of isoperimetric behavior (Cheeger inequalities)
  • Relations to phase transitions
  • Card shuffling
  • Cut-off behavior
  • Coupling from the past
  • Cover/Hitting times

    Prerequisites:
    Reasonable experience in probability theory (feel free to come and
    discuss your background with us).

    Main Course literature (THERE IS A NEWER VERSION WHICH YOU CAN OBTAIN FROM ME) :
    Markov 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

    Examination Form:
    There will be some homeworks and a final oral exam.

    Kursexaminator:
    Jeff Steif (steif@chalmers.se)

    Registration: Please email Jeff Steif (steif@chalmers.se) for registration.
    Last modified: Tuesday December 1 10:15:34 MET DST 2013