Cutoff for non-negatively curved Markov chains

  • Justin Salez

    Université Paris-Dauphine and PSL, Paris, France
Cutoff for non-negatively curved Markov chains cover
Download PDF

This article is published open access under our Subscribe to Open model.

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.

Cite this article

Justin Salez, Cutoff for non-negatively curved Markov chains. J. Eur. Math. Soc. 26 (2024), no. 11, pp. 4375–4392

DOI 10.4171/JEMS/1348