Anna Ben-Hamou

Cutoff for permuted Markov chains

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.