\section{The Birthday Principle}

There are 100 students in a lecture hall.  What is the probability that
some two people share a birthday?  Maybe about $1/3$?  Let's check!  We'll
use the following two variables throughout our analysis:

\begin{itemize}

\item Let $n$ be the number of people in the group.

\item Let $d$ be the number of days in the year.

\item Let $D$ be the number of pairs of students with the same birthday.

\end{itemize}

We'll assume that a random choice of a student is made independently of
the any other choices of students.  For simplicity, we'll assume that the
probability that a randomly chosen student has a given birthday is 1/365.
This assumption is not really true, since more babies are born at certain
times of year.  However, our analysis of this problem applies to many
situations in Computer Science that are unaffected by leap days, snow days
or Spring fever, so we won't dwell on those complications.

A sensible sample space to model this experiment consists of all ways of
assigning birthdays to the people of the group.  There are $d^n$ such
assignments, since the first person can have $d$ different birthdays, the
second person can have $d$ different birthdays, and so forth.
Furthermore, every such assignment is equally probable by our assumption
that birthdays are equally likely and independent of each other.

Now the event that some two students have the same birthday can be
expressed as $[D>0]$.  It turns out to be be easier to calculate the
complement event $[D=0]$ that everyone has a distinct birthday, which is
good enough since $\pr{D>0} = 1 - \pr{D=0}$.

Anyway, the event $[D=0]$ consists of $d (d - 1) (d - 2) \cdots (d - n +
1)$ outcomes, since we can select the birthday of the first person in $d$
days, the birthday of the second person in $d - 1$ ways, and so forth.
Therefore, the probability that everyone has a different birthday is:
\begin{align*}
\pr{D=0} & = \frac{d (d - 1) (d - 2) \cdots (d - n + 1)}{d^n}.
\end{align*}
For $n=100$, this probability is actually fantastically small ---less
than one in a million!  If there are 100 people in a room, two are
almost certain to share a birthday.

Let's rewrite the right side of the preceding equation in a more
insightful form that allows us to use the fact that $e^x >1+x$ for all
$x$.\footnote{This approximation is obtained by truncating the Taylor
series $e^{-x} = 1 - x + x^2/2! - x^3/3! + \cdots$.  The approximation
$e^{-x} \approx 1 - x$ is pretty accurate when $x$ is small.}
\begin{align*}
\pr{D=0} & = \left(1 - \frac{0}{d}\right)
           \left(1 - \frac{1}{d}\right)
           \left(1 - \frac{2}{d}\right) 
           \cdots
           \left(1 - \frac{n - 1}{d}\right)\\
       & < e^0 \cdot e^{-1/d} \cdot e^{-2/d} \cdots e^{-(n-1)/d} \\
       & = e^{-\frac{\sum_{i=1}^{n-1} i}{d}}\\
       & = e^{\dfrac{-n(n-1)}{2d}} = e^{-\dfrac{\binom{n}{2}}{d}}.
\end{align*}

The exponent $\binom{n}{2}/d$ in the final expression above is close to
$1$ when $n \approx \sqrt{2d}$.  In this case, the probability that two
people share a birthday is close to $1/e$ which is roughly the break-even
point, where it's equally likely whether or not a couple of people will
share a birthday.  This leads to a rule called the \term{Birthday
Principle}, which is useful in many contexts in Computer Science:
\begin{quote}
If there are $d$ days in a year and $\sqrt{2d}$ people in a
room, then the probability that two share a birthday is about 
$1 - 1/e \approx 0.632$.
\end{quote}
For example, this principle says that if you have $\sqrt{2 \cdot 365}
\approx 27$ people in a room, then the probability that two share a
birthday is about $0.632$.  The actual probability is about $0.626$,
so the approximation is quite good.

The Birthday Principle is a great rule of thumb with surprisingly many
applications.  For example, cryptographic systems and digital signature
schemes must be hardened against ``birthday attacks''.  The principle also
tells us how many items can be inserted into a hash table before one
starts to experience collisions.

\endinput