Random generation under the Ewens distribution

Abstract

The Ewens sampling formula with parameter $α$ is the distribution on $S_n$ which gives each $π\in S_n$ weight proportional to $α^{C(π)}$, where $C(π)$ is the number of cycles of $π$. We show that, for any fixed $α$, two Ewens-random permutations generate at least $A_n$ with high probability. More generally we work out how many permutations are needed for $α$ growing with $n$. Roughly speaking, two are needed for $0 \leq α\ll n^{1/2}$, three for $n^{1/2} \ll α\ll n^{2/3}$, etc.

10 pages. Fixed typo