\documentclass[12pt]{6042}
%\usepackage{eepic}
\usepackage{psfig}

%\documentstyle[12pt,twoside,amsfonts,amstex,psfig]{article}

%\raggedbottom

%\input{macros-course}

\newcommand{\recn}[3]
{\setcounter{problemsetnum}{#1}
\handout{rec#1}{Notes for Recitation #1 (#2/98)}{#3}
}

\newcommand{\numb}[1]{\#\text{#1}}
\let\union\cup
\let\intersect\cap

\let\Union\bigcup
\let\Intersect\bigcap

\begin{document}

\recn{10}{4/17}{April 15, 1998}


\section{A Dice Problem}

There is a game involving three dice and two players.  The dice are
not normal; rather, they are numbered as shown in
Figure~\ref{fig:dice}.  Each hidden face has the same number as the
opposite, exposed face.  As a result, each die has only three distinct
numbers, and each number comes up $\frac{1}{3}$ of the time.

\begin{figure}[htbp]
\centerline{\psfig{figure=figures/dice.eps,height=1.5in}}
\caption{\em This figure shows the strange numbering of the three dice
in the Dice Problem.  The number on each concealed face is the same as
the number on the exposed, opposite face.}
\label{fig:dice}
\end{figure}

In the game, the first player can choose any one of the three dice.  Then
the second player chooses one of the two remaining dice.  They both
roll and the player with the higher number wins.  Which of the three
dice should player one choose?  That is, which of the three dice is
best?

For example, die B is attractive, because it has a 9, the highest
number overall; on the other hand, it also has a 1, the lowest number.
Intuition gives no clear answer!  We can solve the problem with the
same four-step method used in the Monty Hall problem.

\begin{claim}
Die A beats die B more than half of the time.
\end{claim}

\begin{proof}
The claim concerns the experiment of throwing dice A and B.

{\em Step 1: Find the Sample Space. } The sample space for this
experiment is indicated by the tree diagram in
Figure~\ref{fig:diceAB}.

{\em Step 2: Define Events of Interest. } We are interested in the
event that die A comes up greater than die B.  The outcomes in
this event are marked ``A'' in the figure.

{\em Step 3: Compute Outcome Probabilities. } To find outcome
probabilities, we first assign probabilities to edges in the tree
diagram.  Each number comes up with probability $\frac{1}{3}$,
regardless of the value of the other die.  Therefore, we assign all
edges probability $\frac{1}{3}$.  The probability of an outcome is the
product of probabilities on the corresponding root-to-leaf path; this
means that every outcome has probability $\frac{1}{9}$.

{\em Step 4: Compute Event Probabilities. } The probability of an
event is the sum of the probabilities of the outcomes in the event.
Therefore, the probability that die A comes up greater than die
B is $\frac{1}{9} + \frac{1}{9} + \frac{1}{9} + \frac{1}{9} +
\frac{1}{9} = \frac{5}{9}$.

As claimed, the probability that die A beats die B is greater than
half.

\begin{figure}[htbp]
\centerline{\psfig{figure=figures/diceAB.eps,height=2.0in}}
\caption{\em This is the tree diagram arising when die A is played
against die B.  Die A beats die B with probability $\frac{5}{9}$.}
\label{fig:diceAB}
\end{figure}
\end{proof}


\begin{figure}[htbp]
\centerline{\psfig{figure=figures/diceBC.eps,height=2.0in}}
\caption{\em Die B beats die C with probability $\frac{5}{9}$.}
\label{fig:diceBC}
\end{figure}


\begin{figure}[htbp]
\centerline{\psfig{figure=figures/diceCA.eps,height=2.0in}}
\caption{\em Die C beats die A with probability $\frac{5}{9}$.  Amazing!}
\label{fig:diceCA}
\end{figure}

\begin{claim}
Die B beats die C more than half of the time.
\end{claim}

\begin{proof}
See the tree diagram in Figure~\ref{fig:diceBC}; the proof is the same
as for the preceding claim.

\end{proof}

We have shown that A beats B and that B beats C.  From these
results, we might conclude that A is the best die, B is second
best, and C is worst.  But this is totally wrong!

\begin{claim}
Die C beats die A more than half of the time!
\end{claim}

\begin{proof}
See the tree diagram in Figure~\ref{fig:diceCA}.
\end{proof}

Die A beats B, B beats C, and C beats A!  Clearly,
there is no ``transitive law'' here!  This means that no matter what
die the first player chooses, the second player can choose a die that
beats it with probability $\frac{5}{9}$.  The player who picks first is
always at a disadvantage!


\section{Set Theoretic Identities}
\textbf{Review}: in lecture we showed
\[\pr{A \union B} = \pr{A} + \pr{B} \mbox{ for disjoint } A,B.\]
This first fact generalizes to any countable union:
\[\pr{\Union_n A_n} =  \sum_n\pr{A_n} \mbox{ for pairwise disjoint } A_n.\]

We also showed
\begin{eqnarray}
\pr{A-B} & = & \pr{A} - \pr{A \intersect B}, \mbox{ so} \label{a-b}\\
\pr{A \intersect B} & \le & \pr{A}, \label{ab<a}\\
\pr{\overline{B}} & = & 1 - \pr{B}, \label{1-b}\\
\pr{A \union B} & = & \pr{A} + \pr{B} - \pr{A \intersect B}, \mbox{ so}\\
\pr{A \union B} & \le & \pr{A} + \pr{B}.
\end{eqnarray}

The last fact is known as \emph{Boole's Inequality}, where equality holds
if and only if $Pr(A \intersect B) = 0$.  Boole's Inequality can also be
extended to any countable number of events:

\begin{theorem}[Boole's Inequality]\label{bool}
$\pr{\Union_n A_n} \leq \sum_n \pr{A_n}$.
\label{thm:n-union}
\end{theorem}
\begin{proof}
Note that
\[\sum_{p \in \Union_n A_n}\pr{p} \le \sum_n\sum_{p \in A_n}\pr{p}\]
because every term in the sum on the lefthand side occurs on the righthand
side.  But the lefthand side is $\pr{\Union_n A_n}$ by definition, and the
righthand side is $\sum_n \pr{A_n}$.
\end{proof}

\begin{corollary}
$\pr{\Intersect_n A_n} \ge 1 - \sum_n \pr{\overline{A_n}}$.
\begin{proof}

\[\begin{array}{rcll}
\pr{\Intersect_n A_n} & = & 1 - \pr{\overline{\Intersect_n A_n}}
            & \mbox{by equation~(\ref{1-b})}\\
&=& 1 - \pr{\Union_n \overline{A_n}} & \mbox{by DeMorgan's Law}\\
&\ge & 1 - \sum_n \pr{\overline{A_n}} & \mbox{by Boole's Inequality}.
\end{array}\]
\end{proof}

\end{corollary}


\subsection{Wiring circuits}
As an example, let us suppose you are wiring up a circuit.  There are a
total of $n$ connections to be made.  From past experience we assume that 
any particular connection is made {\em incorrectly} 
with probability $p$, for some $0 \leq p \leq 1$.  That is, for $1 \le i
\le n$,
\[\pr{\mbox{$i^{th}$ connection is wrong}} = p.\]
What is the probability that the circuit is wired correctly, i.e., there
are no incorrect connections?
 
Let $A_i$ denote the event that connection $i$ is
made \emph{correctly}.  Then $\overline{A_i}$ is the event that connection
$i$ is made incorrectly, so $\pr{\overline{A_i}} = p$.  Now
\[\pr{\mbox{all connections are OK}} = \pr{\Intersect_{i=1}^n A_i} \ge 1 -
\sum_{i=1}^n \pr{\overline{A_i}} = 1-np.\]

What about an upper bound?  By equation~(\ref{ab<a}),
\[\pr{\mbox{all connections are OK}} = \pr{\Intersect_{i=1}^n A_i} \le
\pr{A_1} = 1-p.\]

So for example, if $n = 10$ and $p = 0.01$, we get the following
bounds:
\[0.9 = 1 - 10\cdot 0.01 \le \pr{\mbox{all connections are OK}} = \le 1-0.01 = 0.99.\]

So we have concluded that the chance that all connections are okay is
somwhere between 90\% and 99\%.  Although we don't have enough information
to calculate the probability of individual sample points, we were able to
conclude something useful by using simple facts from set theory.

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.  Formally, the sample space could consist of two atomic events, one
corresponding to ``all OK'' with probability $99/100$ and one with
corresponding to ``none OK'' with probability $1/100$.  Then $A_1
= A_2 = \ldots = A_{10} = \Intersect_{i=1}^{10}A_i$, so
$\pr{\mbox{all OK}} = \pr{A_i} = 0.99$.

\textbf{Class Exercise}:  A more natural sample space might be
\[
    S ::= \set{0,1}^{10}
\]
where each point $s::=(b_1,b_2,\ldots,b_{10})$ describes the bad set of
connections in a circuit: $b_i= 0$ if the $i$th connection is bad and
$b_i = 1$ if it is OK.  Now what is $A_1$?  Is it equal to $A_2$?
How might we assign probabilities to the points in
$S$ so $\pr{\mbox{all OK}} = \pr{A_1} = 0.99$?

\textbf{Solution}:
$A_i = \set{(b_1,\dots,b_{10}) \in S : b_i = 1}$, so $A_1\neq A_2$.
$\pr{1^{10}}=0.99,\ \pr{0^{10}}=0.01$, and probability of all other points
is zero.

\medskip

Could it be 90\% ?  Yes, suppose the errors are such that we never make
two wrong connections.  So the events $\overline{A_i}$ are all disjoint and the
probability of getting it right is
\[
\pr{\Intersect A_i}  =  1 - \pr{\Union \overline{A_i}}
     = 1 - \sum_{i=1}^{10} \pr{\overline{A_i}} = 1-10\cdot 0.01 = 0.9.
\]

\textbf{Class Exercise}: How might we assign probabilities to the points
in $S$ above so $\pr{\mbox{all OK}} = 0.9$ but $\pr{A_i} = 0.99$?

\textbf{Solution}: $\pr{s}=0.01$ if $s$ contains 9 zeroes and 1 one,
$\pr{1^{10}}=0.9$, and probability of all other points is zero.

\medskip

\subsection{The Nontransitive Dice Again}
The three dice A, B, C had the property that on any roll of dice A and B,
the probability that A beats B is 5/9, on a roll of B and C the
probability that B beats C is 5/9, and likewise on a roll of C and A, the
probability that C beats A is 5/9.  How high can we make this probability?
That is, can we construct dice so that the probability of A beating B, B
beating C, C beating A are all arbitrarily high? --- say 3/4 each?

To answer this, let's roll all three dice.  Define $A$ to be the event
that A beats B, $B$ the event that B beats C and $C$ the event that C
beats A.
\begin{theorem}
\[\min \set{\pr{A}, \pr{B}, \pr{C}} \leq \frac{2}{3}.\]
\end{theorem}

\begin{proof}
\[\begin{array}{rcll}
\pr{A \intersect B \intersect C}
    & = & 1 - \pr{\overline{A} \union \overline{B} \union \overline{C}} 
          & \mbox{by equation~\ref{1-b} and DeMorgan}\\
    & \geq & 1 - (\pr{\overline{A}}+ \pr{\overline{B}} + \pr{\overline{C}}
                & \mbox{by Boole's Inequality}\\
    & = & \pr{A} + \pr{B} + \pr{C}) - 2 & \mbox{by equation~\ref{1-b}}.
\end{array}\]
But $\pr{A \intersect B \intersect C} = 0$,
since it is impossible that on any single roll, die A is higher than die B,
\emph{and} B is higher than C, {\em and} C is higher than A.
Hence
\[2  \geq  \pr{A} + \pr{B} + \pr{C} \geq 3 \min \set{\pr{A},\pr{B},\pr{C}}\]
and therefore
\[2/3 \geq \min \set{\pr{A}, \pr{B}, \pr{C}}.\]
\end{proof}

\textbf{Extra Credit Problem}: Show that the 2/3 bound can be improved to $p
= (\sqrt{5} - 1)/2 = 0.618\ldots$, and that this is the minimum bound.

\section{Conditional probability and Bayes rule}
Recall the formula for conditional
probability:
\[
    \pr{A \mid B} = \frac{\pr{A \intersect B}}{\pr{B}}
\]

As an example, consider rolling two dice. 
What is the probability of having rolled at
least one 3, given that total of the two dice is 8? 

Assume each die gives each outcome (i.e., 1,2,3,4,5, or 6) with probability
1/6, no matter what the outcome of the other die is.
Let $A$ be the event that
total seen is 8, and let $B$ be the event that at least one 3 has
been rolled. The sample space is $S=\set{(i,j) : i,j \in
\set{1,2,3,4,5,6}\, }$, so that $\card{S}=36$.
\[
A = \set{(2,6),(3,5),(4,4),(5,3),(6,2)}, \quad
B\intersect A = \set{(3,5),(5,3)},
\]
Each outcome has probability 1/36,
so $\pr{A} = 5/36$ and $\pr{B\intersect A} = 2/36$. Therefore $\pr{B|A} =
\frac{2/36}{5/36} = 2/5$.

Are $\pr{A|B}$ and $\pr{B|A}$ related? Yes, both relate to $\pr{A\intersect B}$:
\[
\pr{A|B} = \frac{\pr{A\intersect B}}{\pr{B}}, \mbox{ and }
\pr{B|A} = \frac{\pr{B\intersect A}}{\pr{A}},
\]
so
\[
\pr{A|B}\pr{B} = \pr{A\intersect B} = \pr{B|A}\pr{A}.
\]
This yields the famous {\em Bayes Rule:}
\[
\pr{A|B} = \frac{\pr{B|A}}{\pr{B}} \pr{A}.
\]

{\em Example: } At a school 40\% of students are male, and 60\% of males
and 80\% of all students play sports. What is the probability that a
randomly chosen student is a male, given that the student plays sports?

Let $A$ be the event that a student is male.  Let $B$ be the event that a
student plays sports.  We are given $P(A) = 40\%$, $P(B)=80\%$ and
$\pr{B|A}=60\%$. We want to compute $\pr{A|B}$. By Bayes Rule
\[
\pr{A|B} = \frac{\pr{B|A}}{P(B)} \pr{A} = \frac{0.6\times 0.4}{0.8} = 30\%{.}
\]


\section{Team Problem}

\begin{problems}

\problem Verify that the set-theoretic probability equations above
``relativize'' to conditional probabilities, e.g., equation~(\ref{a-b})
relativizes to
\[\pr{A-B\mid C}  =  \pr{A \mid C} - \pr{A \intersect B \mid C}.\]


\problem
In the OJ Simpson trial it was claimed by the defense that the fact that
Simpson battered his wife should be excluded from the evidence as the fraction
of wife batterers that murder their wives is $1/2000$ (Dershowitz Lemma).
In this problem we will condition this probability on the event that Nicole is 
dead and see that we obtain a somewhat different result.

We have the following statistical information (all for 1994):
\begin{itemize}

\item number of women = 125M
\item number of women murdered in 1994 = 6000
\item number of women murdered by spouse in 1994 = 1500
\item number of women with spouse in 1994 = 50M
\item number of women battered by spouse in 1994 = 3M
\end{itemize}

Being murdered counts as being battered. Also, we assume that 
the event of being murdered by
somebody else is not influenced by whether the woman was being battered or not.

Define the events

$S$ = Woman is murdered by spouse  \\
$M$ = Woman is murdered \\
$B$ = Woman is battered by spouse \\

Use the given information to evaluate the following

\bparts

\ppart  The Dershowitz Lemma can be reformulated as
\[\pr{S \mid B} = 1/2000.\]
Prove it.

\ppart Calculate $\pr{S \mid M}$, i.e., the probability that a murdered
woman was done in by her spouse.

\ppart Calculate $\pr{S \mid B \intersect M}$, i.e., the probability that
a battered, murdered woman is done in by her spouse.

\ppart What can you conclude about Dershowitz' argument that the battery
of a spouse should not be admitted as evidence because of his lemma ?

\eparts

\textbf{Solution:}
\[\pr{S \mid B}= \frac{\pr{S \intersect
B}}{\pr{B}}=\frac{\pr{S}}{\pr{B}}=\frac{1500/125M}{3M/125M}=\frac{1500}{3M}=1/2000.\]

\[\pr{S \mid M}= \frac{\pr{S \intersect M}}{\pr{M}}=\frac{\pr{S}}{\pr{M}}=\frac{1500/125M}{6000/125M}=\frac{1500}{6000}=1/4.\]

Next, note that
\[\pr{S \mid B \intersect M} = \frac{\pr{S \intersect B \intersect M}}{\pr{B \intersect M}} = \frac{\pr{S}}{\pr{M \mid B} \pr{B}}.\]

Then to evaluate $\pr{M \mid B}$, we use the following fact from the
previous problem:
\begin{eqnarray*}
\pr{M \mid B} & = & \pr{M \intersect S \mid B} + \pr{M \intersect \bar{S} \mid B}\\
& = & \pr{S \mid B} + \pr{M \intersect \bar{S}}.
\end{eqnarray*}
In simplifying the second term we used the fact that being murdered by
someone other than the spouse is not influenced by whether the victim was
battered by her spouse or not, namely,
\[\pr{M \intersect \bar{S} \mid B} = \pr{M \intersect \bar{S}}.\]

Now we have
\begin{eqnarray*}
\pr{S \mid B \intersect M} & = & \frac{1500 / 125M}{(\frac{1}{2000} +
\frac{6000- 1500}{125M})\frac{3M}{125M}}\\
& = & \frac{1500 \times 125}{67000 \times 3}\\
 & = & \frac{125}{134}\  =\  0.93.
\end{eqnarray*}

\end{problems}

\end{document}

