12
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ If $p=0$ then $E=1$, as the identity is always an element of any subgroup. $\endgroup$ – Berci Jun 9 '18 at 15:33
  • 3
    $\begingroup$ 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$. $\endgroup$ – Derek Holt Jun 9 '18 at 17:05
  • $\begingroup$ Sorry I mean the expected size of $A$ is $n!p$. $\endgroup$ – Derek Holt Jun 9 '18 at 17:43
  • 1
    $\begingroup$ What's $\langle A\rangle$ and $|\langle A\rangle|$, btw? $\endgroup$ – Saad Jul 16 '18 at 12:13
  • 1
    $\begingroup$ @Alex $\langle A\rangle$ is the subgroup generated by the set $A$, and $|\langle A\rangle|$ is the order of this subgroup. $\endgroup$ – user1729 Jul 16 '18 at 12:16
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.