Markov chains and mixing times - Yuval Peres

Markov chains and mixing times

Markov chain Monte Carlo (MCMC) is a widely used algorithm in Mathematical Physics, Computer Science and Statistics, in order to sample from intractable distributions.

The main component in the running time of the MCMC algorithm is the “mixing time” of the underlying Markov chain., i.e., the number of steps one needs to run the chain to approximate the stationary distribution well. The modern mathematical theory of Markov chain mixing was initiated by Aldous and Diaconis in the 1980s. They described the “cutoff phenomenon” where the distribution of the Markov chain approaches the limiting stationary distribution abruptly. They wrote “From a theoretical viewpoint, there are interesting questions concerning the cut-off phenomenon. This occurs in all the examples we can explicitly calculate, but we know no general result which says that the phenomenon must happen for all “reasonable” shuffling methods”. 

This book introduces the modern theory of Markov chain mixing, starting from basic notions and inequalities, and later developing the key tools used in analysis of Markov chains; Coupling, expansion, strong stationary times, electrical networks, eigenvalues, comparison inequalities, transportation methods (path coupling) and martingales. These tools are then applied to a variety of interesting chains, including random walks on graphs, card shuffling, Glauber dynamics for the Ising model, birth and death chains and lamplighter walks. Advanced chapters are devoted to the cutoff phenomenon, the exclusion process, and chains on infinite state spaces. The book has been used in undergraduate and graduate. courses in many universities.

Related links

Related open problems

If you have ideas or comments pertaining to the open problems listed below, please send email to yuval@yuvalperes.com

1.

Let V be a monotone subset of the hypercube {0,1}^n, i.e., if x is in V and y in the hypercube is greater or equal than x in each coordinate, then y must be in V as well. Assuming that the volume of V is at least a half of the hypercube, what is the best upper bound one can prove for the mixing time of lazy simple random walk on V? See Ding, Jian, and Elchanan Mossel. “Mixing under monotone censoring.” Electronic Communications in Probability 19 (2014): 1-6 where an upper bound of order n^3 is proved. It is conjectured that the answer is O(n log n).

2.

Consider the Markov chain on the set GL_n(2) of n by n invertible matrices, defined as follows. Given a matrix A, choose two distinct rows i and j uniformly at random, and add row i to row j modulo 2. What is the mixing time of this chain? The best upper bound known, due to Kassabov, is O(n^3), and the best lower bound known is of order n^2/(log n). See the discussion in page 2 of the paper: Ben-Hamou, Anna, and Yuval Peres. “Cutoff for a stratified random walk on the hypercube.” Electronic Communications in Probability 23 (2018): 1-10. (Link to PDF).

3.

Consider supercritical bond percolation on the hypercube {0,1}^d, i.e., each edge is independently retained with probability p=c/d, where c>1. Let G=(V,E) denote the giant component, so with high probability, |V| is of order 2^d. What is the mixing time of lazy SRW on G? Recently, an upper bound of order d^{11} was proved in https://arxiv.org/pdf/2111.06752.pdf, but no lower bound is known beyond order d log(d).

Contact me