If I randomly (uniformly) distribute n balls into k bags, what is the distribution of the number of empty bags? The Next CEO of Stack OverflowGeneralised inclusion-exclusion principleHelp with combinations problem?Distribution of $r$ balls into $n$ cells leaving none of the cells empty.Distribute n balls across m bags when bags are not empty to get the same sizesProbability of balls drawn with replacementDistribution of balls in different boxes and each containing a different number of ballsPopcorn ProbabilityWhat is the probability that both balls are white?Suppose $n$ balls are distributed at random into $r$ boxes. Let $S$ be the numSetting up the probability distribution of Y = the number of empty bowlsYou are given K different boxes and N different balls? In how many ways can one distribute the balls so that no box is empty?
How do we know the LHC results are robust?
Grabbing quick drinks
Should I tutor a student who I know has cheated on their homework?
Why were Madagascar and New Zealand discovered so late?
Fastest way to shutdown Ubuntu Mate 18.10
Why doesn't a table tennis ball float on the surface? How do we calculate buoyancy here?
Is a stroke of luck acceptable after a series of unfavorable events?
Inappropriate reference requests from Journal reviewers
How do scammers retract money, while you can’t?
How to be diplomatic in refusing to write code that breaches the privacy of our users
Which organization defines CJK Unified Ideographs?
How should I support this large drywall patch?
Is it okay to store user locations?
I believe this to be a fraud - hired, then asked to cash check and send cash as Bitcoin
How do I solve this limit?
WOW air has ceased operation, can I get my tickets refunded?
What do "high sea" and "carry" mean in this sentence?
What is the purpose of the Evocation wizard's Potent Cantrip feature?
Whats the best way to handle refactoring a big file?
How to make a software documentation "officially" citable?
Term for the "extreme-extension" version of a straw man fallacy?
How to write papers efficiently when English isn't my first language?
Does it take more energy to get to Venus or to Mars?
Only print output after finding pattern
If I randomly (uniformly) distribute n balls into k bags, what is the distribution of the number of empty bags?
The Next CEO of Stack OverflowGeneralised inclusion-exclusion principleHelp with combinations problem?Distribution of $r$ balls into $n$ cells leaving none of the cells empty.Distribute n balls across m bags when bags are not empty to get the same sizesProbability of balls drawn with replacementDistribution of balls in different boxes and each containing a different number of ballsPopcorn ProbabilityWhat is the probability that both balls are white?Suppose $n$ balls are distributed at random into $r$ boxes. Let $S$ be the numSetting up the probability distribution of Y = the number of empty bowlsYou are given K different boxes and N different balls? In how many ways can one distribute the balls so that no box is empty?
$begingroup$
If I uniformly distribute $n$ balls into $k$ bags, I am trying to work out the distribution of the number of bags which are empty.
Now I had thought that I could use that each bag has $textBinomial(n, frac1k)$ balls and use this but these distributions are not independent so this doesn't work.
Any help will be greatly appreciated.
probability combinatorics probability-theory probability-distributions
edited yesterday
Yanior Weg
2,78211346
asked Mar 25 at 11:31
Alexander ModellAlexander Modell
82
New contributor
Alexander Modell is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
$begingroup$
If I uniformly distribute $n$ balls into $k$ bags, I am trying to work out the distribution of the number of bags which are empty.
Now I had thought that I could use that each bag has $textBinomial(n, frac1k)$ balls and use this but these distributions are not independent so this doesn't work.
Any help will be greatly appreciated.
probability combinatorics probability-theory probability-distributions
edited yesterday
Yanior Weg
2,78211346
asked Mar 25 at 11:31
Alexander ModellAlexander Modell
82
New contributor
Alexander Modell is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
$begingroup$
How many ways are there of choosing two empty bags? How many ways are there of distributing the balls among the remaining bags, so that at least one ball is in each bag?
$endgroup$
– Peter Shor
Mar 25 at 11:38
add a comment |
$begingroup$
If I uniformly distribute $n$ balls into $k$ bags, I am trying to work out the distribution of the number of bags which are empty.
Now I had thought that I could use that each bag has $textBinomial(n, frac1k)$ balls and use this but these distributions are not independent so this doesn't work.
Any help will be greatly appreciated.
probability combinatorics probability-theory probability-distributions
edited yesterday
Yanior Weg
2,78211346
asked Mar 25 at 11:31
Alexander ModellAlexander Modell
82
New contributor
Alexander Modell is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
If I uniformly distribute $n$ balls into $k$ bags, I am trying to work out the distribution of the number of bags which are empty.
Now I had thought that I could use that each bag has $textBinomial(n, frac1k)$ balls and use this but these distributions are not independent so this doesn't work.
Any help will be greatly appreciated.
probability combinatorics probability-theory probability-distributions
probability combinatorics probability-theory probability-distributions
edited yesterday
Yanior Weg
2,78211346
asked Mar 25 at 11:31
Alexander ModellAlexander Modell
82
New contributor
Alexander Modell is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited yesterday
Yanior Weg
2,78211346
asked Mar 25 at 11:31
Alexander ModellAlexander Modell
82
New contributor
Alexander Modell is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited yesterday
Yanior Weg
2,78211346
edited yesterday
Yanior Weg
2,78211346
edited yesterday
Yanior Weg
2,78211346
2,78211346
asked Mar 25 at 11:31
Alexander ModellAlexander Modell
82
New contributor
Alexander Modell is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked Mar 25 at 11:31
Alexander ModellAlexander Modell
82
asked Mar 25 at 11:31
Alexander ModellAlexander Modell
82
82
New contributor
Alexander Modell is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Alexander Modell is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Alexander Modell is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$begingroup$
How many ways are there of choosing two empty bags? How many ways are there of distributing the balls among the remaining bags, so that at least one ball is in each bag?
$endgroup$
– Peter Shor
Mar 25 at 11:38
add a comment |
$begingroup$
How many ways are there of choosing two empty bags? How many ways are there of distributing the balls among the remaining bags, so that at least one ball is in each bag?
$endgroup$
– Peter Shor
Mar 25 at 11:38
$begingroup$
How many ways are there of choosing two empty bags? How many ways are there of distributing the balls among the remaining bags, so that at least one ball is in each bag?
$endgroup$
– Peter Shor
Mar 25 at 11:38
$begingroup$
How many ways are there of choosing two empty bags? How many ways are there of distributing the balls among the remaining bags, so that at least one ball is in each bag?
$endgroup$
– Peter Shor
Mar 25 at 11:38
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Define $P_k^n(m)$ as the probability, that there will be $m$ empty bags after $n$ balls were thrown into $k$ bags.
Now, suppose, you have $k$ bags total and have already thrown $n - 1$ balls, and it resulted in $m$ bags remaining empty. Then, after the next ball is thrown, $m$ bags remain empty with probability $frack - mk$ and the number of empty bags will become $m - 1$ is $fracmk$. So we have the following recurrence, that is sufficient to define all probabilities you search:
$$P_k^n(m) = frack - mkP_k^n - 1(m) + fracmkP_k^n-1(m + 1)$$
$$P_k^0(k) = 1$$
$$P_k^0(m) = 0, text if m neq k$$
answered Mar 25 at 17:28
Yanior WegYanior Weg
2,78211346
$endgroup$
add a comment |
$begingroup$
It is also possible to get the following "closed form" for this distribution:
$$
bbox[#EEE,6px,border:1.5px solid black]mathbb Pbig(text# empty bags =mbig)=sum_i=m^k(-1)^i-mbinomimbinomkileft(1-iover kright)^n.
$$
This follows from the generalized inclusion exclusion principle. See Generalised inclusion-exclusion principle.
answered yesterday
Mike EarnestMike Earnest
26.1k22151
$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
);
);
Alexander Modell is a new contributor. Be nice, and check out our Code of Conduct.
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%2f3161661%2fif-i-randomly-uniformly-distribute-n-balls-into-k-bags-what-is-the-distributi%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Define $P_k^n(m)$ as the probability, that there will be $m$ empty bags after $n$ balls were thrown into $k$ bags.
Now, suppose, you have $k$ bags total and have already thrown $n - 1$ balls, and it resulted in $m$ bags remaining empty. Then, after the next ball is thrown, $m$ bags remain empty with probability $frack - mk$ and the number of empty bags will become $m - 1$ is $fracmk$. So we have the following recurrence, that is sufficient to define all probabilities you search:
$$P_k^n(m) = frack - mkP_k^n - 1(m) + fracmkP_k^n-1(m + 1)$$
$$P_k^0(k) = 1$$
$$P_k^0(m) = 0, text if m neq k$$
answered Mar 25 at 17:28
Yanior WegYanior Weg
2,78211346
$endgroup$
add a comment |
$begingroup$
Define $P_k^n(m)$ as the probability, that there will be $m$ empty bags after $n$ balls were thrown into $k$ bags.
Now, suppose, you have $k$ bags total and have already thrown $n - 1$ balls, and it resulted in $m$ bags remaining empty. Then, after the next ball is thrown, $m$ bags remain empty with probability $frack - mk$ and the number of empty bags will become $m - 1$ is $fracmk$. So we have the following recurrence, that is sufficient to define all probabilities you search:
$$P_k^n(m) = frack - mkP_k^n - 1(m) + fracmkP_k^n-1(m + 1)$$
$$P_k^0(k) = 1$$
$$P_k^0(m) = 0, text if m neq k$$
answered Mar 25 at 17:28
Yanior WegYanior Weg
2,78211346
$endgroup$
add a comment |
$begingroup$
Define $P_k^n(m)$ as the probability, that there will be $m$ empty bags after $n$ balls were thrown into $k$ bags.
Now, suppose, you have $k$ bags total and have already thrown $n - 1$ balls, and it resulted in $m$ bags remaining empty. Then, after the next ball is thrown, $m$ bags remain empty with probability $frack - mk$ and the number of empty bags will become $m - 1$ is $fracmk$. So we have the following recurrence, that is sufficient to define all probabilities you search:
$$P_k^n(m) = frack - mkP_k^n - 1(m) + fracmkP_k^n-1(m + 1)$$
$$P_k^0(k) = 1$$
$$P_k^0(m) = 0, text if m neq k$$
answered Mar 25 at 17:28
Yanior WegYanior Weg
2,78211346
$endgroup$
Define $P_k^n(m)$ as the probability, that there will be $m$ empty bags after $n$ balls were thrown into $k$ bags.
Now, suppose, you have $k$ bags total and have already thrown $n - 1$ balls, and it resulted in $m$ bags remaining empty. Then, after the next ball is thrown, $m$ bags remain empty with probability $frack - mk$ and the number of empty bags will become $m - 1$ is $fracmk$. So we have the following recurrence, that is sufficient to define all probabilities you search:
$$P_k^n(m) = frack - mkP_k^n - 1(m) + fracmkP_k^n-1(m + 1)$$
$$P_k^0(k) = 1$$
$$P_k^0(m) = 0, text if m neq k$$
answered Mar 25 at 17:28
Yanior WegYanior Weg
2,78211346
answered Mar 25 at 17:28
Yanior WegYanior Weg
2,78211346
answered Mar 25 at 17:28
Yanior WegYanior Weg
2,78211346
answered Mar 25 at 17:28
Yanior WegYanior Weg
2,78211346
2,78211346
add a comment |
add a comment |
$begingroup$
It is also possible to get the following "closed form" for this distribution:
$$
bbox[#EEE,6px,border:1.5px solid black]mathbb Pbig(text# empty bags =mbig)=sum_i=m^k(-1)^i-mbinomimbinomkileft(1-iover kright)^n.
$$
This follows from the generalized inclusion exclusion principle. See Generalised inclusion-exclusion principle.
answered yesterday
Mike EarnestMike Earnest
26.1k22151
$endgroup$
add a comment |
$begingroup$
It is also possible to get the following "closed form" for this distribution:
$$
bbox[#EEE,6px,border:1.5px solid black]mathbb Pbig(text# empty bags =mbig)=sum_i=m^k(-1)^i-mbinomimbinomkileft(1-iover kright)^n.
$$
This follows from the generalized inclusion exclusion principle. See Generalised inclusion-exclusion principle.
answered yesterday
Mike EarnestMike Earnest
26.1k22151
$endgroup$
add a comment |
$begingroup$
It is also possible to get the following "closed form" for this distribution:
$$
bbox[#EEE,6px,border:1.5px solid black]mathbb Pbig(text# empty bags =mbig)=sum_i=m^k(-1)^i-mbinomimbinomkileft(1-iover kright)^n.
$$
This follows from the generalized inclusion exclusion principle. See Generalised inclusion-exclusion principle.
answered yesterday
Mike EarnestMike Earnest
26.1k22151
$endgroup$
It is also possible to get the following "closed form" for this distribution:
$$
bbox[#EEE,6px,border:1.5px solid black]mathbb Pbig(text# empty bags =mbig)=sum_i=m^k(-1)^i-mbinomimbinomkileft(1-iover kright)^n.
$$
This follows from the generalized inclusion exclusion principle. See Generalised inclusion-exclusion principle.
answered yesterday
Mike EarnestMike Earnest
26.1k22151
answered yesterday
Mike EarnestMike Earnest
26.1k22151
answered yesterday
Mike EarnestMike Earnest
26.1k22151
answered yesterday
Mike EarnestMike Earnest
26.1k22151
26.1k22151
add a comment |
add a comment |
Alexander Modell is a new contributor. Be nice, and check out our Code of Conduct.
Alexander Modell is a new contributor. Be nice, and check out our Code of Conduct.
Alexander Modell is a new contributor. Be nice, and check out our Code of Conduct.
Alexander Modell is a new contributor. Be nice, and check out our Code of Conduct.
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%2f3161661%2fif-i-randomly-uniformly-distribute-n-balls-into-k-bags-what-is-the-distributi%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$
How many ways are there of choosing two empty bags? How many ways are there of distributing the balls among the remaining bags, so that at least one ball is in each bag?
$endgroup$
– Peter Shor
Mar 25 at 11:38