A random walk on the symmetric group generated by random involutions

作者：Bernstein Megan^*

来源：Electronic Journal of Probability, 2018, 23(0): 26.

DOI：10.1214/18-EJP140

• mixing-time
• character polynomial
• pre-cutoff
• character theory
• symmetric groups
• random walks
• likelihood order

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 1/2 <= p <= 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.

• 出版日期2018