  Let $P$ be a bistochastic matrix of size $n$, and let $\Pi$ 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\Pi$. In other words, the
chain alternates between random steps governed by $P$ and deterministic steps
governed by $\Pi$. We show that if the permutation $\Pi$ is chosen uniformly at
random, then under mild assumptions on $P$, with high probability, the chain
$Q$ exhibits cutoff at time $\frac{\log n}{\mathbf{h}}$, where $\mathbf{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).
