\documentclass[11pt]{amsart}
\usepackage{course}

\begin{document}
\lecturenotes{11}{Independence}{November 14, 2001}

\section{Independence}

\begin{definition*}
Suppose $A$ and $B$ are events in the same probability space.
Then $A$ is \emph{independent} of $B$ if:
\begin{displaymath}
  \pr{A \mid B} = \pr{A}
\end{displaymath}
\end{definition*}
In other words, that fact that event $B$ occurs does not affect the
probability that event $A$ occurs.

Figure~\ref{fig:independent} shows an arrangement of events such that
$A$ is independent of $B$.  Assume that the probability of an event is
proportional to its area in the diagram.  In this example, event $A$
occupies the same fraction of event $B$ as of event $S$, namely
$1/2$.  Therefore, the probability of event $A$ is
$1/2$ and the probability of event $A$, given event $B$, is
also $1/2$.  This implies that $A$ is independent of $B$.

\begin{figure}
  \centerline{\includegraphics[height=1.5in]{figures/independent}}
  \caption{In this diagram, event $A$ is independent of event $B$.}
  \label{fig:independent}
\end{figure}

\subsection{An Example with Coins}

Suppose we flip two fair coins.  Let $A$ be the event that the first
coin is heads, and let $B$ be the event that the second coin is heads.
Since the coins are fair, we have $\pr{A} = \pr{B} = 1/2$.  In
fact, the probability that the first coin is heads is still
$1/2$, even if we are given that the second coin is heads; the
outcome of one toss does not affect the outcome of the other.  In
symbols, $\pr{A \mid B} = 1/2$.  Since $\pr{A \mid B} =
\pr{A}$, events $A$ and $B$ are independent.

% One can draw a straightforward connection between our product rule for
% independent events and the product rule from combinatorics.
% Essentially, the produce rule applies to our probability space because
% the sample space consists of the cartesian product of the sample
% spaces for the two independent coins.

Now suppose that we glue the coins together, heads to heads.  Now each
coin still has probability $1/2$ of coming up heads; that is,
$\pr{A} = \pr{B} = 1/2$.  But if the second coin comes up
heads, then the first coin must be tails!  That is, $\pr{A \mid B} =
0$.  Now, since $\pr{A \mid B} \neq \pr{A}$, the events $A$ and $B$
are not independent. 

\subsection{Symmetry of Independence}

It turns out that independence is a symmetric relation. For this
reason, we do not have to say, ``$A$ is independent of $B$'' or vice
versa; we can just say ``$A$ and $B$ are independent''.
\begin{theorem}
  Suppose $A$ and $B$ are events in the same probability space, with
  nonzero probabilities.  If event $A$ is independent of $B$, then $B$
  is independent of $A$.
\end{theorem}

\begin{proof}
By assumption, $\pr{A \mid B} = \pr{A}$.  We must show that $\pr{B
\mid A} = \pr{B}$.
\begin{eqnarray*}
\pr{B \mid A}   & = & \frac{\pr{A \cap B}}{\pr{A}} \\
                & = & \frac{\pr{A \mid B} \cdot \pr{B}}{\pr{A}} \\
                & = & \frac{\pr{A} \cdot \pr{B}}{\pr{A}} \\
                & = & \pr{B}
\end{eqnarray*}

The first equation uses the Product Rule.  In the second equation, we
use the Product Rule again to rewrite $\pr{A \cap B}$.  The third
equation uses the assumption, $\pr{A \mid B} = \pr{A}$.  The last step
is simplification.
\end{proof}

For example, in Figure \ref{fig:independent}, $B$ occupies the same
fraction of event $A$ as of event $S$ (about $1/4$). 


\subsection{Disjoint Events vs. Independent Events}

