Anna Ben-Hamou

Sorbonne University Pierre and Marie Curie


Cutoff for permuted Markov chains


Probability Seminar


29th June 2022, 4:00 pm – 5:00 pm
Online, Zoom


For a given finite Markov chain with uniform stationary distribution, and a given permutation on the state-space, we consider the Markov chain which alternates between random jumps according to the initial chain, and deterministic jumps according to the permutation. In this framework, Chatterjee and Diaconis (2020) showed that when the permutation satisfies some expansion condition with respect to the chain, then the mixing time is logarithmic, and that this expansion condition is satisfied by almost all permutations. We will see that the mixing time can even be characterized much more precisely: for almost all permutations, the permuted chain has cutoff, at a time which only depends on the entropic rate of the initial chain.





Organisers: Benjamin Lees, Jessica Jay

Comments are closed.
css.php