2013-11-19 12:13 pm (UTC)
There was a similar question on facebook a while ago:
I wonder how many facebook friends you need so that you are more like than not to have a friend with a birthday on every single day of the year?
This was solved neatly by Ben:
Under (presumably) the same assumptions as above (uniform distribution of birthdays, ignoring leap years):
Define P(N,D) to be the probability that N people have exactly D different birthdays. Then we want to find the smallest N* such that P(N*,365)>0.5.
I'm thinking induction is the way to go. Suppose we have P(N-1,d) for all d, i.e. we know the chance of N-1 people having exactly d birthdays (for d = 1, 2, ... N-1).
Then to get P(N,D) there are two ways:
1) The N-1 people had D-1 different birthdays and the Nth person has a different birthday. The chance of this is (365-(D-1))/365 = (366-D)/365.
2) The N-1 people had D different birthdays and the Nth person has the same birthday as one of them. The chance of this is D/365.
So the recursion is
P(N,D) = [ P(N-1,D) * D + P(N-1,D-1)*(366-D) ]/365
with initial conditions P(1,1) = 1 and P(1,D) = 0 for D>1.
You can probably solve this with generating functions, but to be honest I don't care that much! A simple bit of code gives N* = 2287. This is pretty close to Vincent's answer. I wonder what happens if Vincent computes the median, and not the mean? Of course, since I said the code was simple, it's also quite possible that I made a mistake!
I think this is probably the solution for this... define P (N,X) as the probability after buying N Octonauts you have X Octonauts that you want? (I did this as P(N,O) with O for Octonaut initially, but it's _awful_ notation, because O looks like 0) Then we could have the recursion as P (N,X) = P(N-1,X) * P(didn't get an octonaut you want, given you already have X) + P (N-1,X-1)* P (did get an octonaut you want, given you already have X-1)
P(didn't get an octonaut you want, given you already have X) is easy, it's (X+3)/8 (so as soon as you have all 5, you never get an octonaut you want). Likewise P (did get an octonaut you want, given you already have X-1) is (6-X)/8
But I don't know how to actually do the recursion and calculate the answer...
Reply to this
Thread from start
Post a comment in response:
This account has disabled anonymous posting.
You can comment on this post while signed in with an account from many other sites, once you have confirmed your email address.
Sign in using OpenID
If you don't have an account you can
create one now
HTML doesn't work in the subject.
Check spelling during preview
This account is set to log the IP addresses of everyone who comments.
Links will be displayed as unclickable URLs to help prevent spam.