Suppose that events $A$ and $B$ are disjoint, as shown in
Figure~\ref{fig:dependent}; that is, no outcome is in both events.  In
the diagram, we see that $\pr{A}$ is non-zero.  On the other hand:
\begin{figure}
  \centerline{\includegraphics[height=1.5in]{figures/dependent}}
  \caption{This diagram shows two disjoint events, $A$ and $B$.  Disjoint
    events are not independent!}
  \label{fig:dependent}
\end{figure}
\begin{displaymath}
  \pr{A \mid B} = \frac{\pr{A \cap B}}{\pr{B}} = 0.
\end{displaymath}
Therefore, $\pr{A \mid B} \neq \pr{A}$, and so event $A$ is not
independent of event $B$.  In general, \emph{disjoint} events are not
\emph{independent}.

\subsection{Product Rule for Independent Events}


The Product Rule says:

\[
\pr{A \cap B} = \pr{A \mid B} \cdot \pr{B} 
\]

If $A$ and $B$ are independent events, then $\pr{A \mid B} = \pr{A}$.
In this case, the Product Rule simplifies to:

\[
\pr{A \cap B} = \pr{A} \cdot \pr{B}
\]

This rule is very useful and worth remembering.  But also remember
that it only holds if $A$ and $B$ are independent events!  In fact,
many texts {\em define} two events to be independent if $\pr{A \cap B}
= \pr{A} \cdot \pr{B}$.  This is equivalent to our definition, though
we will not prove that here.

\section{Examples}

\subsection{An Experiment with Two Coins}

Suppose that we flip two independent, fair coins.  Let $A$ be the
event that the coins match; that is, both are head or both are tails.
Let $B$ the event that the first coin is heads.  Are these independent
events?

At first, the answer may appear to be ``no''.  After all, whether or
not the coins match depends on how the first coin comes up; if we toss
$HH$, then they match, but if we toss $TH$, then they do not.

The preceding observation is true, but irrelevant.  The two events
are independent if $\pr{A \mid B} = \pr{A}$, and we can prove this by
the usual procedure.
\begin{claim}
  Events $A$ and $B$ are independent.
\end{claim}

  \begin{figure}
    \centerline{\includegraphics[height=2.5in]{figures/20coinsa}}
    \caption{This is a tree diagram for the two coins experiment.}
    \label{fig:20coinsa}
  \end{figure}


\begin{proof}
  We must show that $\pr{A \mid B} = \pr{A}$.

  \emph{Step 1: Find the Sample Space.} The tree diagram in
  Figure~\ref{fig:20coinsa} shows that there are four outcomes in this
  experiment, $HH$, $TH$, $HT$, and $TT$.

  \emph{Step 2: Define Events of Interest.}  As previously defined, $A$
  is the event that the coins match, and $B$ is the event that the first
  coin is heads.  Outcomes in each event are marked in the tree diagram.
  
  \emph{Step 3: Compute Outcome Probabilities.}  Since the coins are
  independent and fair, all edge probabilities are $1/2$.  We
  find outcome probabilities by multiplying edge probabilities on each
  root-to-leaf path.  All outcomes have probability $1/4$.

  \emph{Step 4: Compute Event Probabilities.}  
  \begin{gather*}
    \pr{A \mid B} = \frac{\pr{A \cap B}}{\pr{B}}
                  = \frac{\pr{HH}}{\pr{HH} + \pr{HT}}
                  = \frac{\frac{1}{4}}{\frac{1}{4} + \frac{1}{4}}
                  = \frac{1}{2} \\
    \pr{A} = \pr{HH} + \pr{TT}
           = \frac{1}{4} + \frac{1}{4}
           = \frac{1}{2}
  \end{gather*}
  Therefore, $\pr{A \mid B} = \pr{A}$, and so $A$ and $B$ are
  independent events as claimed.
\end{proof}


\subsection{A Variation of the Two-Coin Experiment}

Now suppose that we alter the preceding experiment so that the coins are
independent, but not fair.  That is each coin is heads with
probability $p$ and tails with probability $1-p$.  Again, let $A$ be
the event that the coins match, and let $B$ the event that the first
coin is heads.  Are events $A$ and $B$ independent for all values of
$p$?

