Random generation under the Ewens distribution

2018/08/27 by Sean Eberhard, Eberhard, Sean
Computer Science · Mathematics · #20B30 #Algorithms and Data Compression #Bayesian Methods and Mixture Models #FOS: Mathematics #Group Theory (math.GR) #Probability (math.PR) #Statistical Distribution Estimation and Applications

paper · pdf · doi:10.48550/arxiv.1808.08892

openalex publication_date 2018/08/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The Ewens sampling formula with parameter α is the distribution on S_n which gives each π∈ 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 ≤ α≪ n^1/2, three for n^1/2 ≪ α≪ n^2/3, etc.

Related

• Ewens sampling and invariable generation
• Random derangements and the Ewens Sampling Formula
• A central limit theorem for a generalization of the Ewens measure to random tuples of commuting permutations
• Involution factorizations of Ewens random permutations
• On statistics of permutations chosen from the Ewens distribution