There are 365 possible birthdays, ignoring leap-days.  Suppose that
there are 120 students in a lecture hall.  What is the probability
that two students have the same birthday?  50\%? 90\%? 99\%?  In fact,
the probability is greater than $99.99999997\%$!  There is less than
one chance in four billion that everyone has a different birthday!

There are two big assumptions underlying this assertion.  First, we
assume that all birthdates are equally likely.  Second, we assume that
birthdays are mutually independent.  Neither assumption is really
true.  Birthdays follow seasonal patterns and are often related to
major events.  For example, nine months after a blackout in the 70's
there was a sudden increase in the number of births in New England.
(Try counting back nine months from your birthday!)  Nevertheless,
we'll stick with these assumptions!

Suppose we perform the following experiment.  We ask one student at a
time for his or her birthday.  How many students must we ask before we
find two with the same birthday?  Surprisingly, the answer is usually
in the mid-twenties.  This seems odd!  There are 12 months in the
year.  At a point when we've only collected about two birthdays per
month, we have usually already found two students with exactly the
same birthday!

Here is the intuition.  The probability that a pair of students have
the same birthday is only $\frac{1}{365}$.  This is very small.  But
by the time we have a couple dozen birthdays, we have lots of pairs of
students!  Therefore, the probability that some pair have the same
birthday is really pretty good.

In general, suppose there are $m$ students and $N$ days in the year.
We want to determine the probability that at least two students have
the same birthday.  There are at least two good ways to solve this
problem.  We will show only one here.

\subsection*{Step 1.  Find the Sample Space}

Finding the sample space with a tree diagram is difficult.  Each
internal node will have $N$ children, and the tree will have depth
$m$.  For the values of $N$ and $m$ of interest, this tree will be huge!

We have to find the sample space a different way.  There are $N$
possible birthdays for the first student, $N$ birthdays for the second
student, and so on for all $m$ students.  In fact, we can regard an
outcome as a vector of $m$ birthdays.  The sample space is the set of
all such vectors:

\[
S = \{ <b_1, b_2, \ldots, b_m> \mid b_i \in [1, N] \mbox{ for all $i$} \}
\]

By the Product Rule for the cardinality of a product of sets, the size
of the sample space is $N^m$.

\subsection*{Step 2:  Define Events of Interest}

Let $A$ be the event that two or more students have the same birthday.
That is, event $A$ is the following set of outcomes:

\[
\{ <b_1, b_2, \ldots, b_m> \mid b_i = b_j
		\mbox{ for some distinct $i$ and $j$} \}
\]

\subsection*{Step 3:  Compute Outcome Probabilities}

The probability of outcome $<b_1, b_2, \ldots, b_m>$ is the
probability that the first student has birthday $b_1$ and the second
student has birthday $b_2$ and the third student has birthday $b_3$,
etc.  The $i$-th person has birthday $b_i$ with probability
$\frac{1}{N}$.  Since birthdates are independent, we can multiply
probabilities to get the probability of a particular outcome:

\[
\Pr(<b_1, b_2, \ldots, b_m>) = \frac{1}{N^m}
\]

In principle, we could obtain the same result from a tree diagram.
Since each students is equally likely to have any one of $N$
birthdays, independent of all other students, we would label every
edge in the tree with probability $\frac{1}{N}$.  Then we would
compute the probability of an outcome by multiplying probabilities on
the corresponding root-to-leaf path.  Since the tree has depth $m$, we
would find that every outcome has probability $\frac{1}{N^m}$, exactly
as above.

\subsubsection{Digression: Uniform Sample Spaces}

Let's digress from the analysis of the birthday problem for a bit to
discuss a nice feature that will arise in other problems.  The
remaining task in the birthday problem is to compute the probability
of event $A$.  This is particularly easy because the sample space is
{\em uniform}.

\begin{defin*}
A sample space $S$ is {\em uniform} or {\em equiprobable} if $\Pr(s)$
is the same for all $s \in S$.
\end{defin*}

