I have given a group of permutations as a set of generators. I.e. $G=\langle g_1,...,g_k\rangle < S_n$. There are efficient algorithms (using stabilizer-chains and Schreier-Sims algorithm for example) for the following questions (and others)
- determine the order of $G$
- test whether a permutation $g\in S_n$ is in $G$ or not
- generate a random element $g\in G$ (with nearly uniform distribution)
Now I would like to generate a random subgroup of $G$ (again given as a set of generators). The obvious way to do this is to just create a few random elements, but it seems this gives mostly trivial answers: When you select just two random elements from $S_n$, the probability of them generating $S_n$ or $A_n$ is approximately $1-1/n$ (Dixon's theorem). Similar results hold for other groups, i.e.: the chances of generating the whole $G$ with very few random elements are very high.
So the question:
- Is there an algorithm to generate a subgroup of $G$ with more or less uniform distribution?
- What about a random maximal subgroup? (so the algorithm could be iterated to get smaller groups)
Even the case $G=S_n$ would already be interesting to me.