  The involution walk is the random walk on $S_n$ generated by involutions with
a binomially distributed with parameter $1-p$ number of $2$-cycles. This is a
parallelization of the transposition walk. The involution walk is shown in this
paper to mix for $\frac{1}{2} \leq p \leq 1$ fixed, $n$ sufficiently large in
between $\log_{1/p}(n)$ steps and $\log_{2/(1+p)}(n)$ steps. The paper
introduces a new technique for finding eigenvalues of random walks on the
symmetric group generated by many conjugacy classes using the character
polynomial for the characters of the representations of the symmetric group.
Monotonicity relations used in the bound also give after sufficient time the
likelihood order, the asymptotic order from most likely to least likely
permutation. The walk was introduced to study a conjecture about a random walk
on the unitary group from the information theory of black holes.