The problem is worked out with a tree diagram in
Figure~\ref{fig:20coinsb}.  The sample space and events are the same
as before, so we will not repeat steps 1 and 2 of the probability
calculation.

\begin{figure}[t]
  \centerline{\includegraphics[height=2.5in]{figures/20coinsb}}
  \caption{This is a tree diagram for a variant of the two coins
  experiment.  The coins are still independent, but no longer
  necessarily fair.}  \label{fig:20coinsb}
\end{figure}

\emph{Step 3: Compute Outcome Probabilities.} Since the coins are
independent, all edge probabilities are $p$ or $1-p$.  Outcomes
probabilities are products of edge probabilities on root-to-leaf
paths, as shown in the figure.

\emph{Step 4: Compute Event Probabilities.} We want to determine
whether $\pr{A \mid B} = \pr{A}$.
\begin{gather*}
\pr{A \mid B} = \frac{\pr{A \cap B}}{\pr{B}}
              = \frac{\pr{HH}}{\pr{HH} + \pr{HT}}
              = \frac{p^2}{p^2 + p(1-p)}
              = p \\
\pr{A} = \pr{HH} + \pr{TT} = p^2 + (1-p)^2 = 1 - 2p + 2p^2
\end{gather*}
Events $A$ and $B$ are independent only if these two probabilities are
equal:
\begin{eqnarray*}
\pr{A \mid B}   & = &   \pr{A} \\
\Leftrightarrow \quad \quad
p               & = &   1 - 2p + 2p^2 \\
\Leftrightarrow \quad \quad
0               & = &   1 - 3p + 2p^2 \\
\Leftrightarrow \quad \quad
0               & = &   (1 - 2p)(1 - p) \\
\Leftrightarrow \quad \quad
p               & = &   \frac{1}{2}, 1
\end{eqnarray*}
The two events are independent only if the coins are fair or if both
always come up heads.  Evidently, there was some dependence lurking in
the previous problem, but it was cleverly hidden by the unbiased
coins!



\subsection{Dice}

Suppose we throw two fair dice.  Is the event that the sum is equal to
a particular value independent of the event that the first throw
yields a particular value? More specifically, let $A$ be the event
that the first die turns up $3$ and $B$ the event that the sum is $6$.
Are the two events independent?

No, because
\[
\pr{B \mid A} = \frac{\pr{B \cap A}}{\pr{A}} =
\frac{\frac{1}{36}}{\frac{1}{6}} = \frac{1}{6},
\]
whereas $\pr{B} = 5/36$.

On the other hand, let $A$ be the event that the first die turns up
$3$ and $B$ the event that the sum is $7$.  Then
\[
\pr{B \mid A} = \frac{\pr{B \cap A}}{\pr{A}} =
\frac{\frac{1}{36}}{\frac{1}{6}} = \frac{1}{6},
\]
whereas $\pr{B} = 6/36$.  So in this case, the two events are
independent.

Can you explain the difference between these two results?

\section{Mutual Independence}

We have defined what it means for two events to be independent.  But
how can we talk about independence when there are more than two
events?

\subsection{Example: Blood Evidence}

During the O.\,J. Simpson trial a few years ago, a probability problem
involving independence came up.  A prosecution witness claimed that
only one in 200 Americans has the blood type found at the crime scene.
The witness then presented facts something like the following:
\begin{itemize}
\item $\cfrac{1}{10}$ of people have type $O$ blood.
\item $\cfrac{1}{5}$ of people have a positive Rh factor.
\item $\cfrac{1}{4}$ of people have another special marker.
\end{itemize}
The one in~200 figure came from multiplying these three fractions.
Was the witness reasoning correctly?

The answer depends on whether or not the three blood characteristics
are independent. This might not be true; maybe most people with $O^+$
blood have the special marker. When the math-competent defense lawyer
asked the witness whether these characteristics were independent, he
could not say. He could not justify his claim.

