\documentclass[11pt]{article}
%\usepackage{eepic}
\usepackage{psfig}
\usepackage{amsmath}
%\usepackage{graphics}
%\usepackage{eepic}
\input{macros-course}

\newcommand{\intersect}{\cap}
\newcommand{\union}{\cup}
\newcommand{\Union}{\bigcup}
\newcommand{\Intersect}{\bigcap}

%\newcommand{\solution}[1]{}
\newcommand{\solution}[1]{\textbf{Solution}: \quad #1}


\begin{document}

\tutn{10}{4/15/99}{April 14, 1999}

\section{Identities and Inequalities}

\subsection{Sum Rule and Boole's Inequality}
\textbf{Review}: In lecture we showed
\begin{theorem}
\emph{Sum Rule for two events}
\[\pr{A \union B} = \pr{A} + \pr{B}\]
for all disjoint events $A,B$.
\end{theorem}

This first fact generalizes easily to any countable union:
\begin{theorem}\emph{Sum Rule for Events}
\[\pr{\Union_{n=0}^\infty A_n} =  \sum_{n=0}^\infty \pr{A_n}\]
for any sequence $A_0,A_1,\dots$ of pairwise disjoint events.
\end{theorem}

It follows that
\begin{corollary}
\[
\pr{A} = \pr{A \intersect B} + \pr{A - B}
\]
\end{corollary}
for \emph{all} events $A, B$, from which we then can directly derive:
\begin{corollary}

\begin{eqnarray}
\pr{A-B} & = & \pr{A} - \pr{A \intersect B}, \mbox{ so} \label{a-b}\\
\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 \intersect B} & \le & \pr{A}, \label{ab<a} \mbox{and}\\
\pr{A \union B} & \le & \pr{A} + \pr{B}.
\end{eqnarray}

\end{corollary}
The last inequality 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=0}^\infty A_n} \leq \sum_{n=0}^\infty \pr{A_n}.\]
\label{thm:n-union}
\end{theorem}

\iffalse
\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}
\fi

\subsection{Wiring circuits}
\textbf{Review}:
We saw in lecture how to use Boole's inequality to estimate error
probabilities for circuit wiring.  The situation was that there were a
total of $n$ wiring connections to be made.  Based on 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
\begin{eqnarray*}
\pr{\mbox{all connections are OK}} & =& \pr{\Intersect_{i=1}^n A_i}\\
& = & 1 - \pr{\Union_{i=1}^n \overline{A_i}} \qquad\mbox{(by DeMorgan and identity~\ref{1-b})}\\
& \ge & 1 - \sum_{i=1}^n \pr{\overline{A_i}} \qquad\mbox{(by Boole's Inequality)}\\\\
& =& 1-np.
\end{eqnarray*}

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 got 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 concluded that the chance that all connections are okay is somewhere
between 90\% and 99\%.

\subsection{Nontransitive Dice Again}
We saw in lecture a contrived example of three ``intransitive'' dice A,B,
C.  These had the property that on any roll of dice A and B, the
probability that A beats B is $p = (\sqrt{5} - 1)/2 = 0.618\ldots$, on a
roll of B and C the probability that B beats C is $p$, and likewise on a
roll of C and A, the probability that C beats A is $p$.  Can we increase
this probability?  That is, can we construct dice so that the probability
of A beating B, B beating C, C beating A are each, say, at least 3/4?

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{lemma}
\[\min \set{\pr{A}, \pr{B}, \pr{C}} \leq \frac{2}{3}.\]
\end{lemma}

\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}}
\]

\emph{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 Problems}

\begin{problems}

