Bastien Dubail: Cutoff for mixtures of permuted Markov chains

Abstract:

In this talk, I will investigate the mixing time of a new model of a Markov chain in random environment defined as a mixture of a deterministic chain and a chain whose state space has been permuted uniformly at random. Under mild assumptions on the base Markov chains, we show the occurrence of a cutoff phenomenon at entropic time: provided the chain is started from a typical state the mixing time will with high probability scale as \(\log n/h\)as the number of states \(n\) goes to infinity, while \(h\) is a constant related to the entropy of the chain. In general, the mixing time from an arbitrary starting state can be larger, namely of polyologarithmic order of any degree. However if some reversibility constraints are imposed it is possible to prove the cutoff at entropic time for all starting states simultaneously. This generalizes a result of Hermon, Sly and Sousi, who proved the cutoff phenomenon for the simple random walk on a graph with an added uniform matching. I will also present a novel concentration result for uniform permutations that was developped for this work but could be of independent interest.