\subsection{Definition of Mutual Independence}

What sort of independence is needed to justify multiplying
probabilities of more than two events?  The notion we need is called
\emph{mutual independence}.
\begin{definition*}
  Events $A_1, A_2, \ldots, A_n$ are \emph{mutually independent} if for
  all $i$ such that $1 \leq i \leq n$ and for all $J \subseteq [1, n] -
  \{ i \}$, we have:
  \[
  \Pr\biggl(A_i \biggm| \bigcap_{j \in J} A_j\biggr) = \pr{A_i}
  \]
\end{definition*}
In other words, a collection of events is mutually independent if each
event is independent of the intersection of every subset of the
others. The following definition is equivalent, though we will not
prove this.
\begin{definition*}
  Events $A_1, A_2, \ldots, A_n$ are \emph{mutually independent} if for
  all $J \subseteq [1, n]$, we have:
  \[
  \Pr\biggl(\bigcap_{j \in J} A_j\biggr) = \prod_{j \in J} \pr{A_j}
  \]
\end{definition*}
Like the general form of the Inclusion-Exclusion principle, these
general definitions of mutual independence are a bit tricky.  The
following special case of the second definition may be easier to
understand. 
\begin{definition*}
Three events $A_1$, $A_2$, $A_3$ are mutually independent if all of
the following hold:
\begin{eqnarray*}
\pr{A_1 \cap A_2} & = & \pr{A_1} \cdot \pr{A_2} \\
\pr{A_1 \cap A_3} & = & \pr{A_1} \cdot \pr{A_3} \\
\pr{A_2 \cap A_3} & = & \pr{A_2} \cdot \pr{A_3} \\
\pr{A_1 \cap A_2 \cap A_3} & = & \pr{A_1} \cdot \pr{A_2} \cdot \pr{A_3}
\end{eqnarray*}
\end{definition*}
In the blood example, if the three blood characteristics were known to
be mutually independent, then the witness was justified in multiplying
probabilities by the fourth equality above.

\textbf{Important:} To prove a set of three or more events mutually
independent, it is \emph{not} sufficient to prove every pair of events
independent!  In particular, for three events we must also prove that
the fourth equality also holds.

\subsection{Carnival Dice Revisited}

Remember the gambling game Carnival Dice from the previous lecture. A
player picks a number between 1 and 6 and then rolls three fair dice.
The player wins if his number comes up on at least one die. The
player loses if his number does not appear on any of the dice. What
is the probability that the player wins?

Let $A_i$ be the event that the $i$-th die matches the player's guess.
We are interested in $\pr{A_1 \cup A_2 \cup A_3}$. In the previous
lecture, we computed this probability using inclusion\slash exclusion,
but now that we know about independence, we can also compute it as
\begin{displaymath}
  \pr{A_1 \cup A_2 \cup A_3} =
  1 - \pr{\overline{A_1 \cup A_2 \cup A_3}} =
  1 - \pr{\overline{A_1} \cap \overline{A_2} \cap \overline{A_3}}.
\end{displaymath}
Since the dice are independent,
\begin{displaymath}
  \pr{\overline{A_1} \cap \overline{A_2} \cap \overline{A_3}} =
  \pr{\overline{A_1}} \pr{\overline{A_2}} \pr{\overline{A_3}} =
  \bigl(5/6)^3,
\end{displaymath}
and therefore
\begin{displaymath}
  \pr{A_1 \cup A_2 \cup A_3} =
  1 - \bigl(5/6)^3 =
  91 / 216 \approx 42\%.
\end{displaymath}
When having independent events, the above path is often easier than
using inclusion\slash exclusion. Note that the above approach
generalizes nicely to a larger number of dice, with 6~dice the
probability of a match is $1 - \bigl(5/6)^6 \approx 67\%$, with
12~dice it is $1 - \bigl(5/6)^{12} \approx 89\%$. Using
inclusion\slash exclusion in these cases would have been messy.

