Random Walks on the Symmetric Group, Likelihood Orders, and Involutions

Series: 
Combinatorics Seminar
Friday, September 11, 2015 - 15:00
1 hour (actually 50 minutes)
Location: 
Skiles 005
,  
Georgia Tech
Organizer: 
I will find upper and lower bounds for the mixing time as well as the likelihood order after sufficient time of the following involution walk on the symmetric group. Consider 2n cards on a table. Pair up all the cards. Ignore each pairing with probability $p \geq 1/2$. For any pair not being ignored, pick up the two cards and switch their spots. This walk is generated by involutions with binomially distributed two cycles. The upper bound of $\log_{2/(1+p)}(n)$ will result from spectral analysis using a combination of a series of monotonicity relations on the eigenvalues of the walk and the character polynomial for the representations of the symmetric group. A lower bound of $\log_{1/p}$ differs by a constant factor from the upper bound. This walk was introduced to study a conjecture about a random walk on the unitary group from the information theory of black holes.