This definition has the following consequence.  Since the sum of the
probabilities over all outcomes is 1, we must have $\Pr(s) =
\frac{1}{|S|}$ for all outcomes $s$ in a uniform sample space $S$.

The probability of an event in a uniform sample space is very easy to
compute.  We only need to count the number of outcomes in the event.
This amounts to counting the number of items in a set--- we know all
about that!

\begin{theorem}
\label{th:uniform}
If $A$ is an event in a uniform sample space, then

\[
\Pr(A) = \frac{|A|}{|S|}
\]
\end{theorem}

\begin{proof}
\begin{eqnarray*}
\Pr(A)	& = & \sum^{a \in A} \Pr(a) \\
	& = & \sum^{a \in A} \frac{1}{|S|} \\
	& = & \frac{|A|}{|S|}
\end{eqnarray*}

The first equation follows because the probability of an event is
defined to be the sum of the probabilities of the outcomes it
contains.  The second equation comes from the observation above that
every outcome in a uniform sample space has probability
$\frac{1}{|S|}$.  The final equation holds because the sum has $|A|$
terms.
\end{proof}

Now let's return to the birthday problem.

\subsection*{Step 4:  Compute Event Probabilities}

We want to compute the probability of $A$, the event that two or more
students have the same birthday.  Since the sample space is uniform,
we need only count the number of outcomes in the event.  This can be
done with inclusion-exclusion, but the calculation is involved.

A simpler method is to use the trick of ``counting the complement''.
Let $\bar{A}$ be the complementary event; that is, let $\bar{A} = S -
A$.  Then, since $\Pr(A) = 1 - \Pr(\bar{A})$, we are done if we can
determine the probability of event $\bar{A}$.

In the event $\bar{A}$, all students have different birthdays.  The
event consists of the following outcomes:

\[
\{ <b_1, b_2, \ldots, b_m> \mid b_i \neq b_j
		\mbox{ for all distinct $i$ and $j$} \}
\]

The notation above is a little confusing, but we have seen sets like
this before.  The set $\bar{A}$ consists of all $m$-permutations of
the set of $N$ possible birthdays!  We can now compute the probability
of event $\bar{A}$:

\begin{eqnarray*}
\Pr(\bar{A})	& = &	\frac{|\bar{A}|}{|S|} \\
		& = &	\frac{|\bar{A}|}{N^m} \\
		& = &	\frac{P(N, m)}{N^m} \\
		& = &	\frac{N!}{(N-m)! \ N^m}
\end{eqnarray*}

The first equation uses Theorem~\ref{th:uniform} to reduce the
probability problem to a counting problem.  In the second step, we
substitute in the size of the sample space $S$.  In the third step, we
use the observation that $\bar{A}$ is the set of all $m$-permutations
of an $N$-element set.  In the last step, we substitute the value of
$P(N, m)$ that we worked out a few weeks ago.

We now know $\Pr(A)$:

\[
\Pr(A) = 1 - \frac{N!}{(N-m)! \ N^m}
\]

This is the probability that at least two students in a room of $m$
have the same birthday in a year with $N$ days.

Using this formula, if we have $m = 22$ students and a year with $N =
365$ days, then at least two students have the same birthday with
probability $P(A) \approx 0.476$.  If we have $m = 23$ students, then
the probability rises to $P(A) \approx 0.507$.  Therefore, in a room
with 23 students, the odds are better than even that at least two have
the same birthday!

\section{Approximating the Answer to the Birthday Problem}

We now know that $\Pr(A) = 1 - \frac{N!}{(N-m)! \ N^m}$.  This formula
is hard to work with because it is not a closed form.  Evaluating
the expression for, say, $N = 365$ and $m = 120$ is a lot of work!

There is another reason to want a closed form.  We might want to know
how many students are needed so that at least two have the same
birthday with probability $\frac{1}{2}$.  We computed this for a year
with $N = 365$ days, but what is the answer as a function
of $N$?

\subsection{Approximating $\Pr(\bar{A})$}