\subsection{A Red Sox Streak}

The Boston Red Sox baseball team has lost 14 consecutive playoff
games.  What are the odds of such a miserable streak?

Suppose that we assume that the Sox have a $1/2$ chance of
winning each game and that the game results are mutually independent.
Then we can compute the probability of losing 14 straight games as
follows.  Let $L_i$ be the event that the Sox lose the $i$-th game.
This gives:

\begin{eqnarray*}
\pr{L_1 \cap L_2 \cap \ldots \cap L_{14}}
        & = & \pr{L_1} \pr{L_2} \cdot \ldots \pr{L_{14}} \\
        & = & \left( \frac{1}{2} \right)^{14} \\
        & = & \frac{1}{16,384}
\end{eqnarray*}

The first equation follows from the second definition of mutual
independence.  The remaining steps use only substitution and
simplification.

These are pretty long odds; of course, the probability that the Red
Sox lose a playoff game may be greater than $1/2$.  Maybe
they're cursed.

\subsection{An Experiment with Three Coins}

This is a tricky problem that always confuses people!  Suppose that we
flip three fair coins and that the results are mutually independent.
Define the following events:
\begin{itemize}
\item $A_1$ is the event that coin 1 matches coin 2
\item $A_2$ is the event that coin 2 matches coin 3
\item $A_3$ is the event that coin 3 matches coin 1
\end{itemize}
Are these three events mutually independent?

For once, we will dispense with the tree diagram.  The sample space is
easy enough to find anyway; there are eight outcomes, corresponding to
every possible sequence of three flips: $HHH$, $HHT$, $HTH$, $\ldots$.
We are interested in events $A_1$, $A_2$, and $A_3$, defined as above.
Each outcome has probability $1/8$.

To prove that the three events are mutually independent, we must prove
a sequence of equalities.  It will be helpful first to compute the
probability of each event $A_i$:
\begin{eqnarray*}
\pr{A_1} & = & \pr{HHH} + \pr{HHT} + \pr{TTT} + \pr{TTH} \\
         & = & \frac{1}{8} + \frac{1}{8} + \frac{1}{8} + \frac{1}{8}\\
         & = & \frac{1}{2}
\end{eqnarray*}
By symmetry, $\pr{A_2} = \pr{A_3} = 1/2$.  Now we can begin
checking all the equalities required for mutual independence.
\begin{eqnarray*}
\pr{A_1 \cap A_2}       & = & \pr{HHH} + \pr{TTT} \\
                        & = & \frac{1}{8} + \frac{1}{8} \\
                        & = & \frac{1}{4} \\
                        & = & \frac{1}{2} \cdot \frac{1}{2}\\
                        & = & \pr{A_1} \pr{A_2}
\end{eqnarray*}
By symmetry, $\pr{A_1 \cap A_3} = \pr{A_1} \pr{A_3}$ and $\pr{A_2 \cap
A_3} = \pr{A_2} \pr{A_3}$ must hold as well.  We have now proven that
every pair of events is independent.  But this is not enough to prove
that $A_1$, $A_2$, and $A_3$ are mutually independent!  We must check
the fourth condition:
\begin{eqnarray*}
\pr{A_1 \cap A_2 \cap A_3}      & = & \pr{HHH} + \pr{TTT} \\
                                & = & \frac{1}{8} + \frac{1}{8} \\
                                & = & \frac{1}{4} \\
                                & \neq & \pr{A_1} \pr{A_2} \pr{A_3} = \frac{1}{8}.
\end{eqnarray*}
The three events $A_1$, $A_2$, and $A_3$ are not mutually independent,
even though all pairs of events are independent!  When proving a set
of events independent, remember to check all pairs of events,
\emph{and} all sets of three events, four events, etc.

\subsection{Pairwise Independence}

