What is $E|langle Arangle|$?
$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 Arangle|$?
The case with $p = 1$ ($E|langle Arangle| = n!$) is quite obvious, however, I do not know, how to deal with the situation when $0 < p < 1$.
Any help will be appreciated.
probability abstract-algebra group-theory permutations expectation
asked Jun 9 '18 at 15:15
Yanior WegYanior Weg
2,54511246
$endgroup$
|
show 2 more comments
$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 Arangle|$?
The case with $p = 1$ ($E|langle Arangle| = n!$) is quite obvious, however, I do not know, how to deal with the situation when $0 < p < 1$.
Any help will be appreciated.
probability abstract-algebra group-theory permutations expectation
asked Jun 9 '18 at 15:15
Yanior WegYanior Weg
2,54511246
$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 Arangle$ and $|langle Arangle|$, btw?
$endgroup$
– Saad
Jul 16 '18 at 12:13
1
$begingroup$
@Alex $langle Arangle$ is the subgroup generated by the set $A$, and $|langle Arangle|$ is the order of this subgroup.
$endgroup$
– user1729
Jul 16 '18 at 12:16
|
show 2 more comments
$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 Arangle|$?
The case with $p = 1$ ($E|langle Arangle| = n!$) is quite obvious, however, I do not know, how to deal with the situation when $0 < p < 1$.
Any help will be appreciated.
probability abstract-algebra group-theory permutations expectation
asked Jun 9 '18 at 15:15
Yanior WegYanior Weg
2,54511246
$endgroup$
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 Arangle|$?
The case with $p = 1$ ($E|langle Arangle| = n!$) is quite obvious, however, I do not know, how to deal with the situation when $0 < p < 1$.
Any help will be appreciated.
probability abstract-algebra group-theory permutations expectation
probability abstract-algebra group-theory permutations expectation
asked Jun 9 '18 at 15:15
Yanior WegYanior Weg
2,54511246
asked Jun 9 '18 at 15:15
Yanior WegYanior Weg
2,54511246
edited Jul 16 '18 at 11:23
Yanior Weg
asked Jun 9 '18 at 15:15
Yanior WegYanior Weg
2,54511246
asked Jun 9 '18 at 15:15
Yanior WegYanior Weg
2,54511246
asked Jun 9 '18 at 15:15
Yanior WegYanior Weg
2,54511246
2,54511246
$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 Arangle$ and $|langle Arangle|$, btw?
$endgroup$
– Saad
Jul 16 '18 at 12:13
1
$begingroup$
@Alex $langle Arangle$ is the subgroup generated by the set $A$, and $|langle Arangle|$ is the order of this subgroup.
$endgroup$
– user1729
Jul 16 '18 at 12:16
|
show 2 more comments
$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 Arangle$ and $|langle Arangle|$, btw?
$endgroup$
– Saad
Jul 16 '18 at 12:13
1
$begingroup$
@Alex $langle Arangle$ is the subgroup generated by the set $A$, and $|langle Arangle|$ is the order of this subgroup.
$endgroup$
– user1729
Jul 16 '18 at 12:16
$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
$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
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$
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
$begingroup$
Sorry I mean the expected size of $A$ is $n!p$.
$endgroup$
– Derek Holt
Jun 9 '18 at 17:43
1
1
$begingroup$
What's $langle Arangle$ and $|langle Arangle|$, btw?
$endgroup$
– Saad
Jul 16 '18 at 12:13
$begingroup$
What's $langle Arangle$ and $|langle Arangle|$, btw?
$endgroup$
– Saad
Jul 16 '18 at 12:13
1
1
$begingroup$
@Alex $langle Arangle$ is the subgroup generated by the set $A$, and $|langle Arangle|$ is the order of this subgroup.
$endgroup$
– user1729
Jul 16 '18 at 12:16
$begingroup$
@Alex $langle Arangle$ is the subgroup generated by the set $A$, and $|langle Arangle|$ is the order of this subgroup.
$endgroup$
– user1729
Jul 16 '18 at 12:16
|
show 2 more comments
1 Answer
1
active
oldest
votes
$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).
However, one can prove an interesting fact about the asymptotic behavior of $E|langle Arangle|$ (that also works not only for your case, but for my generalization too). That is $lim_{|G| to infty} frac{E|langle Arangle|}{|G|} = 1$. That is due to the fact, that $|G| geq E|langle Arangle| geq |G| - |G|^3 (1 - p)^{frac{|G|}{2}}$ (that follows from the inequalities $|H| < frac{|G|}{2}$ for any proper subgroup of $G$, $|{H leq G}| leq |G|$ and $|mu(H, K)| leq 1$). Now that means, that $1 geq frac{E|langle Arangle|}{|G|} geq 1 - |G|^2(1 - p)^{frac{|G|}{2}}$. This, combined with the fact, that $lim_{n to infty} n^2(1 - p)^{frac{n}{2}} = 0$, gives us the statement we need.
answered Jan 25 at 21:05
Yanior WegYanior Weg
2,54511246
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2813655%2fwhat-is-e-langle-a-rangle%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$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).
However, one can prove an interesting fact about the asymptotic behavior of $E|langle Arangle|$ (that also works not only for your case, but for my generalization too). That is $lim_{|G| to infty} frac{E|langle Arangle|}{|G|} = 1$. That is due to the fact, that $|G| geq E|langle Arangle| geq |G| - |G|^3 (1 - p)^{frac{|G|}{2}}$ (that follows from the inequalities $|H| < frac{|G|}{2}$ for any proper subgroup of $G$, $|{H leq G}| leq |G|$ and $|mu(H, K)| leq 1$). Now that means, that $1 geq frac{E|langle Arangle|}{|G|} geq 1 - |G|^2(1 - p)^{frac{|G|}{2}}$. This, combined with the fact, that $lim_{n to infty} n^2(1 - p)^{frac{n}{2}} = 0$, gives us the statement we need.
answered Jan 25 at 21:05
Yanior WegYanior Weg
2,54511246
$endgroup$
add a comment |
$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).
However, one can prove an interesting fact about the asymptotic behavior of $E|langle Arangle|$ (that also works not only for your case, but for my generalization too). That is $lim_{|G| to infty} frac{E|langle Arangle|}{|G|} = 1$. That is due to the fact, that $|G| geq E|langle Arangle| geq |G| - |G|^3 (1 - p)^{frac{|G|}{2}}$ (that follows from the inequalities $|H| < frac{|G|}{2}$ for any proper subgroup of $G$, $|{H leq G}| leq |G|$ and $|mu(H, K)| leq 1$). Now that means, that $1 geq frac{E|langle Arangle|}{|G|} geq 1 - |G|^2(1 - p)^{frac{|G|}{2}}$. This, combined with the fact, that $lim_{n to infty} n^2(1 - p)^{frac{n}{2}} = 0$, gives us the statement we need.
answered Jan 25 at 21:05
Yanior WegYanior Weg
2,54511246
$endgroup$
add a comment |
$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).
However, one can prove an interesting fact about the asymptotic behavior of $E|langle Arangle|$ (that also works not only for your case, but for my generalization too). That is $lim_{|G| to infty} frac{E|langle Arangle|}{|G|} = 1$. That is due to the fact, that $|G| geq E|langle Arangle| geq |G| - |G|^3 (1 - p)^{frac{|G|}{2}}$ (that follows from the inequalities $|H| < frac{|G|}{2}$ for any proper subgroup of $G$, $|{H leq G}| leq |G|$ and $|mu(H, K)| leq 1$). Now that means, that $1 geq frac{E|langle Arangle|}{|G|} geq 1 - |G|^2(1 - p)^{frac{|G|}{2}}$. This, combined with the fact, that $lim_{n to infty} n^2(1 - p)^{frac{n}{2}} = 0$, gives us the statement we need.
answered Jan 25 at 21:05
Yanior WegYanior Weg
2,54511246
$endgroup$
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).
However, one can prove an interesting fact about the asymptotic behavior of $E|langle Arangle|$ (that also works not only for your case, but for my generalization too). That is $lim_{|G| to infty} frac{E|langle Arangle|}{|G|} = 1$. That is due to the fact, that $|G| geq E|langle Arangle| geq |G| - |G|^3 (1 - p)^{frac{|G|}{2}}$ (that follows from the inequalities $|H| < frac{|G|}{2}$ for any proper subgroup of $G$, $|{H leq G}| leq |G|$ and $|mu(H, K)| leq 1$). Now that means, that $1 geq frac{E|langle Arangle|}{|G|} geq 1 - |G|^2(1 - p)^{frac{|G|}{2}}$. This, combined with the fact, that $lim_{n to infty} n^2(1 - p)^{frac{n}{2}} = 0$, gives us the statement we need.
answered Jan 25 at 21:05
Yanior WegYanior Weg
2,54511246
edited Jan 25 at 22:34
answered Jan 25 at 21:05
Yanior WegYanior Weg
2,54511246
answered Jan 25 at 21:05
Yanior WegYanior Weg
2,54511246
answered Jan 25 at 21:05
Yanior WegYanior Weg
2,54511246
2,54511246
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2813655%2fwhat-is-e-langle-a-rangle%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$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 Arangle$ and $|langle Arangle|$, btw?
$endgroup$
– Saad
Jul 16 '18 at 12:13
1
$begingroup$
@Alex $langle Arangle$ is the subgroup generated by the set $A$, and $|langle Arangle|$ is the order of this subgroup.
$endgroup$
– user1729
Jul 16 '18 at 12:16