Unfortunately, there is no closed form for $\Pr(A)$.  There is a nice
approximation for $\Pr(\bar{A})$ using Stirling's formula, but some
ugly math is required to find it!  Hold on tight!

\begin{eqnarray*}
\frac{N!}{(N-m)! \ N^m}
	& = &	\frac{	\sqrt{2 \pi N}
			\left( \frac{N}{e} \right)^N
			e^{a_N}		}
		     {	\sqrt{2 \pi (N-m)}
			\left( \frac{N-m}{e} \right)^{N-m}
			e^{a_{N-m}}
			N^m		} \\
	& = &	\sqrt{\frac{N}{N-m}} \ 
		\frac{	N^N
			e^{N-m}
			e^{a_N - a_{N-m}}		}
		     {	(N-m)^{N-m}
			e^N
			N^m		} \\
	& = &	\sqrt{\frac{N}{N-m}} \ 
		\frac{	e^{a_N - a_{N-m}}		}
		     {	e^m
			\left( 1 - \frac{m}{N} \right)^{N-m}
					}
\end{eqnarray*}

In the expressions above, the symbol $a_i$ denotes some value between
$\frac{1}{12i+1}$ and $\frac{1}{12i}$.  In effect, $a_i$ captures the
error in Stirling's approximation.

The last expression is useful for approximating $\Pr(\bar{A})$.
For example, substituting $N=365$ and $m=23$ gives approximately:

\begin{eqnarray*}
\Pr(\bar{A})	& = & 1.033 \ \frac{0.99998}{2.097} \\
		& = & 0.492\ldots
\end{eqnarray*}

Substituting $N=365$ and $m = 120$ gives:

\begin{eqnarray*}
\Pr(\bar{A})	& = & 1.221 \ \frac{0.99999}{5.00 \cdot 10^9} \\
		& = & 2.442 \cdot 10^{-10}
\end{eqnarray*}

The main difference between these two cases is the denominator of the
fraction.  For $m = 23$, the denominator is about 2.  For $m = 120$,
it is about 5 billion!

Since the denominator is the main term, let's try to simplify it some
more.  The first step looks arbitrary; we apply the identity $x =
e^{\ln x}$, seemingly at random:

\begin{eqnarray*}
e^m \left( 1 - \frac{m}{N} \right)^{N-m}
	& = & e^m \left( e^{\ln(1 - \frac{m}{N})} \right)^{N-m} \\
\end{eqnarray*}

The motivation for the preceding step is that there is a nice Taylor
series expansion for $\ln(1-x)$:

\[
\ln(1-x) = - x - \frac{x^2}{2} - \frac{x^3}{3} - \ldots
\]

We can now continue by replacing $\ln(1 - \frac{m}{N})$ with the
Taylor series:

\begin{eqnarray*}
e^m \left( e^{\ln(1 - \frac{m}{N})} \right)^{N-m}
	& = & e^m e^{(- \frac{m}{N} - \frac{m^2}{2N^2}
			- \frac{m^3}{3N^3} - \ldots)(N-m)} \\
	& = & e^m e^{
		(-m - \frac{m^2}{2N} - \frac{m^3}{3N^2} - \ldots) +
		(\frac{m^2}{N} + \frac{m^3}{2N^2} + \frac{m^4}{3N^3} + \ldots)
		    } \\
	& = & e^{\frac{m^2}{2N}+\frac{m^3}{6N^2}+\frac{m^4}{12N^3}+\ldots} \\
	& \geq & e^{\frac{m^2}{2N}}
\end{eqnarray*}

Now we have simplified the denominator in our expression for
$\Pr(\bar{A})$.  Substituting the simplified denominator back into
this expression gives:

\[
\Pr(\bar{A}) \leq \sqrt{\frac{N}{N-m}} \ e^{-\frac{m^2}{2N}}
\]

This is the pretty approximation we were aiming for!

\subsection{Nice Features of the Formula for $\Pr(\bar{A})$}

