How many batches of balls have a leading ball when we fill $n$ bins by placing $k$ balls each turn
up vote
2
down vote
favorite
Suppose we have $n$ bins and $k<n$ is some natural number. Each turn we select at random $k$ distinct bins out of the $n$ bins in which we place a ball. How many turns does it take on average until there is at least $1$ ball in each of the bins? This part has been solved in the comments (as it turned out to be a duplicate).
Related to this : If we call a collection of $k$ balls a winner if one of the balls is the first one to enter a bin, how many winners are there on average. So the first batch of ball has a 100$%$ chance of being a winner and then the probability of being a winner decreases as more balls are added. For the coupon collector's problem mentioned in the comments (with $k=1$) it is obvious that there will always be exactly $n$ winning batches.
probability combinatorics
asked Nov 13 at 22:50
Darkwizie
13610
|
show 1 more comment
up vote
2
down vote
favorite
Suppose we have $n$ bins and $k<n$ is some natural number. Each turn we select at random $k$ distinct bins out of the $n$ bins in which we place a ball. How many turns does it take on average until there is at least $1$ ball in each of the bins? This part has been solved in the comments (as it turned out to be a duplicate).
Related to this : If we call a collection of $k$ balls a winner if one of the balls is the first one to enter a bin, how many winners are there on average. So the first batch of ball has a 100$%$ chance of being a winner and then the probability of being a winner decreases as more balls are added. For the coupon collector's problem mentioned in the comments (with $k=1$) it is obvious that there will always be exactly $n$ winning batches.
probability combinatorics
asked Nov 13 at 22:50
Darkwizie
13610
1
When $k=1$ this is the coupon collector's problem, so you might start by researching that.
– saulspatz
Nov 13 at 22:55
Thank you for this reference, it gives me a good idea of how difficult the problem is and a good starting point to investigate further!
– Darkwizie
Nov 13 at 23:07
"Each turn we select at random k distinct bins out of the n bins in which we place a ball." Does it mean that $k $ balls are placed in (randomly chosen) $k $bins each turn?
– user
Nov 13 at 23:14
@user : Yes exactly
– Darkwizie
Nov 13 at 23:21
The first part is essentially the same as math.stackexchange.com/questions/2147576/… which has two good responses
– Henry
Nov 13 at 23:42
|
show 1 more comment
up vote
2
down vote
favorite
up vote
2
down vote
favorite
Suppose we have $n$ bins and $k<n$ is some natural number. Each turn we select at random $k$ distinct bins out of the $n$ bins in which we place a ball. How many turns does it take on average until there is at least $1$ ball in each of the bins? This part has been solved in the comments (as it turned out to be a duplicate).
Related to this : If we call a collection of $k$ balls a winner if one of the balls is the first one to enter a bin, how many winners are there on average. So the first batch of ball has a 100$%$ chance of being a winner and then the probability of being a winner decreases as more balls are added. For the coupon collector's problem mentioned in the comments (with $k=1$) it is obvious that there will always be exactly $n$ winning batches.
probability combinatorics
asked Nov 13 at 22:50
Darkwizie
13610
Suppose we have $n$ bins and $k<n$ is some natural number. Each turn we select at random $k$ distinct bins out of the $n$ bins in which we place a ball. How many turns does it take on average until there is at least $1$ ball in each of the bins? This part has been solved in the comments (as it turned out to be a duplicate).
Related to this : If we call a collection of $k$ balls a winner if one of the balls is the first one to enter a bin, how many winners are there on average. So the first batch of ball has a 100$%$ chance of being a winner and then the probability of being a winner decreases as more balls are added. For the coupon collector's problem mentioned in the comments (with $k=1$) it is obvious that there will always be exactly $n$ winning batches.
probability combinatorics
probability combinatorics
asked Nov 13 at 22:50
Darkwizie
13610
asked Nov 13 at 22:50
Darkwizie
13610
edited Nov 14 at 16:39
asked Nov 13 at 22:50
Darkwizie
13610
asked Nov 13 at 22:50
Darkwizie
13610
asked Nov 13 at 22:50
Darkwizie
13610
13610
1
When $k=1$ this is the coupon collector's problem, so you might start by researching that.
– saulspatz
Nov 13 at 22:55
Thank you for this reference, it gives me a good idea of how difficult the problem is and a good starting point to investigate further!
– Darkwizie
Nov 13 at 23:07
"Each turn we select at random k distinct bins out of the n bins in which we place a ball." Does it mean that $k $ balls are placed in (randomly chosen) $k $bins each turn?
– user
Nov 13 at 23:14
@user : Yes exactly
– Darkwizie
Nov 13 at 23:21
The first part is essentially the same as math.stackexchange.com/questions/2147576/… which has two good responses
– Henry
Nov 13 at 23:42
|
show 1 more comment
1
When $k=1$ this is the coupon collector's problem, so you might start by researching that.
– saulspatz
Nov 13 at 22:55
Thank you for this reference, it gives me a good idea of how difficult the problem is and a good starting point to investigate further!
– Darkwizie
Nov 13 at 23:07
"Each turn we select at random k distinct bins out of the n bins in which we place a ball." Does it mean that $k $ balls are placed in (randomly chosen) $k $bins each turn?
– user
Nov 13 at 23:14
@user : Yes exactly
– Darkwizie
Nov 13 at 23:21
The first part is essentially the same as math.stackexchange.com/questions/2147576/… which has two good responses
– Henry
Nov 13 at 23:42
1
1
When $k=1$ this is the coupon collector's problem, so you might start by researching that.
– saulspatz
Nov 13 at 22:55
When $k=1$ this is the coupon collector's problem, so you might start by researching that.
– saulspatz
Nov 13 at 22:55
Thank you for this reference, it gives me a good idea of how difficult the problem is and a good starting point to investigate further!
– Darkwizie
Nov 13 at 23:07
Thank you for this reference, it gives me a good idea of how difficult the problem is and a good starting point to investigate further!
– Darkwizie
Nov 13 at 23:07
"Each turn we select at random k distinct bins out of the n bins in which we place a ball." Does it mean that $k $ balls are placed in (randomly chosen) $k $bins each turn?
– user
Nov 13 at 23:14
"Each turn we select at random k distinct bins out of the n bins in which we place a ball." Does it mean that $k $ balls are placed in (randomly chosen) $k $bins each turn?
– user
Nov 13 at 23:14
@user : Yes exactly
– Darkwizie
Nov 13 at 23:21
@user : Yes exactly
– Darkwizie
Nov 13 at 23:21
The first part is essentially the same as math.stackexchange.com/questions/2147576/… which has two good responses
– Henry
Nov 13 at 23:42
The first part is essentially the same as math.stackexchange.com/questions/2147576/… which has two good responses
– Henry
Nov 13 at 23:42
|
show 1 more comment
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
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%2f2997471%2fhow-many-batches-of-balls-have-a-leading-ball-when-we-fill-n-bins-by-placing%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
1
When $k=1$ this is the coupon collector's problem, so you might start by researching that.
– saulspatz
Nov 13 at 22:55
Thank you for this reference, it gives me a good idea of how difficult the problem is and a good starting point to investigate further!
– Darkwizie
Nov 13 at 23:07
"Each turn we select at random k distinct bins out of the n bins in which we place a ball." Does it mean that $k $ balls are placed in (randomly chosen) $k $bins each turn?
– user
Nov 13 at 23:14
@user : Yes exactly
– Darkwizie
Nov 13 at 23:21
The first part is essentially the same as math.stackexchange.com/questions/2147576/… which has two good responses
– Henry
Nov 13 at 23:42