The random (n-k)-cycle to transpositions walk on the symmetric group

2017/07/06 by Alperen Y. Özdemir, Özdemir, Alperen Y.
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #60C05 #Bayesian Methods and Mixture Models #FOS: Mathematics #Genome Rearrangement Algorithms #Probability (math.PR) #Stochastic processes and statistical mechanics

paper · pdf · doi:10.48550/arxiv.1707.01604

openalex publication_date 2017/07/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We study the rate of convergence of the Markov chain on S_n which starts with a random (n-k)-cycle for a fixed k ≥ 1, followed by random transpositions. The convergence to the stationary distribution turns out to be of order n. We show that after cn + (ln k)/(2)n steps for c>0, the law of the Markov chain is close to the uniform distribution. The character of the defining representation is used as test function to obtain a lower bound for the total variation distance. We identify the asymptotic distribution of the test function given the law of the Markov chain for the (n-1)-cycle case. The upper bound relies on estimates for the difference of normalized characters.

Related

• Likelihood Orders for some Random Walks on the Symmetric Group
• A strong stationary time for random transpositions
• Random walks generated by the Ewens distribution on the symmetric group
• A random walk on the symmetric group generated by random involutions
• Representation theory and cycle statistics for random walks on the symmetric group