Suppose we have a set of events.  We know that all pairs of events are
independent, but we know nothing about the independence of subsets of
three or more events.  This situation arises often enough that 
a special term has been defined for it:
\begin{definition*}
  Events $A_1, A_2, \ldots A_n$ are \emph{pairwise independent} if
  $A_i$ and $A_j$ are independent events for all $i \neq j$.
\end{definition*}
Note that mutual independence is stronger than pairwise independence.
That is, if a set of events is mutually independent, then it must be
pairwise independent, but the reverse is not true.  For example, the
events in the three coin experiment of the preceding subsection were
pairwise independent, but not mutually independent.

In the blood example, suppose initially that we know nothing about
independence.  Then we can only say that the probability that a person
has all three blood factors is no greater than the probability that a
person has blood type $O$, which is $1/10$.

If we know that the three blood factors in the O.\,J. case appear
pairwise independently, then we can conclude:
\begin{eqnarray*}
\pr{\mbox{person has all 3 factors}}
        & \leq & \pr{\mbox{person is type $O$ and Rh positive}} \\
        & = & \pr{\mbox{person is type $O$}}
              \pr{\mbox{person is Rh positive}} \\
        & = & \frac{1}{10} \cdot \frac{1}{5} \\
        & = & \frac{1}{50}
\end{eqnarray*}
Knowing that a set of events is pairwise independent is useful!

However, if all three factors are mutually independent, then the
witness is right; the probability a person has all three factors is
$1/200$.

The point is that we get progressively tighter upper bounds as we
strengthen our assumption about independence.

\section{Circuit Failure}

Suppose you are wiring up a circuit containing a total of
$n$~connections. From past experience we assume that any particular
connection is made \emph{incorrectly} with probability~$p$, for some $0
\leq p \leq 1$.  That is, for $1 \leq i \leq n$,
\begin{displaymath}
  \pr{\mbox{$i^{th}$ connection is wrong}} = p.
\end{displaymath}
What can we say about the probability that the circuit is wired
correctly, \ie, that it contains no incorrect connections?
 
Let $A_i$ denote the event that connection~$i$ is made
\emph{correctly}.  Then $\bar{A_i}$ is the event that connection~$i$
is made incorrectly, so $\pr{\bar{A_i}} = p$.  Now 
\begin{displaymath}
  \pr{\mbox{all connections are OK}} = \pr{\cap_{i=1}^n A_i}.
\end{displaymath}

Without any additional assumptions, we can't get an exact answer.
However, we can give reasonable upper and lower bounds. For an upper
bound, we can see that
\begin{displaymath}
  \pr{\bigcap_{i=1}^n A_i} =
  \pr{A_1 \cap (\bigcap_{i=2}^n A_i)} \leq
  \pr{A_1} = 1 - p.
\end{displaymath}
For a lower bound, we can see that
\begin{displaymath}
  \pr{\bigcap_{i=1}^n A_i}
  = 1 - \pr{\overline{\bigcap_{i=1}^n A_i}}
  = 1 - \pr{\bigcup_{i=1}^n \bar{A_i}}
  \geq 1 - \sum_{i=1}^n \pr{\bar{A_i}} = 1 - np.
\end{displaymath}
So for example, if $n = 10$ and $p = 0.01$, we get the following
bounds:
\begin{displaymath}
  0.9 = 1 - 10\cdot 0.01
  \leq \pr{\mbox{all connections are OK}} \leq
  1-0.01 = 0.99.
\end{displaymath}
So we have concluded that the chance that all connections are okay is
somewhere between 90\% and 99\%. Could it actually be as high as
99\%?  Yes, if the errors occur in such a way that whenever you make
one connection wrong, all the connections are wrong. And if you make
one connection correctly, all the connections are correct.

Could it be 90\%? Yes, suppose the errors are such that we never make
two wrong connections. In other words, the events $\overline{A_i}$ are
all disjoint and the probability of getting it right is
\begin{displaymath}
  \pr{\cap A_i}  =  1 - \pr{\cup \overline{A_i}}
  = 1 - \sum_{i=1}^{10} \pr{\overline{A_i}} = 1-10\cdot 0.01 = 0.9.
