Solving the Birthday Problem: Probability & Average Guesses

[curiouschris]

Hi

I have a question about probabilities.

Given 5 people each having a birthday on a different date in the year.

I have the task of working out which day in the year each ones birthday is. There are no clues as to the dates except that if I manage to get one right the persons who's day I got right will admit to it.

In other words there is no way of me knowing before hand which days the birthdays fall on.
The only clue I have is that the birthdays are normally spread out evenly across the year. It is highly unlikely that they are all in January (but possible) and the same goes for December.

I could start off at day 1 and progress to day 365 guaranteeing to get it right in a maximum of 365 guesses.

But what if I was to randomly guess dates?

Is their a way of determining the average number of guesses I would need to have before getting it right?

At the low end it would be at least 5 at the high end it would be 365, but is there a way to work out the average?

I know this sounds like a home work question but its actually not its for a software program. a way to reduce the *average* time it takes to reach the solution.

Much Appreciated
CC

 

[frustr8photon]

Okay, so basically this is a discrete, uniform distribution with 365 possible values, from which we have randomly selected five distinct data points. (It looks like you want to assume that the birthdays are definitely on five distinct days, which probably makes things easier.)

Regarding your question, the method/order of your "guessing" shouldn't matter. Whether you go in order, Jan. 1-Dec. 31, backwards, or using some sort of random guessing technique, should make no difference whatsoever. We should probably assume, however, that you won't re-guess the same day twice.

Let's first work on what may be a slightly easier problem: the expected number of guesses you would make to correctly guess anyone of the five birthdays:

The chance of selecting any correct birthday on your first guess is (5/365). The chance that your second guess is your first correct guess is (360/365)*(5/364). The chance that your third guess is your first correct guess is (360/365)*(359/364)*(5/363)...etc.

Based on this pattern, the probability that your first correct guess is on your nth guess is:
\frac{5}{366-n} \frac{360!}{365!} \frac{(366-n)!}{(361-n)!}

So then the expected number of required guesses N would be:
E(N) = \sum^{n=1}_{n=361} \frac{5}{366-n} \frac{360!}{365!} \frac{(366-n)!}{(361-n)!} n

Wolfram alpha says that this = 61 (apparently exactly). I might have guessed lower, but I suppose it makes some sense that you'd have to work your way through about two months if, on average, there is a birthday every 12/5 = 2.4 months.

However, I think your original question is still unanswered. You want the expected number of guesses required to correctly identify all five birthdays, right? I'll work on this in my next post.

 

[frustr8photon]

So in the above post, I found that the expected number of guesses to identify one of the five birthdays was 61. Now I will find the expected number of guesses to correctly identify all five birthdays.

To do this, I think we would need to determine the probability that a string (of guesses) with length n contains all five birthdays and terminates in a birthday (since when you guess the last birthday, you are done guessing).

Okay...so let's look at this as the probability that a string of length (n-1) contains four of the five birthdays, times the probability of then selecting the fifth birthday.

A. First the latter part. The probability p_a of selecting the fifth birthday on the nth guess after already selecting the other four in the previous n-1 guesses is simply 1/(365-(n-1)), so p_a = 1/(366-n).

B. Now let's find the probability p_b that a string of length n-1 contains four birthdays.

p_b can be found using the hypergeometric density function, given that there are 5 birthdays in total and 365 days to choose from.
p_b = (5 choose 4) * ( 365-5 choose n-1-4) / (365 choose n-1)
p_b = 5 (366-n) \frac{360!}{365!} \frac{(n-1)!}{(n-5)!}

C. Thus, probability that a string of n guesses contains all five birthdays and terminates in a birthday equals:

p_a * p_b = 5 \frac{360!}{365!} \frac{(n-1)!}{(n-5)!}

D. Finally, to find the expected value E (N), we must calculate the sum:

E(N) = \sum^{n=5}_{n=365} 5 \frac{360!}{365!} \frac{(n-1)!}{(n-5)!} n

According to Wolfram alpha, E(N) = 305, apparently exactly. Like the last problem, this is surprisingly high, but since the math all seems to make sense, I'm forced to accept it. Remember that this setup gives the expected number of guesses you would make to have guessed all five uniformly random yet distinct birthdays (given that you you do not repeat guesses). If I have time, I will E(N) for a number of birthdays "m" other than 5. Should be simple.