\documentclass[12pt,twoside]{article}   
\usepackage{light}

\hidesolutions
%\showsolutions

%\newcommand{\pr}[1]{\mathop{\textup{Pr}}\nolimits\left\(#1\right\)}
\newlength{\strutheight}
\newcommand{\prob}[1]{\mathop{\textup{Pr}} \nolimits \left( #1 \right)}
\newcommand{\prsub}[2]{\mathop{\textup{Pr}_{#1}}\nolimits\left(#2\right)}
\newcommand{\prcond}[2]{%
  \ifinner \settoheight{\strutheight}{$#1 #2$}
  \else    \settoheight{\strutheight}{$\displaystyle#1 #2$} \fi%
  \mathop{\textup{Pr}}\nolimits\left(
    #1\,\left|\protect\rule{0cm}{\strutheight}\right.\,#2
  \right)}
%\newcommand{\paren}[1]{\left(#1\right)}
\newcommand{\comment}[1]{}
\newcommand{\intersect}{\cap}
\newcommand{\union}{\cup}
\newcommand{\card}[1]{\lvert #1 \rvert}
%\newcommand{\pr}[1]{\Pr(#1)}
%\newcommand{\prob}[1]{\operatorname{Pr}(#1)}
%\newcommand{\prcond}[2]{\operatorname{Pr}(#1 \mid #2)}
%\newcommand{\prsub}[2]{\operatorname{Pr}_{#1}(#2)}
\newcommand{\cE}{\mathcal{E}}
\renewcommand{\setminus}{-}
\renewcommand{\complement}[1]{\overline{#1}}

\begin{document}

\problemset{10}{November 16, 2004}{\textit{Monday November 22 at 9 PM}}

\insolutions{\stamp}

\begin{problem}[10 points]
We're interested in the probability that a randomly chosen poker hand (5
cards from a standard 52-card deck) contains cards from at most two suits.

%We use a few steps to attack the problem.

\bparts

\ppart What is an appropriate sample space to use for this problem?  What
are the outcomes in the event, $\cE$, we are interested in?  What are the
probabilities of the individual outcomes in this sample space?

\solution{The natural sample space to use consists of the $\binom{52}{5}$
possible poker hands.  The sample space is \emph{uniform}: Each hand is
equally likely and comes up with probability $1 / \binom{52}{5}$.}

\solution{
We define $\cE$ to be the subset of outcomes in which
the 5 cards on the outcome come from at most two suits.
}

\ppart  What is $\prob{\cE}$?

\solution{Since the sample space is uniform,
\[
\prob{\cE} = \frac{\card{\cE}}{\dbinom{52}{5}}.
\]
So we just need to determine the number of outcomes in $\cE$.  For this,
we resort to our usual counting techniques.  Doing it by cases works well.
There are three cases: 5 cards of one suit, 4 cards of one suit and 1 of
another suit, 3 cards of one suit and 2 of another suit.

For 5 of one suit, there are 4 ways to choose the suit and then
$\binom{13}{5}$ ways to choose 5 cards of that suit.

For 4 of one suit and 1 of another, there are 4 ways to choose the suit of
the 4 and $\binom{13}{4}$ ways to choose 4 cards of that suit, and there
are 3 remaining suits to choose for the 1, and 13 choices for the 1 card
of that suit.

Finally, for 3 of one suit and 2 of another, there are 4 ways to choose
the suit of the 3 and $\binom{13}{3}$ ways to choose 3 cards of that suit,
and there are 3 remaining suits to choose for the 2 cards, and
$\binom{13}{2}$ choices for the 2 cards of that suit.   So the total is
\[
4\cdot \binom{13}{5} + 4 \cdot \binom{13}{4} \cdot 3 \cdot 13 + 4 \cdot
\binom{13}{3} \cdot 3 \cdot \binom{13}{2},
\]
and the probability of at most two suits 
is
\[
\frac{4\cdot \dbinom{13}{5} + 4 \cdot \dbinom{13}{4} \cdot 3 \cdot 13 + 4 \cdot
\dbinom{13}{3} \cdot 3 \cdot \dbinom{13}{2}}{\dfrac{1}{\dbinom{52}{5}}}
 = 88/595 \approx 0.15.
\]

\iffalse
There are $\binom{4}{2}$ ways to choose two suits and $\binom{26}{5}$ ways
to choose five cards from these two suits.  But we need to be careful: some
of those $\binom{26}{5}$ choices might all come from the same suit.  These
hands will be triple-counted.  (For example, a hand containing \emph{only}
spades is counted once as a spades-hearts hand, a second time as a
spades-clubs hand, and a third time as a spades-diamonds hand.)  We can
correct for this triple-counting by subtracting off $2$ times the number of
hands that are triple-counted.  Since the number of hands with a single
suit is $4 \cdot \binom{13}{5}$, the number of hands with at most two suits
is
\[
\binom{4}{2} \cdot \binom{26}{5} - 2 \cdot 4 \cdot \binom{13}{5}.
\]
The probability that a random poker hand contains cards from at most
two suits is:
\begin{eqnarray*}
\prob{\cE}
        & = & \frac{\dbinom{4}{2} \cdot \dbinom{26}{5} -
                        2 \cdot 4 \cdot \dbinom{13}{5}}
                {\dbinom{52}{5}} \\
        & = & \frac{88}{595} \approx 0.15
\end{eqnarray*}
\fi

}

\eparts

\end{problem}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{problem}[15 points] \label{Identities}
Prove the following probabilistic identities.  You may assume the theorem
that the probability of a union of \emph{disjoint} sets is the sum of their
probabilities.

\bparts

\ppart \label{setminus}
$\prob{A \setminus B} = \prob{A} - \prob{A \intersect B}$.

\solution{
Any set, $A$, is the disjoint union of $A \setminus B$ and $A \intersect
B$, for any set, $B$.
Thus, 
\[
\prob{ A }= 
\prob{A \setminus B} + \prob{A \intersect B}.
\]
Subtracting $\prob{A \intersect B}$ from both sides gives the desired result.
}


\ppart \label{inclexcl}
The \emph{Inclusion-Exclusion Rule for probability}:
\begin{equation}\label{inclexcleq}
\prob{A \union B} = \prob{A} + \prob{B} - \prob{A \intersect B}.
\end{equation}


\solution{ The proof exactly mirrors the proof of the original
inclusion-exclusion rule given in earlier Notes.  Namely, for any sets
$A,B$, the set $A \union B$ is the disjoint union of $A-B$ and $B$, so
\begin{align*}
\prob{A \union B}
 &= \prob{A \setminus B} + \prob{B} & \text{(disjoint union)}\\
 &= (\prob{A} - \prob{A \intersect B}) + \prob{B} & \text{(by~\eqref{setminus})}\\
 &= \prob{A} + \prob{B} - \prob{B \intersect A}.
\end{align*}
}


\ppart  The \term{Union Bound:}
Let $A_1, \dots, A_n$ be a collection of events.  Then
\[
\prob{A_1 \union A_2 \union \cdots \union A_n} \leq \sum_{i=1}^n
\prob{A_i}.
\]
\emph{Hint:} Induction.

\solution{
For all $n \geq 1$, let $P(n)$ be the proposition that the claim is true.

\textit{Base case:} Trivially $\prob{A_1} \leq \prob{A_1}$, so $P(1)$ is true.

\textit{Induction step:} Assume that $P(n)$ is true and show $P(n+1)$ for
$n \geq 1$.
\begin{align*}
\prob{ A_1 \union A_2 \union \cdots \union A_{n+1}} 
 &= \prob{(A_1 \union A_2 \union \cdots \union A_{n}) \union A_{n+1}} \\
 &= \prob{A_1 \union A_2 \union \cdots \union A_{n}} + \prob{A_{n+1}} \\
 &\quad - \prob{(A_1 \union A_2 \union \cdots \union A_{n}) \intersect A_{n+1}}
 &\text{(by~\eqref{inclexcleq})}\\
 &\leq \prob{A_1 \union A_2 \union \cdots \union A_{n}} + \prob{A_{n+1}}\\
 &\leq \sum_{i=1}^{n} \prob{A_{i}} + \prob{A_{n+1}} &\text{(by Ind. Hyp.)} \\
 &= \sum_{i=1}^{n+1} \prob{A_{i}} 
\end{align*}
Thus $P(n)$ is true and the result follows by induction.
}

\eparts

\end{problem}

\begin{problem}[15 points]

\bparts

\ppart Suppose we independently roll a fair die $n$ times.  What is the
probability of our rolling a 4 at least once?

\solution{The probability of not rolling a 4 on a single roll is $5/6$, so
the probability of not rolling a 4 in $n$ independent rolls is $(5/6)^n$,
and therefore the probability of rolling at least one 4 is $1- (5/6)^n$.}

\ppart Suppose we keep independently rolling a fair die until a 4 gets
rolled.  What is the probability that we roll exactly $n$ times?

\solution{
The probability of not rolling 4 on the first $n-1$ rolls is
$(5/6)^{n-1}$, and the probability of a 4 on the $n$th roll is 1/6, so the
probability of rolling exactly $n$ times is $(5/6)^{n-1}(1/6)$.
}


\ppart Carefully define the probability space you used to answer part~(b),
and prove that your space satisfies the conditions required of a
probability space.

\solution{The simplest space is the positive integers, with the integer $n
>0$ corresponding to the first 4 being rolled on the $n$th roll.  So we
\emph{define} $\prob{n} = (5/6)^{n-1}(1/6)$.  This is a probability space
because $0\leq \prob{n}$ for all outcomes, $n$, and the sum of the
probabilities of all the outcomes is
\[
\sum_{i=1}^{\infty} \paren{\frac{5}{6}}^{n-1}\frac{1}{6} = \frac{1}{6}
\sum_{i=0}^{\infty} \paren{\frac{5}{6}}^{n} = \frac{1}{6} \paren{\frac{1}{1-(5/6)}}
=1.
\]

Another, more detailed probability space, that could be used would have
outcomes equal to all finite sequences of integers 1,2,3,5, and 6, with
each such sequence corresponding to the successive numbers rolled on the
die up to the first roll of 4.  If $s$ is such a sequence of length $n$,
we define $\pr{s} = (1/6)^{n+1}$.  In this probability space, the
probability of 4 first appearing on the $n$th roll for $n \geq 1$ is the
sum of the probabilities of the $5^{n-1}$ length $n-1$ sequences, namely,
$5^{n-1}(1/6)^{n}$, which is, of course the same as the probability of the
integer $n$ in the previous, simple space.}

\ppart In the probability space you used in part~(c), what is the set of
outcomes in the event that a 4 never gets rolled?  What is the probability
of this event?

\solution{Using either of the probability spaces in the solution of
part~(c), the event of never rolling a 4 is the empty set, and the event
of rolling a 4 is the whole space.  So the probability is never rolling a
4 is zero and the probability of eventually rolling a 4 is one.

If it bothers you that there is no outcome corresponding to the logical
possibility that the die is rolled forever without a 4 ever being rolled,
then throw in an additional sample point, $\omega$, corresponding to this
outcome.  Since the sum of the probabilities of the other outcomes is 1,
there is no choice but to define $\pr{\omega} = 0$.  So throwing in
$\omega$ won't make any difference in determining the probabilities or
expectations of events.}

\eparts
\end{problem}

\begin{problem}[10 points]
There is a course---not 6.042, naturally---in which $10 \%$ of the
assigned problems contain errors.  If you ask a TA whether a problem has
an error, then he or she will answer correctly $80\%$ of the time.  This
$80 \%$ accuracy holds regardless of whether or not a problem has an
error.  Likewise when you ask a lecturer, but with only $75 \%$ accuracy.

Suppose you have doubts about a problem and ask a TA about it, and she
tells you that the problem is correct.  To double-check, you ask a
lecturer, who says that the problem has an error.  Assuming that \emph{the
correctness of the lecturers' answer and the TA's answer are independent
of each other, regardless of whether there is an error}.\footnote{This
assumption is questionable: by and large, we would expect the lecturer and
the TA's to spot the same glaring errors and to be fooled by the same
subtle ones.}  Now you want to figure out the probability that there is an
error in the problem.

This question can be formulated as an experiment of choosing one problem
randomly and asking a particular TA and Lecturer about it.  Define the
following events:
\begin{eqnarray*}
E & ::= & \mbox{``the problem has an error,''}\\
T & ::= & \mbox{``the TA says the problem has an error,''}\\
L & ::= & \mbox{``the lecturer says the problem has an error.''}
\end{eqnarray*}

\bparts

\ppart What are $\prob{E}, \prcond{T}{E}$, and $\prcond{L}{E}$?

\solution{The assumptions above tell us:
\begin{eqnarray*}
\prob{E}        & = & \frac{10}{100} = \frac{1}{10},\\
\prcond{T}{E} & = & \prcond{\bar{T}}{\bar{E}} = \frac{80}{100} = \frac{4}{5},\\
\prcond{L}{E} & = & \prcond{\bar{L}}{\bar{E}} = \frac{75}{100} = \frac{3}{4},
\end{eqnarray*}}

\ppart Translate the independence assumptions into a couple of equations
about\\
$\prcond{T \intersect L}{E}$ and $\prcond{T \intersect L}{\bar{E}}$.

\solution{Also, $T$ and $L$ are independent given $E$, and given $\bar{E}$:
\begin{eqnarray*}
\prcond{T \intersect L}{E} & = & \prcond{T}{E} \prcond{L}{E}\\
\prcond{T \intersect L}{\bar{E}} & = & \prcond{T}{\bar{E}} \prcond{L}{\bar{E}}
\end{eqnarray*}
Note that while we know that $T$ and $L$ are independent \emph{given} $E$
or \emph{given} $\bar{E}$, they are not independent by themselves (see
part~\eqref{TL}).
}

\ppart  Calculate
\[
\prcond{E}{\bar{T} \intersect L}.
\]

\solution{
From the definition of conditional probability (this is Bayes' rule):
\begin{equation}\label{eq:B2}
 \prcond{E}{\bar{T} \intersect L} = \prob{E}
 \frac{\prcond{\bar{T} \intersect L}{E}}
      {\prob{\bar{T} \intersect L}}.
\end{equation}

By the independence assumptions, we have:
\begin{eqnarray*}
\prcond{\bar{T} \intersect L}{E} & = & \prcond{\bar{T}}{E} \prcond{L}{E}
     = \frac{1}{5}\frac{3}{4}  = \frac{3}{20},\\
\prcond{\bar{T} \intersect L}{\bar{E}} & = &
         \prcond{\bar{T}}{\bar{E}} \prcond{L}{\bar{E}}
     = \frac{4}{5} \cdot \frac{1}{4} = \frac{1}{5},\\
\prob{\bar{T} \intersect L} & = & \prcond{\bar{T} \intersect L}{E}  \prob{E} + 
                          \prcond{\bar{T} \intersect L}{\bar{E}} \prob{\bar{E}}\\
 & = & \frac{3}{20} \cdot \frac{1}{10} + \frac{1}{5} \cdot \frac{9}{10}
       = \frac{39}{200}.
\end{eqnarray*}

Substituting these values in equation~(\ref{eq:B2}), we get
\[
\prcond{E}{\bar{T} \intersect L} = \frac{1}{10} \cdot \frac{3/20}{39/200} =
\frac{1}{13} \approx 0.077.
\]
So this contradictory information has decreased the probability of an error
from $10 \%$ to about $7.7 \%$.

The calculations here support the common-sense rule that when two people
make contradictory statements, you should be influenced more by the most
``authoritative'' person---the one who is right more often.  But note that
this does not mean that you should {\em believe} in what the most
authoritative person says, since the probability of a mistaken conclusion
remains uncomfortably large.}

\ppart\label{TL} Is the event that ``the TA says that there is an error'',
independent of the event that ``the lecturer says that there is an
error''?   Explain.

\solution{The answer is no.  Because the TA is usually right, when the TA
says that the problem has an error, the likelihood that there really is an
error is increased.  But the lecturer is also usually right, so increasing
the likelihood of there \emph{being} an error also increases the
likelihood that the lecturer will \emph{report} an error.

We verify this informal argument by actually calculating the probability
of each of these events and their conjunction, and observing that the
probability that the two events occur is different from the product of the
probabilities.  Let events $E,T,L$ be as above.

\begin{eqnarray*}
\prob{T} & = & \prob{T \cap E} + \prob{T \cap \bar{E}}\\
 & = & \prob{T \mid E} \prob{E}  + \prob{T \mid \bar{E}} \prob{\bar{E}}\\
 & = & \frac{4}{5} \frac{1}{10} + (1 - \frac{4}{5})
 (1 - \frac{1}{10}) = \frac{13}{50},\\
& & \\
\prob{L} & = & \prob{L \cap E} + \prob{L \cap \bar{E}}\\
  & = & \frac{3}{4} \frac{1}{10} + (1 -\frac{3}{4})(1 - \frac{1}{10}) = \frac{3}{10},\\
& & \\
\prob{L \cap T} & = & \prob{L \cap T \cap E} + \prob{L \cap T \cap \bar{E}} \\
& = & \prob{L \cap T \mid  E} \prob{E} + \prob{L \cap T \mid  \bar E} \prob{\bar E}\\
& = & \prob{L \mid E}      \prob{T \mid  E}       \prob{E} + 
      \prob{L \mid \bar E} \prob{T \mid  \bar{E}} \prob{\bar E}\\
& = & \frac{3}{4} \cdot \frac{4}{5} \cdot \frac{1}{10}
        + (1 - \frac{3}{4}) (1 - \frac{4}{5}) \cdot (1 - \frac{1}{10}) = \frac{105}{1000} = 0.105,
\end{eqnarray*}
which is higher than 
\[
\prob{L}\prob{T} = \frac{3}{10} \cdot \frac{13}{50} = .078.
\]
}

\eparts
\end{problem}


\begin{problem}[15 points]
Three gunfighters, $A$, $B$, and $C$, plan to fight a pistol duel.
They stand in a triangle so that they all have a clear shot at each other.
All of them know that $A$'s chance of hitting his target is $0.3$,
$B$ never misses, and $C$'s chance of hitting is $0.5$.
They will shoot one at a time in the sequence $ABCABC\ldots$
(once a fighter is dead, he no longer gets a turn).
On his turn, a gunfighter may choose to target either one of the
other two, or may fire harmlessly into the air.
Assume that each gunfighter uses the shooting strategy that maximizes his probability
of being the only one left standing. 

\textit{Note:}
You may assume that the events of hitting the desired target at each turn
are mutually independent.

\bparts

\ppart
Whenever it is $B$'s turn, what is his optimal strategy?

\solution{
If either $A$ or $C$ is already dead, $B$ only needs to shoot the remaining
fighter to win.
So suppose that both $A$ and $C$ are still alive.
Since $B$ never misses, the person he doesn't shoot will only have $B$ left to shoot at.
To minimize this remaining person's chance of hitting $B$,
the optimal stategy for $B$ is to shoot the most accurate gunfighter.
So $B$ will shoot $C$---this gives him a $1-0.3 = 0.7$
chance of survival---and not $A$---that would only give him a $1-0.5
= 0.5$ chance of survival.
}

\ppart What is $A$'s probabililty of surviving if: 

\begin{enumerate}

\item he misses on his first shot?

\solution{If $A$ misses, then by part~(a), $B$ shoots $C$, and $A$ gets
one more shot to kill $B$ before he himself is killed.  Therefore $A$ has a
$0.3$ chance of survival.}


\item he hits $B$ on his first shot?

\solution{With $B$ dead, $A$ then he enters a duel
with $C$, where $C$ gets the first shot.  In this case, let $p$ be
the probability that $A$ wins the duel.  For this to happen, either
$C$ must miss and $A$ must hit (probability $0.5 \cdot 0.3$) or else
$C$ must miss, $A$ must miss, and then $A$ must win a duel of the
same type as before (probability $0.5 \cdot 0.7 \cdot p$).  As an
equation:
\begin{displaymath}
p = \frac{1}{2} \cdot \frac{3}{10} + \frac{1}{2} \cdot \frac{7}{10} p,
\end{displaymath}
which has the solution $p = 3 /13 < 0.24$.
}

\item he hits $C$ on his first shot?

\solution{With $C$ dead, then $B$ immediately kills him, so his probability
of survival in this case is 0.}

\end{enumerate}

\ppart Conclude that $A$'s best strategy is to fire in the air!  What is
his probability of survival?

\solution{
If $A$ hits $B$ or $C$, his probability of survival is lower than if he
misses.  So his best strategy is to fire into the air; this gives him the
probability of survival that he has when he misses, namely $0.3$.
}


\eparts
\end{problem}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{problem}[10 points] \label{relative}
Most probability identities continue to hold when all probabilities are
conditioned on the same positive probability event, $C$.  For example, the
Inclusion-Exclusion rule~\eqref{inclexcleq} can be conditioned on $C$ to
become the Conditional Inclusion-Exclusion Rule:
\begin{equation}\label{cie}
\prcond{A \union B}{C} = \prcond{A}{C} + \prcond{B}{C} - \prcond{A \intersect B}{C}.
\end{equation}

\bparts

\ppart Define a new function, $\prsub{C}{}$ by the
rule that
\begin{definition*}%\label{defprs}
\[
\prsub{C}{A} = \prcond{A}{C}.
\]
\end{definition*}
Prove that for any positive probability event, $C$, the function
$\prsub{C}{}$ is another probability measure (on the same sample space).

\iffalse \textit{Hint:} Review the definition of a probability space in the
lecture notes.
\hyperref{http://theory.lcs.mit.edu/classes/6.042/spring02/handouts/lectures/ln9.pdf}
{ln9}{probsp}{Notes 9, Definition 5.2}.
\fi


\solution{
The sample space, $S$, for the new probability space has not
changed.  Note that $\prsub{C}{}$ is defined on events, so we define the
probability of an outcome, $s \in S$, to be the probability of the event
$\set{s}$.

We must must show for the new probability function, $\prsub{C}{}$,
that
\begin{enumerate}

\item the probability of each outcome is nonnegative,

\item\label{S} the sum of the probabilities of all the outcomes in $S$ is 1, and

\item\label{A} the probability of an event is the sum of the probabilities
of its outcomes.

\end{enumerate}
\begin{proof}

To show that outcome probabilities are nonegative, we note that
for any outcome $s \in S$, we have
\[
\prsub{C}{s}= \prsub{C}{\set{s}} = \prcond{\set{s}}{C} = \frac{\pr{\set{s} \cap
C}}{\pr{C}},
\]
and the last quantity is nonnegative because it is a quotient of
nonnegative quantities.


Next we observe that
\[
\prsub{C}{S} = 1
\]
because

\begin{align*}
\prsub{C}{S} & = \prcond{S}{C}
                     & \text{(Def of $\prsub{C}{}$)}\\
             & = \frac{\pr{S \cap C}}{\pr{C}}
                     & \text{(Def of $\prcond{}{C}$)}\\
             & = \frac{\pr{C}}{\pr{C}} = 1
                     & (C \subseteq S).
\end{align*}


So if the probability of $S$ is the sum of the probability of the
outcomes, it follows that the sum of the outcome probabilities is 1, that
is,~\ref{S}.\ holds.

So it remains only to prove~\ref{A}., namely, that for any event, $A$,
\[
\prsub{C}{A} = \sum_{s \in A} \prsub{C}{s}.
\]

This follows because
\begin{align*}
\prsub{C}{A} & = \prcond{A}{C}
                     & \text{(Def of $\prsub{C}{}$)}\\
             & = \frac{\pr{A \cap C}}{\pr{C}}
                     & \text{(Def of $\prcond{}{C}$)}\\
             & = \frac{\sum_{s \in (A \cap C)} \pr{s}}{\pr{C}}
                       &\text{($\pr{E} = \sum_{s \in E} \pr{s}$ for any $E$)}\\
             & = \sum_{s \in (A \cap C)} \frac{\pr{s}}{\pr{C}}\\
             & = \sum_{s \in A} \frac{\pr{\set{s} \cap C}}{\pr{C}}
                & \text{($\set{s} \cap C = \emptyset$ unless $s \in C$)}\\
             & = \sum_{s \in A} \prcond{\set{s}}{C}
                     & \text{(Def of $\prcond{}{C}$)}\\
             & = \sum_{s \in A} \prsub{C}{s}
                     & \text{(Def of $\prsub{C}{}$)}.
\end{align*}

\end{proof}
}


\ppart Use part~(a) to give a simple proof of the Sum Rule conditioned on
$C$.  Namely, suppose $A$ is the disjoint union of sets
$A_1,A_2,\dots,A_n$.  Prove that
\begin{equation*}
\prcond{A}{C} = \sum_{i}^n {\prcond{A_i}{C}}.
\end{equation*}

\solution{
\begin{align*}
\prcond{A}{C} & = \prcond{\bigcup_{i}^n A_i}{C}\\
    &= \prsub{C}{\bigcup_i^n A_i}
            & \text{Def of $\prsub{C}{}$}\\
    &= \sum_i^n \prsub{C}{A_i} & \text{(Sum Rule for $\prsub{C}{}$)}\\
    &=  \sum_{i}^n {\prcond{A_i}{C}} &
           \text{Def of $\prsub{C}{}$}.
\end{align*}

}

\eparts

\end{problem}


\begin{problem}[15 points]\label{ABC}

%The following problems relate to independence of events.

\bparts

\ppart Suppose $A$ and $B$ are \emph{disjoint} events.  Prove that $A$ and
$B$ are \emph{not independent}, unless $\prob{A}$ or $\prob{B}$ is zero.

\solution{
If $\prob{A} \neq 0$ and $\prob{A} \neq 0$, then 
\[
\prob{A} \cdot \prob{B} \neq 0 =  \prob{\emptyset} = \prob{A \intersect B}.
\]
So $A$ and $B$ are not independent.
}


\ppart If $A$ and $B$ are independent, prove that $A$ and $\complement{B}$
are also independent.  You may find it useful to use results from Problem
\ref{Identities}.

\solution{
\begin{align*}
\prob{A \intersect \complement{B}}
 &= \prob{A \setminus B} \\
 &= \prob{A} - \prob{A \intersect B} &&\text{(by Problem \ref{Identities} (\ref{setminus}))} \\
 &= \prob{A} - \prob{A} \cdot \prob{B} &&\text{(since $A$ and $B$ are independent)} \\
 &= \prob{A} \cdot (1 - \prob{B}) \\
 &= \prob{A} \cdot \prob{\complement{B}}.
\end{align*}
The last equality holds since the probability of any event equals $1$ minus the probability of its
complement.
Thus, we have shown that $\prob{A \intersect \complement{B}}=\prob{A} \cdot \prob{\complement{B}}$,
which is equivalent to $A$ and $\complement{B}$ being independent.
}


\ppart 
Give an example of events $A$,$B$, $C$ such that $A$ is independent of $B$,
$A$ is independent of $C$, but $A$ is not independent of $B\union C$.

\solution{The experiment is 2 independent coin flips, letting $A$ be ``the
1st flip is heads'', $B$ the ``the 2nd flip is heads,'' $C$ is ``odd
number of heads.''  Then $A$ is not independent of $B \union C$ because
\[
\prcond{A}{B \union C} = 2/3 \neq 1/2 = \prob{A}.
\]

\iffalse

Consider the usual random experiment of
rolling a die and let $A$, $B$, $C$ be the events that the die rolls
less than 3, rolls an even number, or rolls a prime number,
respectively. I.e., 
\[
A = \{1,2\} \qquad
B = \{2,4,6\} \qquad
C = \{2,3,5\}.
\]
Then, 
$$
\prob{A}=\tfrac{1}{3}, 
\qquad
\prob{B}=\prob{C}=\tfrac{1}{2},
$$
and
$$
\prob{A\cap B}=
\prob{A\cap C}=
\prob{B\cap C}=
\prob{A\cap B\cap C}=
\prob{\{2\}}=
\tfrac{1}{6}.
$$
Easily, 
$$
\prob{A\mid B}=
\prob{A\mid C}=
\tfrac{1}{6}/\tfrac{1}{2}=
\tfrac{1}{3}=
\prob{A},
$$
which proves $A$ is independent of $B$ and also independent of
$C$. However, 
$$
\prob{A\mid B\cap C}=
\prob{A\cap B\cap C}/\prob{B\cap C}=
\tfrac{1}{6}/\tfrac{1}{6}=
1\neq
\prob{A},
$$
which implies $A$ is not independent of $B\cap C$.
\fi

}

\ppart Prove that if $C$ is independent of $A$, and $C$ is independent of
$B$, and $C$ is independent of $A \intersect B$, then $C$ is independent
of $A \union B$.  \textit{Hint:} Calculate $\prcond{A \union B}{C}$.

\solution{
Conditional inclusion-exclusion followed by plain-vanilla inclusion-exclusion provides
a quick proof:
\begin{align*}
\prcond{A \union B}{C}
 &= \prcond{A}{C} + \prcond{B}{C} - \prcond{A \intersect B}{C}
    & \text{(by~\eqref{cie})}\\
 &= \prob{A} + \prob{B} - \prob{A \intersect B}
    &\text{(by independence)} \\
 &= \prob{A \union B}
    & \text{(by~\eqref{inclexcleq})}
\end{align*}
}

\eparts

\end{problem}


\iffalse

\begin{problem}[10 points]
Let $A,B,C$ be events of some experiment.  For each of the following 
statements, prove it if it is true or give a counterexample if it is
false:

\bparts

\ppart 
If $A$ is independent of $B$, and $A$ is independent of $C$, 
then $A$ is independent of $B\cap C$.

\solution{
This is false. To see why, consider the usual random experiment of
rolling a die and let $A$, $B$, $C$ be the events that the die rolls
less than 3, rolls an even number, or rolls a prime number,
respectively. I.e., 
$$
A = \{1,2\} \qquad
B = \{2,4,6\} \qquad
C = \{2,3,5\}.
$$
Then, 
$$
\prob{A}=\tfrac{1}{3}, 
\qquad
\prob{B}=\prob{C}=\tfrac{1}{2},
$$
and
$$
\prob{A\cap B}=
\prob{A\cap C}=
\prob{B\cap C}=
\prob{A\cap B\cap C}=
\prob{\{2\}}=
\tfrac{1}{6}.
$$
Easily, 
$$
\prob{A\mid B}=
\prob{A\mid C}=
\tfrac{1}{6}/\tfrac{1}{2}=
\tfrac{1}{3}=
\prob{A},
$$
which proves $A$ is independent of $B$ and also independent of
$C$. However, 
$$
\prob{A\mid B\cap C}=
\prob{A\cap B\cap C}/\prob{B\cap C}=
\tfrac{1}{6}/\tfrac{1}{6}=
1\neq
\prob{A},
$$
which implies $A$ is not independent of $B\cap C$.
}

\ppart 
If $A$ is independent of $B$, and $A$ is independent of $C$, 
then $A$ is independent of $B\cup C$.

\solution{
This is false. E.g., look again at the counter-example for part~(b)
and notice that  
$$
\prob{B\cup C}=\tfrac{5}{6}, \qquad
\prob{A\cap(B\cup C)}=\tfrac{1}{6}.
$$ 
Hence,
$$
\prob{A\mid B\cup C}=
\tfrac{1}{6}/\tfrac{5}{6}=
\tfrac{1}{5}\neq
\prob{A}
$$
which again implies $A$ is not idependent of $B\cup C$.
}

\eparts

\end{problem}
\fi



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{problem}[10 points] 
Suppose there are 100 people in a room.
Assume that their birthdays are mutually independent and uniformly distributed.
Let $A$ be the event that two people have the same birthday.
As stated in lecture notes, $\prob{A} > 0.99$.

Suppose we fix a particular person in the class---call her ``Jane''---and then ask
everyone in the room \emph{except Jane} when their birthday is.
Let $B$ be the event that all of those 99 birthdays are different.

\bparts

\ppart 
What's wrong with the following argument:
\begin{quotation}\noindent
With probability greater than 0.99, some pair of people in the room
have the same birthday.  Since the 99 people we asked all had
different birthdays, it follows that with probability greater
than 0.99, Jane has the same birthday as some other person in the room. 
\end{quotation}

\solution{
Here's the problem with the argument.
We know that $\prob{A} > 0.99$.
This is known as the \emph{a priori} probability, i.e.,
the initial probability without knowing any additional information.
The argument above makes the erroneous assumption that event $A$ has
probability at least $0.99$ even once we know that event $B$ holds.
More formally, it assumes that $\prcond{A}{B} > 0.99$.
But, for general events $\cE_1$ and $\cE_2$,
$\prob{\cE_1}$ and $\prcond{\cE_1}{\cE_2}$ are \emph{completely unrelated}!
In our particular case, $\prob{A}$ and $\prcond{A}{B}$ are quite different,
as we will see next.
}

\ppart
What is the actual probability that Jane has the same birthday
as some other person in the room?

\solution{
The individual outcomes in the sample space are of the form
\[
(b_1, b_2, \ldots, b_{99}, b_J),
\]
where $b_i$ is the $i$th person's birthday and $b_J$ is Jane's birthday.
The outcomes in $B$ all satisfy the property that $b_1, \dots, b_{99}$
are distinct.  Thus, by the product rule, the size of $B$ is:
\[
(365 \cdot 364 \cdots 267) \cdot 365.
\]
We are interested in $\prcond{A}{B}$.
Since all outcomes have the same probability,
this is simply the fraction of outcomes in $B$ that are also in $A$.
So we're interested in the number of outcomes in $B$ satisfying $b_J \in \{b_1, \dots, b_{99} \}$.
This is
\[
(365 \cdot 364 \cdots 267) \cdot 99,
\]
again by the product rule.
Thus
\[
\prcond{A}{B}
  = \frac{(365 \cdot 364 \cdots 267) \cdot 99}{(365 \cdot 364 \cdots 267) \cdot 365}
  = \frac{99}{365}.
\]
}

\comment{
Old proof, using random variables:

Let $S$ be the set of birthdays of the 99 people in the room
other than Jane. By assumption, $|S| = 99$. Let $b$ be the date
of Jane's birthday. Since $b$ is uniformly distributed over a
set of size 365, and $b$ is independent of all the birthdays in
$S$, we have
\[
\prob{A\mid B} = \prob{b\in S} = 
\frac{\card{S}}{365} = 
\frac{99}{365} \approx 27.1\%,
\]
where $B$ is the event that the 99 people we asked all have
different birthdays.
}
\eparts
\end{problem}


\end{document}
