Random walks generated by Ewens distribution on the symmetric group

Alperen Y. Özdemir

Published 2018-11-05Version 1

This paper studies Markov chains on the symmetric group $S_n$ where the transition probabilities are given by Ewens distribution with parameter $\theta>0$. The eigenvalues are identified to be content polynomials of partitions divided by n$th$ rising factorial of $\theta.$ The mixing time analysis is carried out for two cases: If $\theta$ is a constant integer, the chain is fast enough that the mixing time does not depend on $n.$ If $\theta=n$, the chain exhibits a total variation cutoff at $\frac{\log n}{\log 2}$ steps.