\documentstyle[12pt,twoside,amsfonts,eepic,psfig]{article}
\input{macros-course}
\parskip1.5ex
\parindent0pt


\begin{document}
\handout{notes19}{Notes 19}{November 14, 1995}
\newcommand{\binom}[2]{{#1 \choose #2}}
\section{Probability and Set Theory}

Before discussing some more complicated probability problems,
let's develop some useful connections between probabiliy and
set theory.  Recall from the last lecture that

\begin{defin}
A {\em sample space} for a problem (or experiment) is a set consisting
of all possible outcomes.
\end{defin}

\begin{defin}
A {\em probability space} consists of a sample space $S$ and a
probability function $Pr : S \rightarrow \reals$, such that
\begin{enumerate}
\item For all $s \in S$, $0 \leq Pr(S) \leq 1$.
\item $\sum_{s \in S} Pr(s) = 1.$
\end{enumerate}
\end{defin}

\begin{defin}
An {\em event} is a subset of the sample space.
\end{defin}

\begin{defin}
The probability of an event $S'$ is the sum of the probabilities of
all outcomes in the event.
\end{defin}

Using these definitions, we can establish some basic facts.

\begin{theorem}
Let $A$ and $B$ be events such that $A \subseteq B$.  Then
$Pr(A) \leq Pr(B)$.
\label{thm:subset}
\end{theorem}
\begin{proof}
$$Pr(A) = \sum_{s \in A} Pr(s) \leq \sum_{s \in B} Pr(s) = Pr(B).$$
\end{proof}

For an event $A$, let $\bar{A}$ denote the {\em complement} of $A$.
\begin{theorem}
For any event $A$, $$Pr(\bar{A}) = 1 - Pr(A).$$
\label{thm:complement}
\end{theorem}
\begin{proof}
\begin{eqnarray*}
Pr(\bar{A}) + Pr(A) & = & \sum_{s \in A} Pr(s) + \sum_{s \not\in A} Pr(s) \\
& = & \sum_{s \in S} Pr(s) \\
& = & 1
\end{eqnarray*}
where the first equality follows from the definition of complementation
and the second follows from the definition of a probability space.
\end{proof}

Also this has a simple proof, often it's much easier to calculate a
probability by first calculating the probability of the complement
and then subtracting from $1$.

We can use the inclusion-exclusion principle to get probabilities of
unions.
\begin{theorem}
For any events $A$ and $B$, $Pr(A \cup B) = Pr(A) + Pr(B) - Pr(A \cap B)$.
\label{thm:union}
\end{theorem}
\begin{proof}
\begin{eqnarray*}
Pr(A \cup B) & = & \sum_{s \in A \cup B} Pr(s) \\
& = & \sum_{s \in A} Pr(s) + \sum_{s \in B} Pr(s) - 
\sum_{s \in A \cap B} Pr(s) \\
& = & Pr(A) + Pr(B) - Pr(A \cap B).
\end{eqnarray*}
\end{proof}

Sometimes it's hard to calculate the exact probabilities of unions 
and intersections.  But the advantage of a result like 
Theorem~\ref{thm:union} is that it allows us to give bounds 
on these probabilties.

\begin{corollary}[Boole's Inequality]
For any events $A$ and $B$, 
$$Pr(A \cup B) \leq Pr(A) + Pr(B).$$
\label{cor:boole}
\end{corollary}

Note that equality holds if and only if $Pr(A \cap B) = 0$.
By induction, Boole's Inequality can be easily extended to $n$
events.

\begin{theorem}
For all $n \geq 1$ and any events $A_1, \ldots, A_n$, we have
$$Pr(\cup_{i=1}^n A_i ) \leq \sum_{i=1}^n Pr(A_i).$$
\label{thm:n-union}
\end{theorem}

\begin{proof}
We prove this by induction on $n$.  
For $n = 1$, we just have $Pr(A_1) \leq Pr(A_1)$.
Now, assuming the theorem is true for $n-1$, we apply 
Boole's Inequality followed by the induction hypothesis:
\begin{eqnarray*}
Pr(\cup_{i=1}^n A_i ) \leq & \leq & Pr(\cup_{i=1}^{n-1} A_i ) + Pr(A_n) \\
& \leq & \sum_{i=1}^{n-1} Pr(A_i) + Pr(A_n) \\
& = & \sum_{i=1}^n Pr(A_i).
\end{eqnarray*}
\end{proof}

As an example, let's suppose you're wiring up a circuit.  Overall, you
are supposed to make $n$ connections, and for each connection, the
probability that it is made incorrectly is $p$.  What is the probability that
any of the connections is made incorrectly?

Well, if we let $A_i$ denote the event that connection $i$ is
made incorrectly, we are just asking for 
$Pr(\cup_{i=1}^n A_i)$.  Without knowing the relationship among
these events, we can't give an exact answer --- it could be that
messing up one connection will cause you to mess up others as well.

However, we can still gives bounds on this probability.
Using Theorem~\ref{thm:n-union}, we know
$$Pr(\cup_{i=1}^n A_i ) \leq \sum_{i=1}^n Pr(A_i) = np.$$
Also, since $A_1 \subseteq \cup_{i=1}^n A_i$, and 
$Pr(A_1) = p$, we can use Theorem~\ref{thm:subset} to conclude
$$Pr(\cup_{i=1}^n A_i ) \geq Pr(A_1) = p.$$

So for example, if $n = 10$ and $p = .01$, we get the following
bounds:
$$.01 \leq Pr(\cup_{i=1}^{10} A_i ) \leq .10.$$
Now the event that the chip gets wired correctly is the just
the complement of the event that a connection is made incorrectly;
so by Theorem~\ref{thm:complement}, the probability that the
chip gets wired correctly in this example is 
between $.9$ and $.99$.

\section{Conditional Probability}

In a lot of problems (including the one we looked at in the last
lecture), we want to consider the probability that an event $A$
happens, {\em given} that we know a certain other event $B$ has happened.
We write 
$$Pr(A \mid B)$$ 
to denote the probability of event $A$, given $B$.

There is a very simple formula for this, which can be viewed as 
follows.  Once we know that event $B$ has happened, we are in the
subset of the sample space equal to $B$.  We now want to know 
what fraction of this set consists of outcomes in $A$.
Thus,
$$Pr(A \mid B) = \frac{Pr(A \cap B)}{Pr(B)}.$$
We will take this formula as the definition of 
the {\em conditional probability of $A$ given $B$}.

Let's do an example.  Suppose a baseball team is playing
a best-2-out-of-3 series.  The probability it wins the first
game is $\frac12$.  The probability of winning a game 
following a win in the previous game is $\frac23$; the probability
of winning following a loss is only $\frac13$.

The question is: what is the probability the team wins the series
if it wins the first game?

There are actually two types of conditioning going on here:
\begin{enumerate}
\item The probability of winning a game depends on the probability
of having won the previous game.
\item We're asked for the probability of winning the series, {\em given}
that the team wins the first game.
\end{enumerate}

We solve this problem in the following step-by-step way.

\begin{enumerate}
\item Draw the sample space.  (See the figure below.)
\item Assign probabilities to the outcomes.  
These are all calculated using the same principle; let's show
we calculate the probability of the outcome (tree branch)
$WLL$.

\begin{eqnarray*}
Pr(WLL) & = & Pr({\rm Win~1st}) \cdot Pr({\rm Lose~2nd} \mid 
{\rm Win~1st}) \cdot Pr({\rm Lose~3rd} \mid {\rm Win~1st, Lose~2nd}) \\
& = & \frac12 \cdot \frac13 \cdot \frac23 \\
& = & \frac19
\end{eqnarray*}


\begin{figure}[htb]
\begin{center}

\setlength{\unitlength}{0.0075in}
%
\begingroup\makeatletter\ifx\SetFigFont\undefined
% extract first six characters in \fmtname
\def\x#1#2#3#4#5#6#7\relax{\def\x{#1#2#3#4#5#6}}%
\expandafter\x\fmtname xxxxxx\relax \def\y{splain}%
\ifx\x\y   % LaTeX or SliTeX?
\gdef\SetFigFont#1#2#3{%
  \ifnum #1<17\tiny\else \ifnum #1<20\small\else
  \ifnum #1<24\normalsize\else \ifnum #1<29\large\else
  \ifnum #1<34\Large\else \ifnum #1<41\LARGE\else
     \huge\fi\fi\fi\fi\fi\fi
  \csname #3\endcsname}%
\else
\gdef\SetFigFont#1#2#3{\begingroup
  \count@#1\relax \ifnum 25<\count@\count@25\fi
  \def\x{\endgroup\@setsize\SetFigFont{#2pt}}%
  \expandafter\x
    \csname \romannumeral\the\count@ pt\expandafter\endcsname
    \csname @\romannumeral\the\count@ pt\endcsname
  \csname #3\endcsname}%
\fi
\fi\endgroup
\begin{picture}(325,283)(0,-10)
\path(0,145)(100,205)(200,250)
\path(100,205)(200,165)(280,205)
\path(200,165)(280,125)
\path(0,145)(100,65)(200,85)(280,105)
\path(200,85)(280,65)
\path(100,65)(200,5)
\put(30,175){\makebox(0,0)[lb]{\smash{{{\SetFigFont{10}{12.0}{rm}W}}}}}
\put(30,90){\makebox(0,0)[lb]{\smash{{{\SetFigFont{10}{12.0}{rm}L}}}}}
\put(145,235){\makebox(0,0)[lb]{\smash{{{\SetFigFont{10}{12.0}{rm}W}}}}}
\put(150,165){\makebox(0,0)[lb]{\smash{{{\SetFigFont{10}{12.0}{rm}L}}}}}
\put(235,190){\makebox(0,0)[lb]{\smash{{{\SetFigFont{10}{12.0}{rm}W}}}}}
\put(240,150){\makebox(0,0)[lb]{\smash{{{\SetFigFont{10}{12.0}{rm}L}}}}}
\put(145,80){\makebox(0,0)[lb]{\smash{{{\SetFigFont{10}{12.0}{rm}W}}}}}
\put(155,35){\makebox(0,0)[lb]{\smash{{{\SetFigFont{10}{12.0}{rm}L}}}}}
\put(245,100){\makebox(0,0)[lb]{\smash{{{\SetFigFont{10}{12.0}{rm}W}}}}}
\put(250,75){\makebox(0,0)[lb]{\smash{{{\SetFigFont{10}{12.0}{rm}L}}}}}
\put(220,250){\makebox(0,0)[lb]{\smash{{{\SetFigFont{8}{9.6}{rm}1/3}}}}}
\put(215,0){\makebox(0,0)[lb]{\smash{{{\SetFigFont{8}{9.6}{rm}1/3}}}}}
\put(300,200){\makebox(0,0)[lb]{\smash{{{\SetFigFont{8}{9.6}{rm}1/18}}}}}
\put(300,125){\makebox(0,0)[lb]{\smash{{{\SetFigFont{8}{9.6}{rm}1/9}}}}}
\put(300,95){\makebox(0,0)[lb]{\smash{{{\SetFigFont{8}{9.6}{rm}1/9}}}}}
\put(300,60){\makebox(0,0)[lb]{\smash{{{\SetFigFont{8}{9.6}{rm}1/18}}}}}
\end{picture}
\end{center}
\caption{Why the Red Sox didn't make it to the World Series}
\label{fig:baseball}
\end{figure}

\item Now we identify the events.  $A$ is the event that the team
wins the series, and $B$ is the event that the team wins the first game.

\item Finally, the answer we want is $Pr(A \mid B)$.  We compute this
using the formula, and adding up the probabilities from the figure:
$$Pr(A \mid B) = \frac{Pr(A \cap B)}{Pr(B)} = 
\frac{\frac13 + \frac{1}{18}}{\frac13 + \frac19 + \frac{1}{18}} =
\frac{\frac{7}{18}}{\frac{9}{18}} = \frac79.$$

\end{enumerate}

\section{Another Example}

Conditional probability can lead to some counter-intuitive answers;
but things really do work out if you just follow the definition.
Here's a problem that always confuses people.  It's based on
calculating the probability of an event $A$, given an event $B$
that comes {\em after} it in time.  In such cases, the conditional
probability is often called the {\em a posteriori probability} ---
though it's really the same thing mathematically.

Suppose I have two coins --- one is a fair coin, which comes up heads
or tails with probability $\frac{1}{2}$ each, and the other is an 
unfair coin, which always comes up heads.  Now I choose one of the
two coins with probability $\frac12$ each, and I flip this chosen
coin once.  If it comes up heads, what is the probability that I 
picked the fair coin?

The trickiness here is that our intuitive notion of conditional 
probability does not always match the definition as 
$Pr(A \cap B) / Pr(B)$ --- in this case, the notion of
``causality'' seems to go backwards.  But in such cases, we always have
to follow the definition.

As in the previous example, we solve this problem in the following steps.
\begin{enumerate}
\item Draw the sample space.  (See the figure below.)
\item Assign probabilities to the events, again as in the previous example.
\item Define the relevant events.  Here, $A$ is the event that we choose
the fair coin, and $B$ is the event that the result is heads.
\item 
$$Pr(A \mid B) = \frac{Pr(A \cap B)}{Pr(B)} = \frac{\frac14}{\frac14 + \frac12}
= \frac13.$$
\end{enumerate}


\begin{figure}[htb]
\begin{center}

\setlength{\unitlength}{0.0075in}
%
\begingroup\makeatletter\ifx\SetFigFont\undefined
% extract first six characters in \fmtname
\def\x#1#2#3#4#5#6#7\relax{\def\x{#1#2#3#4#5#6}}%
\expandafter\x\fmtname xxxxxx\relax \def\y{splain}%
\ifx\x\y   % LaTeX or SliTeX?
\gdef\SetFigFont#1#2#3{%
  \ifnum #1<17\tiny\else \ifnum #1<20\small\else
  \ifnum #1<24\normalsize\else \ifnum #1<29\large\else
  \ifnum #1<34\Large\else \ifnum #1<41\LARGE\else
     \huge\fi\fi\fi\fi\fi\fi
  \csname #3\endcsname}%
\else
\gdef\SetFigFont#1#2#3{\begingroup
  \count@#1\relax \ifnum 25<\count@\count@25\fi
  \def\x{\endgroup\@setsize\SetFigFont{#2pt}}%
  \expandafter\x
    \csname \romannumeral\the\count@ pt\expandafter\endcsname
    \csname @\romannumeral\the\count@ pt\endcsname
  \csname #3\endcsname}%
\fi
\fi\endgroup
\begin{picture}(293,234)(0,-10)
\path(0,90)(100,170)(220,210)
\path(100,170)(220,130)
\path(0,90)(100,10)(220,10)
\put(45,105){\makebox(0,0)[lb]{\smash{{{\SetFigFont{10}{12.0}{rm}fair}}}}}
\put(50,55){\makebox(0,0)[lb]{\smash{{{\SetFigFont{10}{12.0}{rm}unfair}}}}}
\put(230,200){\makebox(0,0)[lb]{\smash{{{\SetFigFont{10}{12.0}{rm}H}}}}}
\put(230,125){\makebox(0,0)[lb]{\smash{{{\SetFigFont{10}{12.0}{rm}T}}}}}
\put(230,0){\makebox(0,0)[lb]{\smash{{{\SetFigFont{10}{12.0}{rm}H}}}}}
\put(275,200){\makebox(0,0)[lb]{\smash{{{\SetFigFont{10}{12.0}{rm}1/4}}}}}
\put(275,125){\makebox(0,0)[lb]{\smash{{{\SetFigFont{10}{12.0}{rm}1/4}}}}}
\put(275,0){\makebox(0,0)[lb]{\smash{{{\SetFigFont{10}{12.0}{rm}1/2}}}}}
\end{picture}
\end{center}
\caption{Flipping Coins}
\label{fig:coins}
\end{figure}

The key point here is that we knew the probability of picking the fair
coin was exactly $\frac12$.  Without this, we could not have
computed $Pr(A \mid B)$.


\end{document}
