1
$\begingroup$

Birthday problem: What is the minimum number of people in a room such that at least two people have the same birthday has a probablity $\geq 0.5$ ( http://en.wikipedia.org/wiki/Birthday_problem )

I am trying to solve this by considering each day separately and then adding up the probabilities. This is equivalent to (birthday collision on a particular day) $\cdot \, 365$. I understand that I am doing something wrong as the probability goes more than $1$ after a few iterations. Can you please help me with identifying my mistake. Thanks in advance

$2$ persons: $A$ and $B$ $= 1/365 ( \text{prob of $A$ being born on day 1} ) \cdot 1/365 ( \text{prob of $B$ being born on day 1} ) + 1/365 ( \text{prob of $A$ being born on day 2}) \cdot 1/365 ( \text{prob of $B$ being born on day 2} ) + \dots = \frac{1}{(365 \cdot 365)} ( \text{probability on each day} ) \cdot 365 = 1/365$

$3$ persons: $A$, $B$ and $C$ $AB$ born on day 1 : $\frac{1}{(365 \cdot 365 )}$ $BC$ born on day 1 : $\frac{1}{(365 \cdot 365 )}$ $CA$ born on day 1 : $\frac{1}{(365 \cdot 365 )}$ for day 1 = $\frac{3}{(365\cdot 365)}$ for day 1 = number of pairs$/(365\cdot 365) = 3c2/(365\cdot 365)$ for all days $= 365 \cdot 3c2 / ( 365 \cdot 365 )$ $= 3c2 / 365$

4 persons: $= 4c2 / 365$

2 Answers 2

2

You are counting some cases more than once. Example :

For three persons, $A,B,C$ and for January 1st you have:

$A,B$ born on 1.1: $\frac{1}{365^2}$

$B,C$ born on 1.1: $\frac{1}{365^2}$

$A,C$ born on 1.1: $\frac{1}{365^2}$

Which are all true, but you counted the case that $A,B,C$ were all born on 1.1 three times.

This is called the inclusion-exclusion principle, and can indeed be employed to solve the birthday problem.

However, there is a much simpler solution if you consider the probability that all birthdays are on distinct days and take its complement.

1

The solution is something like 22 or 23 people, I can't remember right now.

You must calculate for what $\,n\,$ you get

$\prod_{k=1}^n\left(1-\frac{k}{365}\right)\geq\frac{1}{2}$

Well, now just solve the above...(there's a way to simplify it using the binomial coefficient)

  • 0
    Ok, thanks for the comment.2012-12-28