What is $E|\langle A\rangle|$?

Suppose $A$ is a random subset of $S_n$, such that each element of $S_n$ independently belongs to $A$ with probability p. What is the expectation of $|\langle A\rangle|$?

The case with $p = 1$ ($E|\langle A\rangle| = n!$) is quite obvious, however, I do not know, how to deal with the situation when $0 < p < 1$.

Any help will be appreciated.

Solution 1:

The probability that two random permutations generate $S_n$ is $1 - o(1)$; see for example this question. Hence as long as $p = \omega(1/n!)$, the probability that $A$ generates $S_n$ is $1 - o(1)$, and in that case the expectation of $|\langle A \rangle|$ is $(1-o(1))n!$. In more detail, we have $$ \begin{align*} E|\langle A \rangle| &= \Pr[|A|=0] + \exp \Theta(\sqrt{n/\log n}) \Pr[|A|=1] + (1-o(1))n! \Pr[|A| \geq 2] \\ &= (1-p)^{n!} + \exp \Theta(\sqrt{n/\log n}) n!(1-p)^{n!-1}p + (1-o(1))n! (1 - (1-p)^{n!} - n!(1-p)^{n!-1}p). \end{align*} $$ using the formula for the expected order of a permutation, due to Goh and Schmutz. When $p = c/n!$ for constant $c$, this gives $$ E|\langle A \rangle| \approx e^{-c} + ce^{-c} \exp \Theta(\sqrt{n/\log n}) + (1-e^{-c} - ce^{-c})n!. $$

Solution 2:

Suppose $A$ is a random subset of a finite group $G$, such that each element of $A$ independently belongs to $G$ with probability $p$ (in your case $G = S_n$). One can see that $\forall H \leq G (P(A \subset H) = (1 - p)^{|G| - |H|}$. It is also true, that $P(A \subset H) = \Sigma_{K \leq H} P(\langle A \rangle = K)$. Thus, $P(\langle A \rangle = H) = \Sigma_{K \leq H} \mu(H, K)P(A \subset K) = \Sigma_{K \leq H} \mu(H, K)(1 - p)^{|G| - |K|}$, where $\mu$ is the Moebius function for subgroup lattice of $G$. Thus we have the formula: $$E|\langle A \rangle| = \Sigma_{H \leq G} \Sigma_{K \leq H} |H|\mu(H, K)(1 - p)^{|G| - |K|}$$

That is one of the possible forms of answer, despite it is quite hard to anyhow simplify it, as one must know the structure of subgroup lattice of $G$ to calculate the Moebius function (In your case it is especially hard as the subgroup lattice of $S_n$ is not well described).