ext_8145 ([identity profile] atreic.livejournal.com) wrote in [personal profile] atreic 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...

Post a comment in response:

Anonymous( )Anonymous This account has disabled anonymous posting.
OpenID( )OpenID 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.
Account name:
If you don't have an account you can create one now.
HTML doesn't work in the subject.


Notice: This account is set to log the IP addresses of everyone who comments.
Links will be displayed as unclickable URLs to help prevent spam.