Title: “Speeding up Markov chains with random permutations”

Abstract: Markov chains are widely used to sample approximately from a given distribution. Some chains however might take a very long time to mix. This raises the question of how to speed up a chain to make it mix faster: can one design a simple perturbation of the chain which ensures fast mixing? In this talk, we will be interested in the following perturbation: take a bijection on the state space and consider the chain which alternates between steps governed the original chain, and deterministic steps governed by the bijection. We will first show that if the bijection satisfies some expansion condition with respect to the original chain, then the mixing time of the permuted chain is logarithmic in the size of the state space, whatever the initial chain, provided it satisfies some mild assumptions. Then, we will see that almost all bijections do the job: if the bijection is chosen uniformly at random, then the permuted chain has cutoff at a time which is characterised by the entropy of the initial chain. This is a joint work with Yuval Peres.