Proceedings of the 28-th International Conference on Formal Power Series and Algebraic Combinatorics
4-8 Jul 2016 Vancouver, British Columbia (Canada)
The Mixing Time for a Random Walk on the Symmetric Group Generated by Random Involutions
Megan Bernstein  1  
1 : College of Computing  (GATECH)  -  Website
801 Atlantic Drive, NW, Atlanta GA 30332-0280, USA -  États-Unis

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 p1fixed,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. 

  • Poster
Online user: 1