Cutoff for mixtures of permuted Markov chains: Reversible case

We investigate the mixing properties of a model of reversible Markov chains in random environment, which notably contains the simple random walk on the superposition of a deterministic graph and a second graph whose vertex set has been permuted uniformly at random. It generalizes in particular a result of Hermon, Sly and Sousi, who proved the cutoff phenomenon at entropic time for the simple random walk on a graph with an added uniform matching. Under mild assumptions on the base Markov chains, we prove that with high probability the resulting chain exhibits the cutoff phenomenon at entropic time logn/h, h being some constant related to the entropy of the chain. We note that the results presented here are the consequence of a work conducted for a more general model that does not assume reversibility, which will be the object of a companion paper. Thus an important contribution of this paper is in the arguments we propose, as most of them do not require reversibility. Among these, we establish a novel concentration result for “low-degree” functions on the symmetric group, established specifically for our purpose but which could be of independent interest.