Random generation under the Ewens distribution

Abstract

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

10 pages. Fixed typo