Random walks generated by the Ewens distribution on the symmetric group

2018/11/05 by Alperen Y. Özdemir, Özdemir, Alperen Y.
Computer Science · Mathematics · #05E10 #60C05 #Advanced Combinatorial Mathematics #Bayesian Methods and Mixture Models #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Probability (math.PR)

paper · pdf · doi:10.48550/arxiv.1811.02039

openalex publication_date 2018/11/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

This paper studies Markov chains on the symmetric group S_n where the transition probabilities are given by the Ewens distribution with parameter θ>1. The eigenvalues are identified to be proportional to the content polynomials of partitions. We show that the mixing time is bounded above by a constant depending only on the parameter if θ is fixed. However, if it agrees with the number of permuted elements (θ=n), the sequence of chains has a total variation cutoff at (log n)/(log 2).

Related

• The random (n-k)-cycle to transpositions walk on the symmetric group
• Cutoff Phenomenon and Limiting Profile of a Random Walk on the Symmetric Group
• On random walks and switched random walks on homogeneous spaces
• Mixing times for Markov chains on wreath products and related\n homogeneous spaces
• Mixing times of a Burnside process Markov chain on set partitions