\problem Suppose the game {\em Let's Make A Deal} is changed
slightly. Instead of having 3 doors with 1 grand prize, in the new game
there are 4 doors with 2 grand prizes. The rule of the game remains the
same. Therefore the game now becomes:

\begin{quote}
At one stage of the game, a contestant is shown 4 doors. The contestant
knows that there are 2 grand prizes behind 2 of the doors and that there
are goats behind the 2 other doors. At the beginning, the contestant picks
a door. To build suspense, the assistant of the game then opens a {\em
different} door, revealing a goat. The contestant can then stick with his
original door or switch to another unopened door. He wins a prize only if
he now picks the door with the prize.
\end{quote}

In the new game, what is the probability of winning with the ``stick''
strategy? How about the ``switch'' strategy? Can you explain why the two
probabilities do not sum up to 1?

\solution{The player wins with a ``stick'' strategy iff he chooses the
``correct door'' in the first place. Therefore the probability of winning
with the ``stick'' strategy is $\frac{1}{2}$.

To calculate the probability of winning with a ``switch'' strategy, let
$E_1$ be the event that ``the player chooses the correct door at his first
chance''. Let $E_2$ be the event that ``the player switches to the correct
door at his second chance''.
\begin{eqnarray*}
P(\mbox{winning with ``switch''
strategy})&=&P(E_2|E_1)P(E_1)+P(E_2|\overline{E_1})P(\overline{E_1})\\
&=&\frac{1}{2}\cdot\frac{1}{2}+1\cdot\frac{1}{2}\\ &=&\frac{3}{4}
\end{eqnarray*}

The two probabilities do not need to sum up to 1. They are calculated in a
different probability space.  In particular, the player winning by the
``switch'' strategy does not imply he will lose by the ``stick'' strategy,
and vice versa. Therefore, the same winning event can be counted in both
cases at the same time.}


\problem In the circuit wiring problem, we concluded that the chance that
all connections are okay is somewhere between 90\% and 99\%.  Let's model
the problem with the sample space
\[
    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.

\bparts

\ppart Show that the probability that the circuit gets wired correctly
actually could be as high as 99\% by describing appropriate probabilities
for the sample points.

\solution{There could be 99\% reliability if the individual errors occur
in such a way that whenever you make one connection wrong, all the
connections are wrong.

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

\ppart
Show that the probability that the circuit gets wired correctly
actually could be as low as 90\% by describing appropriate probabilities
for the sample points.

\solution{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.
\]}

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

\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.}

\eparts


\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 by spouse counts as being battered by spouse.  Also, we
assume that the event of being murdered by somebody else is not influenced
by whether or not the woman was being battered by her spouse.

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

\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*}
}

\problem We describe a set of three ``intransitive'' dice which are a
little more plausible than the ones described in lecture.  The dice 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}

Here is a game for two players: 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}

\bparts \ppart Prove the claim by carefully describing the tree of
possible outcomes and the resulting probability space, the events of
interest, and their probabilities.  In particular, what is th probability
that A beats B?

\solution{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}
}

\ppart The numbers appearing on dice A and B are, in increasing order,
125679, which occur on dice BABAAB, respectively.  If the roll of A
corresponds to the first A in the sequence, that is, if A rolls as 2,
then since there is one B to the left of the first A, the roll of A in
this case will win 1/3 of the time against B.  If the roll of A
corresponds to the second A in the sequence, that is, if A rolls as 6,
then since there are two B's to the left of the second A, the roll of
A in this case will win 2/3 of the time against B.  Similarly, if the
roll of A corresponds to the third A in the sequence, then A will win
2/3 of the time against B.  So A wins $\frac{1}{3} \frac{1}{3} +
\frac{1}{3}\frac{2}{3} + \frac{1}{3}\frac{2}{3} = \frac{5}{9}$ of the
time, as you concluded in the previous part.

Justify this reasoning by relating it to the way you contructed the
outcome tree and probabilities in part (a).  Use it to prove that

\begin{claim}
Die B beats die C $\frac{5}{9}$ of the time, and die C beats die A
$\frac{5}{9}$ of the time.
\end{claim}
\eparts


\end{problems}

\end{document}

