ORIE 7591  Markov Mix and Match
Course Description
The goal of this course is to provide an introduction to the theory of Markov chains, with an emphasis on their applications to algorithms, learning and control. The main tool we will focus on is the mixing properties of finitestate, discretetime, reversible Markov chains, i.e., how ‘fast’ a given chain converges to its stationary distribution from any starting state. This may seem like a narrow question; however, it is central to the analysis of Markov Chain Monte Carlo, with connections to classical questions in statistical physics, numerical integration, randomized algorithms and combinatorial optimization, and increasingly, applications in distributed computing, largescale graph mining, reinforcement learning and highdimensional optimization.
 Course Syllabus: pdf
Coursework
 Homeworks:
 Scribing:

Each student should scribe 12 lectures (depending on class size), in groups of 2.
 Template files
 Signup sheet
Course Information
 Lectures: MF 8.40am11.15am, Phillips 213, Map
 Instructor: Siddhartha Banerjee, 229 Rhodes Hall, email
References
There are two excellent sources for a lot of the techniques we will cover
 Reversible Markov Chains and Random Walks on Graphs by Aldous and Fill
 Markov Chains and Mixing Times by Peres, Levin and Wilmer
The first is a remarkable unfinished monograph, which has been online since the 1990s, and inspired a lot of the work in this field. The second is a more recent book which gives a nice and accessible introduction to many of the topics we will study.