The involution walk is a random walk on the symmetric group generated by involutions with a number of 2-cycles sampled from the binomial distribution with parameter p. This is a parallelization of the lazy transposition walk onthesymmetricgroup.Theinvolutionwalkisshowninthispapertomixfor1 ≤p≤1fixed,nsufficientlylarge 2 in between log1/p(n) steps and log2/(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. This is especially efficient at calculating the large eigenvalues. The smaller eigenvalues are handled by developing monotonicity relations that also give after sufficient time the likelihood order, the order from most likely to least likely state. The walk was introduced to study a conjecture about a random walk on the unitary group from the information theory of back holes.
Discrete Mathematics & Theoretical Computer Science