Analysis and Probability seminar

Abstract: In this talk, I will present results on the mixing time 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, I 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, where h is a constant related to the entropy of the chain. I will show however that in general, the mixing time from an arbitrary starting state can be larger, namely of polylogarithmic order of any degree, while if some reversibility constraints are imposed we recover cutoff uniformly over all starting states. If time allows, I will also present a novel concentration inequality for polynomial functions of a uniform permutation that was developed for the proof and could be of independent interest.