Markov Chain Analysis

# Markov Chain Analysis

## Advanced Topics in Probability (MATH-GA 2932.001), Spring 2015

Instructor: Eyal Lubetzky

Time and place: Thursday 9:00–10:50 at WWH 1302.

Office hours: Thursday 11:00–12:00 at WWH 813.

Course description

The study of Markov chains has surged in the last few decades, driven by applications both in theoretical mathematics and computer science and in applied areas such as statistical physics, mathematical biology, economics and statistics. Nowadays, Markov chains are considered to be one of the most important objects in probability theory.

A Markov chain is a stochastic process with the property that, conditioned on its present state, its future states are independent of the past states. Under mild assumptions, a Markov chain on a finite state space converges to a unique stationary distribution, and of particular importance is the rate of this convergence: the mixing time of a chain is the number of steps needed for its distribution to get reasonably close to its limit. In the early 1980's, pioneering works of Aldous and of Diaconis brought the concept of mixing times to a wider audience, using card shuffling as a central example. Since then, both the field and its interactions with computer science and statistical physics have grown tremendously. By now there are many methods for analyzing the mixing time of a Markov chain, ranging from coupling techniques to chain comparisons to log-Sobolev inequalities, to name a few. We will survey these methods and highlight their applications, with a special emphasis on Markov chains that model the evolution of classical interacting particle systems such as the Ising model.

Prerequisites: Basic experience in Probability Theory.

Textbooks
1. (main textbook) Markov Chains and Mixing Times by Levin, Peres and Wilmer (printed edition freely available here).
2. (supplementary) Lectures on finite Markov chains by Saloff-Coste, Lectures on probability theory and statistics (Saint-Flour, 1996), 301–413.
3. (supplementary) Reversible Markov Chains and Random Walks on Graphs by Aldous and Fill (monograph freely available here).
Topics
• Introduction to classical Markov chain analysis; total variation mixing and coupling methods.
• L2-mixing vs. L1-mixing; spectral decomposition; conductance and Cheeger inequalities.
• Strong stationary times; Markov chains on the symmetric group.
• Markov chains for the evolution of spin-systems (e.g., the Ising model, legal graph colorings) and the interplay between dynamical and static phase transitions.
• Path Coupling and log-Sobolev inequalities.
• The Cutoff phenomenon for Markov chains; random walks on expander graphs.
• Perfect simulation (coupling from the past).
Problem sets: