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.