An entropic interpretation of the cutoff phenomenon for finite Markov chains

Abstract: The cutoff phenomenon is a sharp phase transition in the convergence to equilibrium of certain Markov chains. Discovered by Aldous, Diaconis and Shahshahani in the context of card shuffling, it has since then been established on a variety of examples. However, proving cutoff remains a delicate affair, which requires a very detailed knowledge of the chain. Identifying the general mechanisms underlying this phase transition, without having to pinpoint its precise location, remains one of the most fundamental open problems in the area of mixing times.

In the first part of the lecture, I will provide a self-contained introduction to this beautiful question, and present some classical examples. In the second part, I will discuss a recent interpretation of the cutoff phenomenon in terms of concentration of entropy, and show how this can be used to deduce cutoff for a broad class of Markov chains with non-negative curvature, including random walks on abelian Cayley expanders.

probability

Audience: advanced learners

Bangalore Probability Seminar

Series comments: The link to zoom meeting can be found on the seminar's google calendar - www.isibang.ac.in/~d.yogesh/BPS.html