What are the odds two uniformly chosen elements of S_n span the whole group (or just the alternating group)? Mathematica experements suggest those odds approach 1 – this might have been proven a long time ago. How likely is it to get the alternating group or something much smaller?
Also, how can you efficiently find the size of the subgroup $\langle a,b\rangle$ in S_n ? My crude tests consists of randomly multiplying the two permutations and seeing how many different elements you get. Maybe there's a more efficient way to generate all the elements spanned by two permutation.
You can generate the whole permutation group using a swap (12) and a shift (12…n). I wonder if all two element generating sets are conjugate to this.
Best Answer
The probability of generation of $A_n$ or $S_n$ by two random permutations is $1 - 1/n - O(1/n^2)$. The $1/n$ term comes from both permutations having the same fixed point. This is a classical result of L. Babai: The probability of generating the symmetric group, Journal of Combinatorial Theory, Series A, 1989. Warning: it uses the classification of finite simple groups.
For asymptotics for general simple groups, see this paper by Liebeck and Shalev, and a recent short survey by Shalev.