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.
 A: 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). 
A: 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!.
$$
