Markov chain mixing times

June 6 to June 10, 2016

at the

American Institute of Mathematics, San Jose, California

organized by

Nathanael Berestycki, Eyal Lubetzky, Roberto I. Oliveira, and Yuval Peres

Original Announcement

This workshop will be devoted to new connections between the topic of Markov chain mixing times and other subareas of modern probability theory. In recent years, techniques from interacting particle systems, maximal inequalities and coalescence and fragmentation have been used in novel and subtle ways, yielding proofs of some old conjectures on the cutoff effect and raising new questions such as the dependence on the initial condition. Our goal will be to make further advances in these directions, with four main focus topics.
  1. Harris representations relate interacting particle systems to space time percolation processes, and have been fundamental in recent proofs of the cutoff effect for the subcritical Ising model in three dimensions (Lubetzky and Sly) and the one-dimensional interchange process (Lacoin). Extending these techniques to more general systems (Potts models, interchange on general graphs) is a major goal for our workshop.
  2. Maximal inequalities are a classical topic in probability. Recently, Basu, Hermon and Peres managed to relate cutoff to concentration of hitting times by using Starr's maximal inequality for revesible chains. Exploring other potential uses of this and related inequalities is another important goal of our workshop.
  3. Coalescence and fragmentation ideas have appeaed in recent papers by Beresticki /Schramm /Zeitouni, Pillai /Smith and others. In particular, Berestycki and Sengul have relied on this to prove that there is cutoff for a broad family of conjugation invariant random walks on the symmetric group. We intend to further investigate coalescence and fragmentation ideas for Markov chain mixing during our workshop.
  4. Sensitivity to initial condition and robustness. Recent papers have shown that the mixing time of a chain and the presence of cutoff may noth depend on the initial state. This is the case e.g. in the giant component of $G(n,p)$ (Berestycki/Lubetzky/Peres/Sly) and high temperature Glauber dynamics (Lubetzky/Sly). This is parallel to the question of robustness of mixing times and cutoff phenomena to bounded changes in the geometry of the underlying graph. We intend to investigate how general this phenomenon may be.

Material from the workshop

A list of participants.

The workshop schedule.

A report on the workshop activities.

A list of open problems.

Papers arising from the workshop:

Cutoff for biased transpositions
by  Megan Bernstein, Nayantara Bhatnagar, Igor Pak
Mixing time of an unaligned Metropolis algorithm on the square
by  Balazs Gerencser
Polynomial mixing of the edge-flip Markov chain for unbiased dyadic tilings
by  Sarah Cannon, David Levin, and Alexandre Stauffer,  Combin. Probab. Comput. 28 (2019), no. 3, 365–387  MR3933781