1
$\begingroup$

In a room with many people, we ask each person his/her birthday. Let $N$ be the number of people queried until we get a "duplicate" birthday. Calculate $\mathbb{P}(N >n)$ for $n = 0,1,2,\dots$.

The solutions says

$\mathbb{P} (N>n) = \displaystyle\frac{365}{365} \frac{364}{365} \dots \frac{365-n+1}{365}$

I am curious to know how to achieve the answer? Thanks!

  • 0
    Note that N>n if and only if the first $n$ people queried have distinct birthdays.2012-09-18

2 Answers 2

3

The chance that you have to ask more than 1 is clearly $1=\frac {365}{365}$ as the first person can't match. The chance that you have to ask more than 2 is $\frac {364}{365}$, as there is only one day to match. The third person has two chances to match, as we have been told that the first two are different, and so on.

1

This problem is called birthday paradox. It is acutally a very interesting problem. In a group of $23$ people the probability that two of them will have exactly the same birthday is one half. If you think that there are $365$ days and $23$ people such a probability $p=0.5$ sounds a bit high perhaps.. though it is the probability..

There is also a very good exponential approximation to the problem. This problem is taught in cryptography lectures as it is important to know the probability of collisions if one wants to design some hash functions.

For more informations I think wiki will be quite enough:

http://en.wikipedia.org/wiki/Birthday_problem

What Wiki says about hash functions (if interesting):

In an ideal "perfect hash function", no bucket should have more than one record; but a small number of collisions is virtually inevitable, even if n is much larger than m – see the birthday paradox).