  We consider a random bistochastic matrix of size $n$ of the form $M Q$ where
$M$ is a uniformly distributed permutation matrix and $Q$ is a given
bistochastic matrix. Under mild sparsity and regularity assumptions on $Q$, we
prove that the second largest eigenvalue of $MQ$ is essentially bounded by the
normalized Hilbert-Schmidt norm of $Q$ when $n$ grows large. We apply this
result to random walks on random regular digraphs and to shuffle-and-fold maps
of the unit interval popularized in fluid mixing protocols.
