2021/04/08 by Ben-Hamou, Anna, Peres, Yuval
#60J10 #FOS: Mathematics #Probability (math.PR)
paper · doi:10.48550/arxiv.2104.03568
Let P be a bistochastic matrix of size n, and let Π be a permutation matrix of size n. In this paper, we are interested in the mixing time of the Markov chain whose transition matrix is given by Q=PΠ. In other words, the chain alternates between random steps governed by P and deterministic steps governed by Π. We show that if the permutation Π is chosen uniformly at random, then under mild assumptions on P, with high probability, the chain Q exhibits cutoff at time (log n)/(h), where h is the entropic rate of P. Moreover, for deterministic permutations, we improve the upper bound on the mixing time obtained by Chatterjee and Diaconis (2020).