The formula derived above for $\Pr(\bar{A})$ has several nice
features.  First, it shows why the probability that all students have
distinct birthdays drops off so incredibly fast as the number of
students grows.  The reason is that the number of students, $m$, is
squared and then exponentiated!  Therefore $m$ has a huge effect on
the probability.

Second, this formula actually has some intuitive justification!  The number
of ways to pair $m$ students is $\binom{m}{2} \approx \frac{m^2}{2}$.
The event that a pair of students has the same birthday has
probability $\frac{1}{N}$.  {\em If these events were independent},
then the probability that no pair of students had the same birthday
would be:

\begin{eqnarray*}
\Pr(\mbox{no pair have same birthday})
	& \approx & \left( 1 - \frac{1}{N} \right)^{\frac{m^2}{2}} \\
	& \approx & e^{-\frac{1}{N} \cdot \frac{m^2}{2}} \\
	& = & e^{-\frac{m^2}{2N}}
\end{eqnarray*}

(We use the approximation $1-x \approx e^{-x}$.)

This is almost the same answer that we derived above!  Of course, this
calculation  is for intuition's sake only; it is blatantly not
correct, since we assumed that events were independent when they are
not!

\subsection{Making the Probability of a Match $\frac{1}{2}$}

A final nice feature of our approximation for $\Pr(\bar{A})$ is that
we can determine the number of students for which the probability that
two have the same birthday is $\frac{1}{2}$.

First, notice that if $m = o(N^{\frac{2}{3}})$, then our approximation
is really very good.  The reason is that the major source of error was
truncating the Taylor series for a logarithm.  The terms we threw out
were:

\[
\frac{m^3}{6N^2}+\frac{m^4}{12N^3}+\ldots
\]

Under the assumption that $m = o(N^{\frac{2}{3}})$, these terms all go
to zero as $N$ becomes large.  Furthermore, under this same assumption
the term $\sqrt{\frac{N}{N-m}}$ in our formula tends to 1 as $N$ grows
large.  Therefore, with this assumption we can conclude:

\[
\Pr(\bar{A})  \sim  e^{-\frac{m^2}{2N}}
\]

All that remains is to set the probability that all birthdays are
distinct to $\frac{1}{2}$ and solve for the number of students.

\begin{eqnarray*}
e^{-\frac{m^2}{2N}}	& \sim &	\frac{1}{2} \\
e^{\frac{m^2}{2N}}	& \sim &	2 \\
\frac{m^2}{2N}		& \sim &	\ln 2 \\
m			& \sim &	\sqrt{2 N \ln 2} \\
			& \approx &	1.177 \sqrt{N} \\
			& =	&	\Theta(\sqrt{N})
\end{eqnarray*}

We are interested in values of $m$ that are $\Theta(\sqrt{N}) =
o(N^{\frac{2}{3}})$; therefore, our earlier assumption is justified
and we can expect our approximation to be good!

For example, if $N = 365$, then $1.177 \sqrt{N} = 22.49$.  This is
consistent with out earlier calculation; we found that the probability
that at least two students have the same birthday is $\frac{1}{2}$ in
a room with around 22 or 23 students!

Of course, one has to be careful with the $\sim$ notation; we may end
up with an approximation that is only good for very large values.  In
this case, though, our approximation works well for reasonable values!

\subsection{The Birthday Principle}

The preceding result is called the Birthday Principle.  It can be
interpreted this way: if you throw about $\sqrt{N}$ balls into $N$
boxes, then there is about a 50\% chance that some box gets two balls.

For example, in 27 years there are about 10,000 days.  If we put about
$1.177 \sqrt{10,000} \approx 118$ people under the age of 28 in a
room, then there is a 50\% chance that at least two were born on
exactly the same day of the same year!

As another example, suppose we have a roomful of people.  Each person
writes a random number between 1 and a million on a piece of paper.
Even if there are only about $1.177 \sqrt{1,000,000} = 1177$ people in
the room, then there is a 50\% chance that two wrote exactly the same
number!