Expected number of urns that are empty
$begingroup$
We have $n$ balls that are numbered $1,...,n$ and are put into $n$
urns also numbered 1 thru n in such way that ball $i$ is equally
likely to go into any of the urns $1,2,...,n$. Find the expected
number of urns that are empty. Also, find the probability that none of
urns are empty.
Attempt
Im confused as to how we place the balls into the urns. What is the convention in such problems? Because for instance, I don't know whether an urn can have at most one ball, or can hold more than one ball. This is my confusion, but my idea is to let $X$ be the number of empty urns and then define
$$ X_i = begin{cases} 1, ; ; ; urn ; i ; empty \ 0, ; ; ; otherwise end{cases}$$
So that $X = sum_{i=1}^n X_i$. Now, since we want $E(X) $ and $E(X)= sum^{n} E(X_i)$, then we just need to care about $E(X_i) = P(X_i=1)$. SO, in other words, the problem reduces to find the probability that the ith urn is empty.
my Assumption: an urn can contain any number of balls
Assuming this, then the sample space is $n^n$ and the number of ways an urn is empty is just $n!$ since to have the ith urn empty all the other $n$ balls must go into remaining $n-1$ urns. Therefore $E(X_i) = frac{n!}{n^n} $ and thus
$$ E(X) = n frac{n!}{n^n} = frac{n!}{n^{n-1} } $$
Now, if we want none of the urn empty, we just have to count in how many ways can all $n$ balls be placed in $n$ urns so that no urn is empty, well this is just $n!$. Threfore
$$ P(no ; urn ; empty) = frac{n!}{n^n} $$
is my approach correct?
probability
asked Nov 28 '18 at 6:07
Jimmy SabaterJimmy Sabater
2,648321
$endgroup$
add a comment |
$begingroup$
We have $n$ balls that are numbered $1,...,n$ and are put into $n$
urns also numbered 1 thru n in such way that ball $i$ is equally
likely to go into any of the urns $1,2,...,n$. Find the expected
number of urns that are empty. Also, find the probability that none of
urns are empty.
Attempt
Im confused as to how we place the balls into the urns. What is the convention in such problems? Because for instance, I don't know whether an urn can have at most one ball, or can hold more than one ball. This is my confusion, but my idea is to let $X$ be the number of empty urns and then define
$$ X_i = begin{cases} 1, ; ; ; urn ; i ; empty \ 0, ; ; ; otherwise end{cases}$$
So that $X = sum_{i=1}^n X_i$. Now, since we want $E(X) $ and $E(X)= sum^{n} E(X_i)$, then we just need to care about $E(X_i) = P(X_i=1)$. SO, in other words, the problem reduces to find the probability that the ith urn is empty.
my Assumption: an urn can contain any number of balls
Assuming this, then the sample space is $n^n$ and the number of ways an urn is empty is just $n!$ since to have the ith urn empty all the other $n$ balls must go into remaining $n-1$ urns. Therefore $E(X_i) = frac{n!}{n^n} $ and thus
$$ E(X) = n frac{n!}{n^n} = frac{n!}{n^{n-1} } $$
Now, if we want none of the urn empty, we just have to count in how many ways can all $n$ balls be placed in $n$ urns so that no urn is empty, well this is just $n!$. Threfore
$$ P(no ; urn ; empty) = frac{n!}{n^n} $$
is my approach correct?
probability
asked Nov 28 '18 at 6:07
Jimmy SabaterJimmy Sabater
2,648321
$endgroup$
$begingroup$
I believe that urns in probability problems usually have infinite capacity $ddotsmile$
$endgroup$
– Lord Shark the Unknown
Nov 28 '18 at 6:12
$begingroup$
I don't get $E(X_i)$ as $n!/n^n$.
$endgroup$
– Lord Shark the Unknown
Nov 28 '18 at 6:13
add a comment |
$begingroup$
We have $n$ balls that are numbered $1,...,n$ and are put into $n$
urns also numbered 1 thru n in such way that ball $i$ is equally
likely to go into any of the urns $1,2,...,n$. Find the expected
number of urns that are empty. Also, find the probability that none of
urns are empty.
Attempt
Im confused as to how we place the balls into the urns. What is the convention in such problems? Because for instance, I don't know whether an urn can have at most one ball, or can hold more than one ball. This is my confusion, but my idea is to let $X$ be the number of empty urns and then define
$$ X_i = begin{cases} 1, ; ; ; urn ; i ; empty \ 0, ; ; ; otherwise end{cases}$$
So that $X = sum_{i=1}^n X_i$. Now, since we want $E(X) $ and $E(X)= sum^{n} E(X_i)$, then we just need to care about $E(X_i) = P(X_i=1)$. SO, in other words, the problem reduces to find the probability that the ith urn is empty.
my Assumption: an urn can contain any number of balls
Assuming this, then the sample space is $n^n$ and the number of ways an urn is empty is just $n!$ since to have the ith urn empty all the other $n$ balls must go into remaining $n-1$ urns. Therefore $E(X_i) = frac{n!}{n^n} $ and thus
$$ E(X) = n frac{n!}{n^n} = frac{n!}{n^{n-1} } $$
Now, if we want none of the urn empty, we just have to count in how many ways can all $n$ balls be placed in $n$ urns so that no urn is empty, well this is just $n!$. Threfore
$$ P(no ; urn ; empty) = frac{n!}{n^n} $$
is my approach correct?
probability
asked Nov 28 '18 at 6:07
Jimmy SabaterJimmy Sabater
2,648321
$endgroup$
We have $n$ balls that are numbered $1,...,n$ and are put into $n$
urns also numbered 1 thru n in such way that ball $i$ is equally
likely to go into any of the urns $1,2,...,n$. Find the expected
number of urns that are empty. Also, find the probability that none of
urns are empty.
Attempt
Im confused as to how we place the balls into the urns. What is the convention in such problems? Because for instance, I don't know whether an urn can have at most one ball, or can hold more than one ball. This is my confusion, but my idea is to let $X$ be the number of empty urns and then define
$$ X_i = begin{cases} 1, ; ; ; urn ; i ; empty \ 0, ; ; ; otherwise end{cases}$$
So that $X = sum_{i=1}^n X_i$. Now, since we want $E(X) $ and $E(X)= sum^{n} E(X_i)$, then we just need to care about $E(X_i) = P(X_i=1)$. SO, in other words, the problem reduces to find the probability that the ith urn is empty.
my Assumption: an urn can contain any number of balls
Assuming this, then the sample space is $n^n$ and the number of ways an urn is empty is just $n!$ since to have the ith urn empty all the other $n$ balls must go into remaining $n-1$ urns. Therefore $E(X_i) = frac{n!}{n^n} $ and thus
$$ E(X) = n frac{n!}{n^n} = frac{n!}{n^{n-1} } $$
Now, if we want none of the urn empty, we just have to count in how many ways can all $n$ balls be placed in $n$ urns so that no urn is empty, well this is just $n!$. Threfore
$$ P(no ; urn ; empty) = frac{n!}{n^n} $$
is my approach correct?
probability
probability
asked Nov 28 '18 at 6:07
Jimmy SabaterJimmy Sabater
2,648321
asked Nov 28 '18 at 6:07
Jimmy SabaterJimmy Sabater
2,648321
asked Nov 28 '18 at 6:07
Jimmy SabaterJimmy Sabater
2,648321
asked Nov 28 '18 at 6:07
Jimmy SabaterJimmy Sabater
2,648321
asked Nov 28 '18 at 6:07
Jimmy SabaterJimmy Sabater
2,648321
2,648321
$begingroup$
I believe that urns in probability problems usually have infinite capacity $ddotsmile$
$endgroup$
– Lord Shark the Unknown
Nov 28 '18 at 6:12
$begingroup$
I don't get $E(X_i)$ as $n!/n^n$.
$endgroup$
– Lord Shark the Unknown
Nov 28 '18 at 6:13
add a comment |
$begingroup$
I believe that urns in probability problems usually have infinite capacity $ddotsmile$
$endgroup$
– Lord Shark the Unknown
Nov 28 '18 at 6:12
$begingroup$
I don't get $E(X_i)$ as $n!/n^n$.
$endgroup$
– Lord Shark the Unknown
Nov 28 '18 at 6:13
$begingroup$
I believe that urns in probability problems usually have infinite capacity $ddotsmile$
$endgroup$
– Lord Shark the Unknown
Nov 28 '18 at 6:12
$begingroup$
I believe that urns in probability problems usually have infinite capacity $ddotsmile$
$endgroup$
– Lord Shark the Unknown
Nov 28 '18 at 6:12
$begingroup$
I don't get $E(X_i)$ as $n!/n^n$.
$endgroup$
– Lord Shark the Unknown
Nov 28 '18 at 6:13
$begingroup$
I don't get $E(X_i)$ as $n!/n^n$.
$endgroup$
– Lord Shark the Unknown
Nov 28 '18 at 6:13
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Standard probability assumptions say that urns have unlimited capacity and/or balls have zero volume (wow!). Your ideas seem to be on the right track, although some of the calculations are off. $P(X_i = 1)$ is the probability that every single ball misses the $i$th bin. Each ball is independent and each is equally likely to land in every bin, so this is just $left(frac{n-1}{n}right)^n$. Then you would apply linearity of expectation in much the same manner as you do above.
The solution for the second problem seems fine.
answered Nov 28 '18 at 6:32
plattyplatty
3,370320
$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%2f3016790%2fexpected-number-of-urns-that-are-empty%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$
Standard probability assumptions say that urns have unlimited capacity and/or balls have zero volume (wow!). Your ideas seem to be on the right track, although some of the calculations are off. $P(X_i = 1)$ is the probability that every single ball misses the $i$th bin. Each ball is independent and each is equally likely to land in every bin, so this is just $left(frac{n-1}{n}right)^n$. Then you would apply linearity of expectation in much the same manner as you do above.
The solution for the second problem seems fine.
answered Nov 28 '18 at 6:32
plattyplatty
3,370320
$endgroup$
add a comment |
$begingroup$
Standard probability assumptions say that urns have unlimited capacity and/or balls have zero volume (wow!). Your ideas seem to be on the right track, although some of the calculations are off. $P(X_i = 1)$ is the probability that every single ball misses the $i$th bin. Each ball is independent and each is equally likely to land in every bin, so this is just $left(frac{n-1}{n}right)^n$. Then you would apply linearity of expectation in much the same manner as you do above.
The solution for the second problem seems fine.
answered Nov 28 '18 at 6:32
plattyplatty
3,370320
$endgroup$
add a comment |
$begingroup$
Standard probability assumptions say that urns have unlimited capacity and/or balls have zero volume (wow!). Your ideas seem to be on the right track, although some of the calculations are off. $P(X_i = 1)$ is the probability that every single ball misses the $i$th bin. Each ball is independent and each is equally likely to land in every bin, so this is just $left(frac{n-1}{n}right)^n$. Then you would apply linearity of expectation in much the same manner as you do above.
The solution for the second problem seems fine.
answered Nov 28 '18 at 6:32
plattyplatty
3,370320
$endgroup$
Standard probability assumptions say that urns have unlimited capacity and/or balls have zero volume (wow!). Your ideas seem to be on the right track, although some of the calculations are off. $P(X_i = 1)$ is the probability that every single ball misses the $i$th bin. Each ball is independent and each is equally likely to land in every bin, so this is just $left(frac{n-1}{n}right)^n$. Then you would apply linearity of expectation in much the same manner as you do above.
The solution for the second problem seems fine.
answered Nov 28 '18 at 6:32
plattyplatty
3,370320
answered Nov 28 '18 at 6:32
plattyplatty
3,370320
answered Nov 28 '18 at 6:32
plattyplatty
3,370320
answered Nov 28 '18 at 6:32
plattyplatty
3,370320
3,370320
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%2f3016790%2fexpected-number-of-urns-that-are-empty%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$
I believe that urns in probability problems usually have infinite capacity $ddotsmile$
$endgroup$
– Lord Shark the Unknown
Nov 28 '18 at 6:12
$begingroup$
I don't get $E(X_i)$ as $n!/n^n$.
$endgroup$
– Lord Shark the Unknown
Nov 28 '18 at 6:13