Ewens sampling and invariable generation

DOI10.1017/S096354831800007XMaRDI QIDQ4554773zbMATH OpenOpenAlexFDO

Authors Gerandy Brito, Christopher F. Fowler, Matthew Junge, Avi Levy

Publication date 9 November 2018

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1610.04212

Mathematics Subject Classification ID

Randomized algorithms (68W20) Symbolic computation and algebraic computation (68W30) Analysis of algorithms (68W40) Combinatorial probability (60C05)

Abstract: We study the number of random permutations needed to invariably generate the symmetric group, $S_n$, when the distribution of cycle counts has the strong $alpha$-logarithmic property. The canonical example is the Ewens sampling formula, for which the number of $k$-cycles relates to a conditioned Poisson random variable with mean $alpha/k$. The special case $alpha=1$ corresponds to uniformly random permutations, for which it was recently shown that exactly four are needed. For strong $alpha$-logarithmic measures, and almost every $alpha$, we show that precisely $leftlceil(1-alphalog2{)}^{-1}ightceil$ permutations are needed to invariably generate $S_n$. A corollary is that for many other probability measures on $S_n$ no bounded number of permutations will invariably generate $S_n$ with positive probability. Along the way we generalize classic theorems of ErdH{o}s, Tehran, Pyber, Luczak and Bovey to permutations obtained from the Ewens sampling formula.

Recommendations

• Invariable generation of the symmetric group
• On Random Generation of the Symmetric Group
• Random sets which invariably generate the symmetric group
• On statistics of permutations chosen from the Ewens distribution
• scientific article; zbMATH DE number 1047740

Cites work

• scientific article; zbMATH DE number 3523640 (Why is no real title available?)
• Cycle structure of random permutations with cycle weights
• Exploiting the Feller coupling for the Ewens sampling formula
• Fast recognition of alternating and symmetric Galois groups
• Fixed points and cycle structure of random permutations
• Four random permutations conjugated by an adversary generate \(\mathcal{S}_{n}\) with high probability
• Independent process approximations for random combinatorial structures
• Invariable generation of the symmetric group
• Limits of logarithmic combinatorial structures.
• NON-NULL RANKING MODELS. I
• On Random Generation of the Symmetric Group
• On polynomials with symmetric Galois group which are easy to compute
• On some problems of a statistical group-theory. II
• On the Efficiency of a Polynomial Irreducibility Test
• On the cycle structure of Mallows permutations
• On the minimal degree of a primitive permutation group
• On the order of uniprimitive permutation groups
• On the set of divisors of an integer
• Permutations Fixing ak-set
• Poisson process approximations for the Ewens sampling formula
• Random permutations with cycle weights
• Random sets which invariably generate the symmetric group
• Rejoinder: The ubiquitous Ewens sampling formula
• The Probability that some Power of a Permutation has Small Degree
• The cycle structure of random permutations
• The fundamental limit theorems in probability
• The sampling theory of selectively neutral alleles
• The ubiquitous Ewens sampling formula

Cited in

(2)

• How to Generate and Use Universal Samplers
• Minimal invariable generating sets

This page was built for publication: Ewens sampling and invariable generation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4554773)