Probability of having k groups of r consecutive empty bins throwing n balls in n bins
Suppose to throw independently n balls in n bins with uniform probability. I'm trying to obtain the probability distribution of having exactly k groups of r consecutive empty bins.
I started considering the case $r=1$ and I numbered the bins from $1$ to $n$. I counted the ways to choose $k$ numbers out of ${1,dots,n}$ so none of them is consecutive, obtaining $$binom{n-k+1}{k}.$$ For each case I had now to place $n$ balls in the remaining $n-k$ bins, which can be done in $$S(n,n-k)(n-k)!$$ ways, where $S(a,b)$ is the Stirling number of the second kind. Dividing by the number of possible configurations $n^n$, I thought to obtain the desired result, but then I realized there's a problem: the total number of empty bins can be greater than $k$, so I can have groups of $2$ or more consecutive empty bins along with the single empty bins, which aren't accounted for in my derivation.
I tried to run some simulations too, and it seems to me that the probability I'm looking for takes the form of a binomial distribution for all $r$, but I can't figure out why. For example for $n=100$ I found:
$r=1$ $;longrightarrow;$ $P(k)=Binom(40,0.38)$
$r=2$ $;longrightarrow;$ $P(k)=Binom(26,0.21)$
probability combinatorics balls-in-bins
edited Nov 21 '18 at 19:55
Jack Moody
16611
asked Nov 21 '18 at 19:44
ARWarrior
64
add a comment |
Suppose to throw independently n balls in n bins with uniform probability. I'm trying to obtain the probability distribution of having exactly k groups of r consecutive empty bins.
I started considering the case $r=1$ and I numbered the bins from $1$ to $n$. I counted the ways to choose $k$ numbers out of ${1,dots,n}$ so none of them is consecutive, obtaining $$binom{n-k+1}{k}.$$ For each case I had now to place $n$ balls in the remaining $n-k$ bins, which can be done in $$S(n,n-k)(n-k)!$$ ways, where $S(a,b)$ is the Stirling number of the second kind. Dividing by the number of possible configurations $n^n$, I thought to obtain the desired result, but then I realized there's a problem: the total number of empty bins can be greater than $k$, so I can have groups of $2$ or more consecutive empty bins along with the single empty bins, which aren't accounted for in my derivation.
I tried to run some simulations too, and it seems to me that the probability I'm looking for takes the form of a binomial distribution for all $r$, but I can't figure out why. For example for $n=100$ I found:
$r=1$ $;longrightarrow;$ $P(k)=Binom(40,0.38)$
$r=2$ $;longrightarrow;$ $P(k)=Binom(26,0.21)$
probability combinatorics balls-in-bins
edited Nov 21 '18 at 19:55
Jack Moody
16611
asked Nov 21 '18 at 19:44
ARWarrior
64
add a comment |
Suppose to throw independently n balls in n bins with uniform probability. I'm trying to obtain the probability distribution of having exactly k groups of r consecutive empty bins.
I started considering the case $r=1$ and I numbered the bins from $1$ to $n$. I counted the ways to choose $k$ numbers out of ${1,dots,n}$ so none of them is consecutive, obtaining $$binom{n-k+1}{k}.$$ For each case I had now to place $n$ balls in the remaining $n-k$ bins, which can be done in $$S(n,n-k)(n-k)!$$ ways, where $S(a,b)$ is the Stirling number of the second kind. Dividing by the number of possible configurations $n^n$, I thought to obtain the desired result, but then I realized there's a problem: the total number of empty bins can be greater than $k$, so I can have groups of $2$ or more consecutive empty bins along with the single empty bins, which aren't accounted for in my derivation.
I tried to run some simulations too, and it seems to me that the probability I'm looking for takes the form of a binomial distribution for all $r$, but I can't figure out why. For example for $n=100$ I found:
$r=1$ $;longrightarrow;$ $P(k)=Binom(40,0.38)$
$r=2$ $;longrightarrow;$ $P(k)=Binom(26,0.21)$
probability combinatorics balls-in-bins
edited Nov 21 '18 at 19:55
Jack Moody
16611
asked Nov 21 '18 at 19:44
ARWarrior
64
Suppose to throw independently n balls in n bins with uniform probability. I'm trying to obtain the probability distribution of having exactly k groups of r consecutive empty bins.
I started considering the case $r=1$ and I numbered the bins from $1$ to $n$. I counted the ways to choose $k$ numbers out of ${1,dots,n}$ so none of them is consecutive, obtaining $$binom{n-k+1}{k}.$$ For each case I had now to place $n$ balls in the remaining $n-k$ bins, which can be done in $$S(n,n-k)(n-k)!$$ ways, where $S(a,b)$ is the Stirling number of the second kind. Dividing by the number of possible configurations $n^n$, I thought to obtain the desired result, but then I realized there's a problem: the total number of empty bins can be greater than $k$, so I can have groups of $2$ or more consecutive empty bins along with the single empty bins, which aren't accounted for in my derivation.
I tried to run some simulations too, and it seems to me that the probability I'm looking for takes the form of a binomial distribution for all $r$, but I can't figure out why. For example for $n=100$ I found:
$r=1$ $;longrightarrow;$ $P(k)=Binom(40,0.38)$
$r=2$ $;longrightarrow;$ $P(k)=Binom(26,0.21)$
probability combinatorics balls-in-bins
probability combinatorics balls-in-bins
edited Nov 21 '18 at 19:55
Jack Moody
16611
asked Nov 21 '18 at 19:44
ARWarrior
64
edited Nov 21 '18 at 19:55
Jack Moody
16611
asked Nov 21 '18 at 19:44
ARWarrior
64
edited Nov 21 '18 at 19:55
Jack Moody
16611
edited Nov 21 '18 at 19:55
Jack Moody
16611
edited Nov 21 '18 at 19:55
Jack Moody
16611
16611
asked Nov 21 '18 at 19:44
ARWarrior
64
asked Nov 21 '18 at 19:44
ARWarrior
64
asked Nov 21 '18 at 19:44
ARWarrior
64
64
add a comment |
add a comment |
0
active
oldest
votes
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%2f3008237%2fprobability-of-having-k-groups-of-r-consecutive-empty-bins-throwing-n-balls-in-n%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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%2f3008237%2fprobability-of-having-k-groups-of-r-consecutive-empty-bins-throwing-n-balls-in-n%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
