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 Nov 19 at 21:38
Drew
112
|
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 Nov 19 at 21:38
Drew
112
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
Nov 19 at 21:44
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
Nov 19 at 21:48
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
Nov 19 at 21:49
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
Nov 19 at 22:13
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
Nov 19 at 23:49
|
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 Nov 19 at 21:38
Drew
112
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 Nov 19 at 21:38
Drew
112
asked Nov 19 at 21:38
Drew
112
edited Nov 19 at 21:43
asked Nov 19 at 21:38
Drew
112
asked Nov 19 at 21:38
Drew
112
asked Nov 19 at 21:38
Drew
112
112
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
Nov 19 at 21:44
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
Nov 19 at 21:48
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
Nov 19 at 21:49
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
Nov 19 at 22:13
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
Nov 19 at 23:49
|
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
Nov 19 at 21:44
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
Nov 19 at 21:48
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
Nov 19 at 21:49
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
Nov 19 at 22:13
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
Nov 19 at 23:49
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
Nov 19 at 21:44
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
Nov 19 at 21:44
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
Nov 19 at 21:48
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
Nov 19 at 21:48
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
Nov 19 at 21:49
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
Nov 19 at 21:49
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
Nov 19 at 22:13
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
Nov 19 at 22:13
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
Nov 19 at 23:49
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
Nov 19 at 23:49
|
show 4 more comments
active
oldest
votes
active
oldest
votes
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%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
Nov 19 at 21:44
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
Nov 19 at 21:48
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
Nov 19 at 21:49
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
Nov 19 at 22:13
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
Nov 19 at 23:49