Cutoff for non-negatively curved Markov chains

By Justin Salez. Journal of the European Mathematical Society (Print), 2021

57 citations recorded by the source corpus.

Discovered in the context of card shuffling by Aldous, Diaconis and Shahshahani, the cutoff phenomenon has since then been established in a variety of Markov chains. However, proving cutoff remains a delicate affair, which requires a 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 Markov chains with non-negative curvature, under a suitably refined product condition. The result applies, in particular, to random walks on abelian Cayley expanders satisfying a mild degree condition, hence in particular to \emph{almost all} abelian Cayley graphs. Our proof relies on a quantitative \emph{entropic concentration principle}, which we believe to lie behind all cutoff phenomena.

Subfields: Mathematical Physics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/78d19231e79e0ee8b85807712fc0d0d98497daef