\section{Set Theory and Probability}

Let's abstract what we've just done in this Monty Hall example into a
general mathematical definition of probability.  In the Monty Hall
example, there were only finitely many possible outcomes.  Other examples
in this course will have an infinite number of outcomes, but in each case,
the set of outcomes is \term{countable}.  This means that in any infinite
sample space, $\sspace$, the outcomes, $w$, can be numbered with
nonnegative integers, so $\sspace = set{w_n \suchthat n \in \naturals}$.

\begin{definition}
  A set, $S$, is \term{countable} iff it is finite or there is a bijection
  from $\naturals$ to $S$.
\end{definition}

General probability theory deals with uncountable sets like the set of
real numbers, but we won't need these, and sticking to countable sets lets
us avoid some distracting technical problems in set theory like the
Banach-Tarski ``paradox'' from Week 2 Notes.

\subsection{Probability Spaces}

\begin{definition}\label{LN12:sampsp}
  A countable \term{sample space}, $\sspace$, is a nonempty countable set.
  An element $w \in \sspace$ is called an \term{outcome}.  A subset of
  $\sspace$ is called an \term{event}.
\end{definition}

We won't mention the word ``countable'' again, since that's the only kind
of sample space we're going to consider.

\begin{definition}\label{LN12:probsp}
  A \hyperdef{prob}{space}{\term{probability space}} consists of a sample
  space, $\sspace$, and a function $\pr{}: \sspace\to [0,1]$, called
  the \term{probability function}, such that
\[
\sum_{w \in \sspace} \pr{w} = 1.
\]

For any event, $E \subseteq \sspace$, the \term{probability of $E$} is
defined to be the sum of the probabilities of the outcomes in $E$:
\[
\pr{E} \eqdef \sum_{w \in E} \pr{w}.
\]
\end{definition}

An immediate consequence of the definition of event probability is that
for \emph{disjoint} events, $E,F$,
\[
\pr{E \union F} = \pr{E} +\pr{F}.
\]
This generalizes to a countable number of events.  Namely, a collection of
sets is \term{pairwise disjoint} when no element is in more than one of
them --formally, $A \intersect B = \emptyset$ for all sets $A \neq B$ in
the collection.

\begin{rul*} [Sum Rule] 
  If $\set{E_0,E_1,\dots}$ is collection of pairwise disjoint events, then
\[
\pr{\lgunion_{n\in\naturals}E_n} = \sum_{n\in\naturals} \pr{E_n}.
\]
\end{rul*}

\iffalse
The Sum Rule\footnote{If you think like a Mathematician, you should be
   wondering if the infinite sum is really necessary.  Namely, suppose we
   had only used finite sums in Definition~\ref{LN12:probsp} instead of sums
   over all natural numbers.  Would this imply the result for infinite
   sums?  It's hard to find counterexamples, but there are some: it is
   possible to find a pathological ``probability'' measure on a sample
   space satisfying the Sum Rule for finite unions, in which the outcomes
   $w_0,w_1,\dots$ each have probability zero, and the probability
   assigned to any event is either zero or one!  So the infinite Sum Rule
   fails dramatically, since the whole space is of measure one, but it is
   a union of the outcomes of measure zero.

   The construction of such weird examples is beyond the scope of 6.042.  You
   can learn more about this by taking a course in Set Theory and Logic that
   covers the topic of ``ultrafilters.''}
lets us analyze a complicated event by breaking it down into simpler
cases.  For example, if the probability that a randomly chosen MIT student
is native to the United States is 60\%, to Canada is 5\%, and to Mexico is
5\%, then the probability that a random MIT student is native to North
America is 70\%.
\fi

Another consequence of the Sum Rule is that $\pr{A} + \pr{\bar{A}} = 1$,
which follows because $\pr{\sspace}=1$ and $\sspace$ is the union of the
disjoint sets $A$ and $\bar{A}$.  This equation often comes up in the form
\begin{rul*} [Complement Rule]
\[
\pr{\bar{A}}  =  1 - \pr{A}.
\]
\end{rul*}
Often the easiest way to compute the probability of an event is to compute
the probability of its complement and then apply this formula.

Some further basic facts about probability parallel facts about
cardinalities of finite sets.  In particular:
\begin{align}
\pr{B-A}        & =  \pr{B} - \pr{A \intersect B},\tag{Difference Rule}\\
\pr{A \union B} & =  \pr{A} + \pr{B} - \pr{A \intersect B},
                  \tag{Inclusion-Exclusion}\\
