You're viewing atreic's journal Create a Dreamwidth Account Learn More  site light  Reload page in style:
If I'm wrong, tell me why I'm wrong and you're right.. (Reply).
Sun  Mon  Tue  Wed  Thu  Fri  Sat 

1

2 
3

4

5

6


7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

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(N1,d) for all d, i.e. we know the chance of N1 people having exactly d birthdays (for d = 1, 2, ... N1).
Then to get P(N,D) there are two ways:
1) The N1 people had D1 different birthdays and the Nth person has a different birthday. The chance of this is (365(D1))/365 = (366D)/365.
2) The N1 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(N1,D) * D + P(N1,D1)*(366D) ]/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(N1,X) * P(didn't get an octonaut you want, given you already have X) + P (N1,X1)* P (did get an octonaut you want, given you already have X1)
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 X1) is (6X)/8
But I don't know how to actually do the recursion and calculate the answer...