Mixing
Generalized Birthday Problem? Combinatorics
up vote
2
down vote
favorite
I am having a difficult time understanding how to think about and analyze the following problem:
(I have done research, but I am not sure how to phrase my enquiries and my research seems to be almost helpful, I think I need a little nudge in the right direction)
There are n people in a room that contains a vending machine that
dispenses k varieties of soda, k and n positive integers. Assume the
machine is stocked with at least n cans of each variety. Every person
buys one can of soda, dispensed at random. Show that when n is large,
the probability that two people get the same variety of soda is
$1 -e^frac{-n^2}{2k}$.
This seems to be the equation for the birthday problem when you consider $1 - bar{p}(x)$, with the approximation $e^x approx 1 + x$.
However, I don't see how this could be the case.
I do not know what to make of "the machine is stocked with at least n cans of each variety", as this is incredibly vague. Do we assume there are only n of each variety? Do we assume there are an infinite number of cans of each variety? How do we handle the fact that there are k varieties of soda, whereas there is only 1 variety of birthday in the birthday problem? How could it end up being the same formula despite all of these differences?
When I follow the steps laid out in the wikipedia article on the birthday problem I end up getting something along the lines of (via the pigeonhole principle):
$bar{p}(x) = 1 - p(x) = 1 -(1- frac{(k)_n}{(k)^n}) = frac{(k)_n}{(k)^n}$
This in turn can be written:
$frac{(k)(k-1)...(k-n+1)}{k^n}$
$=frac{(k)}{k}frac{(k-1)}{k}...frac{(k-n+1)}{k}$
$=1(1-frac{1}{k})(1-frac{2}{k})...(1-frac{n-1}{k})$
This only holds if we assume there is a uniform probability of each person getting a given soda 1/k (like the pigeonhole principle).
From here this becomes the same as the birthday problem, but why did we assume the probability is 1/k for each of them?
Doesn't the probability change as sodas are dispensed, since the pool of targets and the overall pool of candidates both shrink?
I'm pretty sure this is wrong, but I do not know what to do.
Can someone please explain to me how I should be thinking about this problem, and how I should approach it?
Thank you, I really appreciate it.
probability combinatorics pigeonhole-principle birthday
asked 2 days ago
Drew
112
New contributor
Drew is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
|
show 4 more comments
up vote
2
down vote
favorite
I am having a difficult time understanding how to think about and analyze the following problem:
(I have done research, but I am not sure how to phrase my enquiries and my research seems to be almost helpful, I think I need a little nudge in the right direction)
There are n people in a room that contains a vending machine that
dispenses k varieties of soda, k and n positive integers. Assume the
machine is stocked with at least n cans of each variety. Every person
buys one can of soda, dispensed at random. Show that when n is large,
the probability that two people get the same variety of soda is
$1 -e^frac{-n^2}{2k}$.
This seems to be the equation for the birthday problem when you consider $1 - bar{p}(x)$, with the approximation $e^x approx 1 + x$.
However, I don't see how this could be the case.
I do not know what to make of "the machine is stocked with at least n cans of each variety", as this is incredibly vague. Do we assume there are only n of each variety? Do we assume there are an infinite number of cans of each variety? How do we handle the fact that there are k varieties of soda, whereas there is only 1 variety of birthday in the birthday problem? How could it end up being the same formula despite all of these differences?
When I follow the steps laid out in the wikipedia article on the birthday problem I end up getting something along the lines of (via the pigeonhole principle):
$bar{p}(x) = 1 - p(x) = 1 -(1- frac{(k)_n}{(k)^n}) = frac{(k)_n}{(k)^n}$
This in turn can be written:
$frac{(k)(k-1)...(k-n+1)}{k^n}$
$=frac{(k)}{k}frac{(k-1)}{k}...frac{(k-n+1)}{k}$
$=1(1-frac{1}{k})(1-frac{2}{k})...(1-frac{n-1}{k})$
This only holds if we assume there is a uniform probability of each person getting a given soda 1/k (like the pigeonhole principle).
From here this becomes the same as the birthday problem, but why did we assume the probability is 1/k for each of them?
Doesn't the probability change as sodas are dispensed, since the pool of targets and the overall pool of candidates both shrink?
I'm pretty sure this is wrong, but I do not know what to do.
Can someone please explain to me how I should be thinking about this problem, and how I should approach it?
Thank you, I really appreciate it.
probability combinatorics pigeonhole-principle birthday
asked 2 days ago
Drew
112
New contributor
Drew is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
As to the distribution questions: the only thing that makes sense is to assume that each person's selection is independent of all the others and each person gets a soda uniformly from the $k$ options. If they had something else in mind, they should have given you more information.
– lulu
2 days ago
Oh I see. So they would indeed have a uniform probability of 1/k then. Maybe I was reading too much into the information they gave me. What you said makes sense, thank you!
– Drew
2 days ago
Well, you do have a point. By setting up this story they lead you to believe that the mechanics will matter. But then, as you point out, they are so vague about the mechanics that, really, the only option is to just assume that they didn't mean it at all, and that they just wanted to rephrase the standard birthday problem .
– lulu
2 days ago
1
This question is very poorly worded. First, instead of "at least $n$" cans of each type, it should have said each choice is uniform among the $k$ types. Further, if $k<n$, the probability is exactly $1$ (some two people are sure to get the same type). For the required answer to make any sense, we need $kge n$, but for large $n$, how does $k$ grow? I have an informal proof if we assume, not just $n gg 1$, but also $k/n gg 1$.
– antkam
2 days ago
1
If as @antkam suggests, you need $n gg 1$ and $k /n gg 1$ to get the approximations to work with uniform and independent probabilities for each can, then you can probably extend this to cases where there are an equal finite number of cans of each variety with at least $n$ of each, as the probabilities will still be close to $frac1k$ in the non-collision calculations
– Henry
2 days ago
|
show 4 more comments
up vote
2
down vote
favorite
up vote
2
down vote
favorite
I am having a difficult time understanding how to think about and analyze the following problem:
(I have done research, but I am not sure how to phrase my enquiries and my research seems to be almost helpful, I think I need a little nudge in the right direction)
There are n people in a room that contains a vending machine that
dispenses k varieties of soda, k and n positive integers. Assume the
machine is stocked with at least n cans of each variety. Every person
buys one can of soda, dispensed at random. Show that when n is large,
the probability that two people get the same variety of soda is
$1 -e^frac{-n^2}{2k}$.
This seems to be the equation for the birthday problem when you consider $1 - bar{p}(x)$, with the approximation $e^x approx 1 + x$.
However, I don't see how this could be the case.
I do not know what to make of "the machine is stocked with at least n cans of each variety", as this is incredibly vague. Do we assume there are only n of each variety? Do we assume there are an infinite number of cans of each variety? How do we handle the fact that there are k varieties of soda, whereas there is only 1 variety of birthday in the birthday problem? How could it end up being the same formula despite all of these differences?
When I follow the steps laid out in the wikipedia article on the birthday problem I end up getting something along the lines of (via the pigeonhole principle):
$bar{p}(x) = 1 - p(x) = 1 -(1- frac{(k)_n}{(k)^n}) = frac{(k)_n}{(k)^n}$
This in turn can be written:
$frac{(k)(k-1)...(k-n+1)}{k^n}$
$=frac{(k)}{k}frac{(k-1)}{k}...frac{(k-n+1)}{k}$
$=1(1-frac{1}{k})(1-frac{2}{k})...(1-frac{n-1}{k})$
This only holds if we assume there is a uniform probability of each person getting a given soda 1/k (like the pigeonhole principle).
From here this becomes the same as the birthday problem, but why did we assume the probability is 1/k for each of them?
Doesn't the probability change as sodas are dispensed, since the pool of targets and the overall pool of candidates both shrink?
I'm pretty sure this is wrong, but I do not know what to do.
Can someone please explain to me how I should be thinking about this problem, and how I should approach it?
Thank you, I really appreciate it.
probability combinatorics pigeonhole-principle birthday
asked 2 days ago
Drew
112
New contributor
Drew is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
I am having a difficult time understanding how to think about and analyze the following problem:
(I have done research, but I am not sure how to phrase my enquiries and my research seems to be almost helpful, I think I need a little nudge in the right direction)
There are n people in a room that contains a vending machine that
dispenses k varieties of soda, k and n positive integers. Assume the
machine is stocked with at least n cans of each variety. Every person
buys one can of soda, dispensed at random. Show that when n is large,
the probability that two people get the same variety of soda is
$1 -e^frac{-n^2}{2k}$.
This seems to be the equation for the birthday problem when you consider $1 - bar{p}(x)$, with the approximation $e^x approx 1 + x$.
However, I don't see how this could be the case.
I do not know what to make of "the machine is stocked with at least n cans of each variety", as this is incredibly vague. Do we assume there are only n of each variety? Do we assume there are an infinite number of cans of each variety? How do we handle the fact that there are k varieties of soda, whereas there is only 1 variety of birthday in the birthday problem? How could it end up being the same formula despite all of these differences?
When I follow the steps laid out in the wikipedia article on the birthday problem I end up getting something along the lines of (via the pigeonhole principle):
$bar{p}(x) = 1 - p(x) = 1 -(1- frac{(k)_n}{(k)^n}) = frac{(k)_n}{(k)^n}$
This in turn can be written:
$frac{(k)(k-1)...(k-n+1)}{k^n}$
$=frac{(k)}{k}frac{(k-1)}{k}...frac{(k-n+1)}{k}$
$=1(1-frac{1}{k})(1-frac{2}{k})...(1-frac{n-1}{k})$
This only holds if we assume there is a uniform probability of each person getting a given soda 1/k (like the pigeonhole principle).
From here this becomes the same as the birthday problem, but why did we assume the probability is 1/k for each of them?
Doesn't the probability change as sodas are dispensed, since the pool of targets and the overall pool of candidates both shrink?
I'm pretty sure this is wrong, but I do not know what to do.
Can someone please explain to me how I should be thinking about this problem, and how I should approach it?
Thank you, I really appreciate it.
probability combinatorics pigeonhole-principle birthday
probability combinatorics pigeonhole-principle birthday
asked 2 days ago
Drew
112
New contributor
Drew is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 2 days ago
Drew
112
New contributor
Drew is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 2 days ago
asked 2 days ago
Drew
112
New contributor
Drew is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 2 days ago
Drew
112
asked 2 days ago
Drew
112
112
New contributor
Drew is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Drew is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Drew is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
As to the distribution questions: the only thing that makes sense is to assume that each person's selection is independent of all the others and each person gets a soda uniformly from the $k$ options. If they had something else in mind, they should have given you more information.
– lulu
2 days ago
Oh I see. So they would indeed have a uniform probability of 1/k then. Maybe I was reading too much into the information they gave me. What you said makes sense, thank you!
– Drew
2 days ago
Well, you do have a point. By setting up this story they lead you to believe that the mechanics will matter. But then, as you point out, they are so vague about the mechanics that, really, the only option is to just assume that they didn't mean it at all, and that they just wanted to rephrase the standard birthday problem .
– lulu
2 days ago
1
This question is very poorly worded. First, instead of "at least $n$" cans of each type, it should have said each choice is uniform among the $k$ types. Further, if $k<n$, the probability is exactly $1$ (some two people are sure to get the same type). For the required answer to make any sense, we need $kge n$, but for large $n$, how does $k$ grow? I have an informal proof if we assume, not just $n gg 1$, but also $k/n gg 1$.
– antkam
2 days ago
1
If as @antkam suggests, you need $n gg 1$ and $k /n gg 1$ to get the approximations to work with uniform and independent probabilities for each can, then you can probably extend this to cases where there are an equal finite number of cans of each variety with at least $n$ of each, as the probabilities will still be close to $frac1k$ in the non-collision calculations
– Henry
2 days ago
|
show 4 more comments
As to the distribution questions: the only thing that makes sense is to assume that each person's selection is independent of all the others and each person gets a soda uniformly from the $k$ options. If they had something else in mind, they should have given you more information.
– lulu
2 days ago
Oh I see. So they would indeed have a uniform probability of 1/k then. Maybe I was reading too much into the information they gave me. What you said makes sense, thank you!
– Drew
2 days ago
Well, you do have a point. By setting up this story they lead you to believe that the mechanics will matter. But then, as you point out, they are so vague about the mechanics that, really, the only option is to just assume that they didn't mean it at all, and that they just wanted to rephrase the standard birthday problem .
– lulu
2 days ago
1
This question is very poorly worded. First, instead of "at least $n$" cans of each type, it should have said each choice is uniform among the $k$ types. Further, if $k<n$, the probability is exactly $1$ (some two people are sure to get the same type). For the required answer to make any sense, we need $kge n$, but for large $n$, how does $k$ grow? I have an informal proof if we assume, not just $n gg 1$, but also $k/n gg 1$.
– antkam
2 days ago
1
If as @antkam suggests, you need $n gg 1$ and $k /n gg 1$ to get the approximations to work with uniform and independent probabilities for each can, then you can probably extend this to cases where there are an equal finite number of cans of each variety with at least $n$ of each, as the probabilities will still be close to $frac1k$ in the non-collision calculations
– Henry
2 days ago
As to the distribution questions: the only thing that makes sense is to assume that each person's selection is independent of all the others and each person gets a soda uniformly from the $k$ options. If they had something else in mind, they should have given you more information.
– lulu
2 days ago
As to the distribution questions: the only thing that makes sense is to assume that each person's selection is independent of all the others and each person gets a soda uniformly from the $k$ options. If they had something else in mind, they should have given you more information.
– lulu
2 days ago
Oh I see. So they would indeed have a uniform probability of 1/k then. Maybe I was reading too much into the information they gave me. What you said makes sense, thank you!
– Drew
2 days ago
Oh I see. So they would indeed have a uniform probability of 1/k then. Maybe I was reading too much into the information they gave me. What you said makes sense, thank you!
– Drew
2 days ago
Well, you do have a point. By setting up this story they lead you to believe that the mechanics will matter. But then, as you point out, they are so vague about the mechanics that, really, the only option is to just assume that they didn't mean it at all, and that they just wanted to rephrase the standard birthday problem .
– lulu
2 days ago
Well, you do have a point. By setting up this story they lead you to believe that the mechanics will matter. But then, as you point out, they are so vague about the mechanics that, really, the only option is to just assume that they didn't mean it at all, and that they just wanted to rephrase the standard birthday problem .
– lulu
2 days ago
1
1
This question is very poorly worded. First, instead of "at least $n$" cans of each type, it should have said each choice is uniform among the $k$ types. Further, if $k<n$, the probability is exactly $1$ (some two people are sure to get the same type). For the required answer to make any sense, we need $kge n$, but for large $n$, how does $k$ grow? I have an informal proof if we assume, not just $n gg 1$, but also $k/n gg 1$.
– antkam
2 days ago
This question is very poorly worded. First, instead of "at least $n$" cans of each type, it should have said each choice is uniform among the $k$ types. Further, if $k<n$, the probability is exactly $1$ (some two people are sure to get the same type). For the required answer to make any sense, we need $kge n$, but for large $n$, how does $k$ grow? I have an informal proof if we assume, not just $n gg 1$, but also $k/n gg 1$.
– antkam
2 days ago
1
1
If as @antkam suggests, you need $n gg 1$ and $k /n gg 1$ to get the approximations to work with uniform and independent probabilities for each can, then you can probably extend this to cases where there are an equal finite number of cans of each variety with at least $n$ of each, as the probabilities will still be close to $frac1k$ in the non-collision calculations
– Henry
2 days ago
If as @antkam suggests, you need $n gg 1$ and $k /n gg 1$ to get the approximations to work with uniform and independent probabilities for each can, then you can probably extend this to cases where there are an equal finite number of cans of each variety with at least $n$ of each, as the probabilities will still be close to $frac1k$ in the non-collision calculations
– Henry
2 days ago
|
show 4 more comments
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
Drew is a new contributor. Be nice, and check out our Code of Conduct.
Drew is a new contributor. Be nice, and check out our Code of Conduct.
Drew is a new contributor. Be nice, and check out our Code of Conduct.
Drew 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%2f3005559%2fgeneralized-birthday-problem-combinatorics%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
As to the distribution questions: the only thing that makes sense is to assume that each person's selection is independent of all the others and each person gets a soda uniformly from the $k$ options. If they had something else in mind, they should have given you more information.
– lulu
2 days ago
Oh I see. So they would indeed have a uniform probability of 1/k then. Maybe I was reading too much into the information they gave me. What you said makes sense, thank you!
– Drew
2 days ago
Well, you do have a point. By setting up this story they lead you to believe that the mechanics will matter. But then, as you point out, they are so vague about the mechanics that, really, the only option is to just assume that they didn't mean it at all, and that they just wanted to rephrase the standard birthday problem .
– lulu
2 days ago
1
This question is very poorly worded. First, instead of "at least $n$" cans of each type, it should have said each choice is uniform among the $k$ types. Further, if $k<n$, the probability is exactly $1$ (some two people are sure to get the same type). For the required answer to make any sense, we need $kge n$, but for large $n$, how does $k$ grow? I have an informal proof if we assume, not just $n gg 1$, but also $k/n gg 1$.
– antkam
2 days ago
1
If as @antkam suggests, you need $n gg 1$ and $k /n gg 1$ to get the approximations to work with uniform and independent probabilities for each can, then you can probably extend this to cases where there are an equal finite number of cans of each variety with at least $n$ of each, as the probabilities will still be close to $frac1k$ in the non-collision calculations
– Henry
2 days ago