\pr{A \union B} & \le  \pr{A} + \pr{B}. \tag{Boole's Inequality}
\end{align}
The Difference Rule follows from the Sum Rule because $B$ is the union of
the disjoint sets $B-A$ and $A \intersect B$.  Inclusion-Exclusion then
follows from the Sum and Difference Rules, because $A \union B$ is the
union of the disjoint sets $A$ and $B-A$.  Boole's inequality is an
immediate consequence of Inclusion-Exclusion since probabilities are
nonnegative.

The two event Inclusion-Exclusion equation above generalizes to $n$ events
in the same way as the corresponding Inclusion-Exclusion rule for $n$
sets.  Boole's inequality also generalizes to
\begin{equation}
\pr{E_1 \cup \cdots \cup E_n} \leq \pr{E_1} + \cdots + \pr{E_n}.\tag{Union Bound}
\end{equation}
This simple Union Bound is actually useful in many calculations.  For
example, suppose that $E_i$ is the event that the $i$-th critical
component in a spacecraft fails.  Then $E_1 \cup \cdots \cup E_n$ is the
event that {\em some} critical component fails.  The Union Bound can give
an adequate upper bound on this vital probability.
\iffalse

Similarly, the Difference Rule implies that
\hyperdef{ln10}{monotonicity}{
\begin{equation}\label{LN12:subsetbound}
\text{If } A \subseteq B, \text{ then } \pr{A} \le \pr{B}.\tag{Monotonicity}
\end{equation}
\fi

\subsection{An Infinite Sample Space}

Suppose two players take turns flipping a fair coin.  Whoever flips
heads first is declared the winner.  What is the probability that the
first player wins?  A tree diagram for this problem is shown below:

\mfigure{!}{2in}{figures/infinite-tree1}

The event that the first player wins contains an infinite number of
outcomes, but we can still sum their probabilities:
\begin{align*}
\pr{\text{first player wins}}
    & = \frac{1}{2} + \frac{1}{8} + \frac{1}{32} + \frac{1}{128} + \cdots \\
    & = \frac{1}{2} \sum_{n=0}^\infty \paren{\frac{1}{4}}^n
    & = \frac{1}{2}\frac{1}{1-1/4} = \frac{2}{3}.
\end{align*}

Similarly, we can compute the probability that the second player wins:
\begin{align*}
\pr{\text{second player wins}}
    & = \frac{1}{4} + \frac{1}{16} + \frac{1}{64} + \frac{1}{256}
                      + \cdots \\
    & = \frac{1}{3}.
\end{align*}

To be formal about this, sample space is the infinite set
\[
\sspace \eqdef \set{\mathtt{T}^n\mathtt{H} \suchthat n \in \naturals}
\]
where $\mathtt{T}^n$ stands for a length $n$ string of $\mathtt{T}$'s.
The probability function is
\[
\pr{\mathtt{T}^n\mathtt{H}} \eqdef \frac{1}{2^{n+1}}.
\]
To verify that these define a probability space, we just have to check
that all the probabilities sum to 1.  But this follows directly from the
formula for the sum of a geometric series:
\[
\sum_{\mathtt{T}^n\mathtt{H} \in \sspace} \pr{\mathtt{T}^n\mathtt{H}} =
\sum_{n \in \naturals} \frac{1}{2^{n+1}} = \frac{1}{2}\sum_{n \in
  \naturals} \frac{1}{2^n} = 1.
\]

\iffalse
= \frac{1}{2}\sum_{n \in \naturals} \frac{1}{2^n} = \frac{1}{2}\frac{1}{1
  - 1/2}\fi

Notice that this model does not account for the possibility that both
players keep flipping tails forever.  In the diagram, flipping forever
corresponds to following the infinite path in the tree without ever
reaching a leaf.

OK, if this omission bothers you, just add another outcome,
$w_{\text{forever}}$, to model this possibility.  Of course since the
probabililities of the other outcomes already sum to 1, the probability of
of $w_{\text{forever}}$ must be defined to be 0.  Since outcomes with
probability zero will have no impact on our calculations, there's no harm
in adding in such an outcome if it makes you happier.  But since it has no
impact, there's also no harm in simply leaving it out.

The mathematical machinery we've developed is adequate to model and
analyze many interesting probability problems with infinite sample
spaces.  However, some intricate infinite processes require more
powerful (and more complex) measure-theoretic notions of probability.
For example, if we generate an infinite sequence of random bits $b_1,
b_2, b_3, \ldots$, then what is the probability that
\[
\frac{b_1}{2^1} + \frac{b_2}{2^2} + \frac{b_3}{2^3} + \cdots
\]
is a rational number?  We won't take up such problems in this book.

\endinput