# 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.

• If $p=0$ then $E=1$, as the identity is always an element of any subgroup. – Berci Jun 9 '18 at 15:33
• The expected size of $A$ is $n!/p$. If this is at least $2$, then the probability that $\langle A \rangle = A_n$ or $S_n$ approaches $1$ as $n \to \infty$. – Derek Holt Jun 9 '18 at 17:05
• Sorry I mean the expected size of $A$ is $n!p$. – Derek Holt Jun 9 '18 at 17:43
• What's $\langle A\rangle$ and $|\langle A\rangle|$, btw? – Saad Jul 16 '18 at 12:13
• @Alex $\langle A\rangle$ is the subgroup generated by the set $A$, and $|\langle A\rangle|$ is the order of this subgroup. – user1729 Jul 16 '18 at 12:16

## 2 Answers

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!.$$

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).