Cutoff for non-negatively curved Markov chains

Abstract

Discovered by Aldous, Diaconis and Shahshahani in the context of card shuffling, the cutoff phenomenon has since then been established for a variety of Markov chains. 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 present paper, we make a step in this direction by establishing cutoff for all Markov chains with non-negative curvature, under a suitably refined product condition. The result applies, in particular, to the random walk on abelian Cayley expanders satisfying a mild degree assumption, hence to the random walk on almost all abelian Cayley graphs. Our proof relies on a quantitative entropic concentration principle, which we believe to lie behind all cutoff phenomena.