## 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

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.