Cutoff for permuted Markov chains

Abstract: Let

P

be a bistochastic matrix of size

n

, and let

P i

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 P i

. In other words, the chain alternates between random steps governed by

P

and deterministic steps governed by

P i

. We show that if the permutation

P i

is chosen uniformly at random, then under mild assumptions on

P

, with high probability, the chain

Q

exhibits cutoff at time

f r a c l o g n m a t h b f h

, where

m a t h b f 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).

This page was built for publication: Cutoff for permuted Markov chains