\end{displaymath}

% \subsection{Circuit Failure Revisited}

% Let's reconsider the circuit problem mentioned earlier in these notes,
% involving wiring up a circuit containing $n$ connections,
% where the probability that each particular connection is made 
% \emph{incorrectly}, $\pr{\bar{A_i}}$, is $p$.
% Again, we want to know the probability that the entire circuit is
% wired correctly.

What if we know that all the events $A_i$ are mutually independent?

Now we can calculate the exact probability that the circuit is
correct: $(1-p)^n$.  For $n = 10$, and $p = 0.01$ as above, this comes
out to around 90.4\% Very close to the lower bound.  That's because
the chance of more than one error is relatively small (less than 1\%).

% I get 1 - 90.4 - 10 (.99)^9 (.01), = ...



\section{The Birthday Problem}

Most people expect that, if the same experiment is repeated over and
over again, independently, the results are likely to be very varied.
However, some patterns are actually pretty likely.

\subsection{The Problem}

There are 365 possible birthdays, ignoring leap-days, and there are
100 students in the lecture hall.  What is the probability that two
students have the same birthday?  50\%? 90\%? 99\%?  In fact, the
probability is greater than $99.999969\%$!  There is less than one
chance in thirty million 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 $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{Solution}

\subsubsection*{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$.

\subsubsection*{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$} \}
\]

\subsubsection*{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
$\cfrac{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}
\]
Notice that we have a uniform probability space---the probabilities of
all the outcomes are the same.

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 $\cfrac{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 $\cfrac{1}{N^m}$, exactly
as above.

\subsubsection*{Step 4:  Compute Event Probabilities}

The remaining task in the birthday problem is 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}$:
\[
\pr{\bar{A}} = \frac{|\bar{A}|}{|S|} = \frac{|\bar{A}|}{N^m} = \frac{P(N,
m)}{N^m} = \frac{N!}{(N-m)! \ N^m}.
\]

Because we have a uniform sample space, we can reduce the probability
problem to a counting problem in the first step.  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!

\subsection{Approximating the Answer to the Birthday Problem}

We now know that $\pr{A} = 1 - \cfrac{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 = 100$ 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 $1/2$.  We computed this for a year
with $N = 365$ days, but what is the answer as a function
of $N$?

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
$\cfrac{1}{12i+1}$ and $\cfrac{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{displaymath}
  \pr{\bar{A}}  = 1.033 \ \frac{0.99998}{2.097} = 0.492\ldots
\end{displaymath}
Substituting $N=365$ and $m = 100$ gives:
\begin{displaymath}
  \pr{\bar{A}} = 1.174 \ \frac{0.99991}{3.82 \cdot 10^6} = 3.073 \cdot 10^{-7}
%  \pr{\bar{A}} = 1.221 \ \frac{0.99999}{5.00 \cdot 10^9} = 2.442 \cdot 10^{-10}
\end{displaymath}
The main difference between these two cases is the denominator of the
fraction.  For $m = 23$, the denominator is about 2.  For $m = 100$,
it is almost 4 million!

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 - \cfrac{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 Approximation}

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 $\dbinom{m}{2} \approx \cfrac{m^2}{2}$.
The event that a pair of students has the same birthday has
probability $\cfrac{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 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 (approximately) $1 / 2$.

First, notice that if $m = o(N^{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^{2/3})$, these terms all go
to zero as $N$ becomes large.  Furthermore, under this same assumption
the term
\[
\sqrt{\frac{N}{N-m}} = \sqrt{\frac{1}{1-m/N}}
\]
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 $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} \\
m                        & =  &   \Theta(\sqrt{N})
\end{eqnarray*}
We are interested in values of $m$ that are $\Theta(\sqrt{N}) =
o(N^{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 $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!

\end{document}
