\documentclass[11pt, twoside]{article}
\input{macros-course}
\usepackage{graphicx}
\renewcommand{\implies}{\longrightarrow}
\newcommand{\ignore}[1]{}
\askaboutsolutions
\begin{document}
\pset{9}{April 24, 2001}{2:35pm in lecture, May 1, 2001}
\renewcommand{\labelenumi}{\bf (\alph{enumi})}
\renewcommand{\labelenumii}{\bf (\roman{enumi})}
\textbf{Be sure to indicate your TA's name clearly on the solutions
you turn in}.

\paragraph{Reading}
Rosen, \textit{Discrete Mathematics and Its Applications},
Sections 4.4 and 4.5

\vspace{-.25in}

\paragraph{Policy on collaboration}
If you collaborated with someone on the problem sets, you should
mention their names on top of the problem set. If you did not
collaborate with anyone, you should explicitly say so. As a reminder,
the write-up of your solutions should be entirely your own.

\vspace{-.25in}

\paragraph{Self-study}
The following exercises are \emph{optional;} do them if you think you
need the practice. The mini-quiz in tutorial on Friday will draw
(only) from these problems.

Exercises from Rosen (answers in the back of the book): 
4.4.1; 4.4.3; 4.4.5; 4.4.7; 4.4.21; 4.5.1; 4.5.3; 4.5.7

\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem \goals{Discrete Probability, teams}
Suppose that you roll three six-sided dice.

\begin{problemparts}
\problempart What is the probability that the sum of the first two rolls is 7?
\solution{%
  \textbf{Solution:} There are 36 equally-likely outcomes for the
  first two rolls.  In 6 of these outcomes, the sum of the rolls is 7.
  Therefore, the probability is $\frac{6}{36} = \frac{1}{6}$.}
\problempart What is the probability that the sum of the first two
  rolls is 7 and the sum of the last two rolls is 7?
\solution{%
  \textbf{Solution:} There are $6^3 = 216$ equally-likely outcomes for
  all three rolls.  In 6 of these outcomes, the sum of the first two
  rolls is 7 and the third is equal to the first.  Therefore, the
  probability is $\frac{6}{216} = \frac{1}{36}$.}
\problempart What is the probability that every pair of rolls sums up to 7?
\solution{%
  \textbf{Solution:} The probability is zero.  Assume that there were
  a set of rolls such that every pair summed to 7.  Since the first
  rolls sum to 7, one of these rolls must be odd and the other even.
  As a result, the third roll can always be paired with one of the
  same parity to give an even sum.}
\problempart What is the probability that some pair of rolls sums up to 7?
\solution{%
  \textbf{Solution:} Let $A$ be the event that the first two rolls sum
  up to 7, $B$ be the event that the last two rolls sum to 7, and $C$
  be the event that the first and last rolls sum to 7.  The
  probability that some pair of rolls sums up to 7 is $\Pr(A \cup B
  \cup C)$.  We can evaluate this quantity with inclusion exclusion:
  \begin{eqnarray*}
    \Pr(A \cup B \cup C)    & = &   \Pr(A) + \Pr(B) + \Pr(C) \\
                        &   &   \mbox{} - \Pr(A \cap B) - \Pr(A \cap C)
                                - \Pr(B \cap C) \\
                        &   &   \mbox{} + \Pr(A \cap B \cap C) \\
                        & = &   \frac{1}{6} + \frac{1}{6} + \frac{1}{6}
                                - \frac{1}{36} - \frac{1}{36} - \frac{1}{36}
                                + 0 \\
                        & = &   \frac{5}{12}
  \end{eqnarray*}
  All the probabilities were computed in preceding steps.}
\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem  \goals{Discrete Probability, teams}
After their arrest and sentencing for
unlawful use of firearms, and short hospital stays, the three
gunfighters, $A$, $B$, and $C$ applied for parole.  The parole board
decided to release two of the three, chosen uniformly at random, but
has not released their names.

Gunfighter $A$ figures that he will be released with probability
$\frac{2}{3}$.  A guard offers to tell gunfighter $A$ the name of one
of the other gunfighters who will be released (either $B$ or $C$).
However, gunfighter $A$ declines the offer.  He reasons that if the
guard says, for example, ``$B$ will be released'', then his own
probability of release will drop to $\frac{1}{2}$.  This is because he
will then know that either he or $C$ will also be released, but these
events are equally likely.

Either prove that gunfighter $A$ has reasoned correctly or prove that
he is wrong.  Assume that if the guard has a choice of saying $B$ or
$C$ because both are to be released, then he picks one uniformly at
random.

\solution{Gunfighter $A$ has reasoned incorrectly.  We must compute

\begin{eqnarray*}
\Pr(\text{$A$ released} \mid \text{guard says ``$B$''})
        & = &   \frac{\Pr(\text{$A$ released and guard says ``$B$''})}
                        {\Pr(\text{guard says ``$B$''})}.
\end{eqnarray*}

These probabilities are worked out in the tree diagram below.

\bigskip
\centerline{\resizebox{!}{3.0in}{\includegraphics{figures/Sol9-prisoner}}}
\bigskip

Plugging these probabilities into the preceding equation gives
\begin{displaymath}
  \Pr(\text{$A$ released} \mid \text{guard says $B$ released})
  = \frac{1}{3} \biggm/ \frac{1}{2} = \frac{2}{3}\,.
\end{displaymath}
If the guard says that $B$ will be released, then $A$ still has a
$\frac{2}{3}$ chance of release.
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset9 problem2 spring98
\ignore{
\problem 

A sequence of numbers $<{\tt 0},{\tt 2},{\tt 2},{\tt 2},{\tt 2},{\tt 5},{\tt 5},{\tt 7},{\tt 7}>$ is randomly permuted to form a 
9-digit integer, in such a way that the digit {\tt 0} does not come first.
(In other words, if the digit {\tt 0} comes first in the permutation, we
try a new permutation until this does not occur.) Let $p$ be the 9-digit
number. Find the probabilities of the following:

\bparts
\ppart $p$ is a multiple of 2.

\solution{
We have two ways to solve the problem. Method 1 counts the number of outcomes
in the event spaces and sample space. Since each outcome is equally likely to
occur, the probability is simple the ratio of the two numbers. Method 2 finds
the probability of the desired outcome using conditional probability. 

{\bf Method 1: Counting}

To find the total number of permutations, first note that the digit {\tt0} can
appear as the $2^{nd}, 3^{rd},\ldots,9^{th}$ position. So there are 8 ways to
put the number {\tt0}. The remaining 8 numbers (some of them are repeated) can
permute among the remaining 8 positions. Therefore the total number of
permutations is $8\cdot\frac{8!}{4!2!2!}=3360$. 

$p$ is a multiple of 2 iff $p$ ends {\tt0} or {\tt2}. The number of outcomes
which end with {\tt0} is $\frac{8!}{4!2!2!}=420$. This is because once {\tt0}
is fixed at position 9, the other 8 numbers can permute in the remaining 8
positions in any way.

The number of outcomes which end with {\tt2} is $7\cdot\frac{7!}{3!2!2!}=1470$. 
This is because with the number {\tt2} fixed at the $9^{th}$ digit, the
number {\tt0} has to choose among the $2^{nd},3^{rd},\ldots,8^{th}$ positions.
Therefore there are 7 choices to put {\tt0}. The remaining 7 numbers can
permute in the remaining 7 positions in $\frac{7!}{3!2!2!}$ ways.

Therefore, the probability that $p$ is even is
$\frac{420+1470}{3360}=\frac{9}{16}$.

{\bf Method 2: Conditional Probability}

First note that the probability distribution for {\tt 0} to appear in any
places is different from other numbers because it cannot appear in the first
place. So we have to deal with it separately. In fact, the probability that
{\tt 0} appears in the $n^{th}$ digit is $\frac{1}{8}$ for $n=2,3,\ldots,9$,
since it can be placed in any of the 8 positions.  

We need to find the probability that $p$ ends with an even integer.

We first find the probability for each number to appear at the last position.
Since the probability that $p$ ends with {\tt 0} is $\frac{1}{8}$, the
probability that $p$ ends with other numbers is $\frac{7}{8}$. If we treat all
the repeated numbers as distinct numbers, the probability for each of them to
appear as the last digit is $\frac{7}{8}\cdot\frac{1}{8}=\frac{7}{64}$.
Since {\tt 2} has appeared four times among the eight numbers, the probability
that {\tt 2} appears as the last digit is $4\cdot\frac{7}{64}=\frac{7}{16}$.
(Same reasoning can be applied to other positions. We will use this reasoning
for the following parts.)

The probability that $p$ is a multiple of 2 is equal to the probability that
$p$ ends with a {\tt 0} or {\tt 2}. Since the two events are disjoint, we can
apply the sum rule:
\begin{eqnarray*}
P(p\mbox{ is a multiple of 2})&=&\underbrace{\frac{1}{8}}_{\mbox{{\em p} ends with {\tt 0}}}+\underbrace{\frac{7}{16}}_{\mbox{{\em p} ends with {\tt 2}}}\\
&=&\frac{9}{16}\\
\end{eqnarray*}
}

%\ppart  $p$ is a multiple of 3.
%
%\solution{
%{\bf Solution}
%
%Since the sum of the digits is not a multiple of 3, $p$ is not divisible by 3.
%Therefore the probability that $p$ is a multiple of 3 is 0.
%}

\ppart  $p$ is a multiple of 25.

\solution{
{\bf Method 1: Counting}

If $p$ is a multiple of 25, it has to end with either {\tt 25}, {\tt 50} or
{\tt 75}. We count the number of outcomes that end with either {\tt25, 50} or
{\tt75}.

The number of outcomes that end with {\tt25} is $6\cdot\frac{6!}{3!1!2!}=360$.
The number of outcomes that end with {\tt50} is $\frac{7!}{4!1!2!}=105$. The
number of outcomes that end with {\tt75} is $6\cdot\frac{6!}{4!1!1!}=180$.
Therefore the probability that $p$ is a multiple of 25 is
$\frac{360+105+180}{3360}=\frac{43}{224}$.


{\bf Method 2: Conditional Probability}

If $p$ is a multiple of 25, it has to end with either {\tt 25}, {\tt 50} or
{\tt 75}. We calculate the probability for each event separately, using the
same reasoning as in part a). 

Let $A_i$ be the event that ``The $8^{th}$ digit of $p$ is {\tt $i$}''.

Let $B_i$ be the event that ``The last digit of $p$ is {\tt $i$}''.

\begin{eqnarray*}
P(p\mbox{ ends with {\tt 25}})&=&P(A_2 \cap B_5)\\
&=&P(A_2|B_5)P(B_5)\\
&=&\underbrace{(1-\frac{1}{7})\cdot4\cdot\frac{1}{7}}_{P(A_2|B_5)}\cdot2\cdot\frac{7}{64}\\
&=&\frac{3}{28}\\
\\
P(p\mbox{ ends with {\tt 50}})&=&P(A_5\cap B_0)\\
&=&P(A_5|B_0)P(B_0)\\
&=&\underbrace{2\cdot\frac{1}{8}}_{P(A_5|B_0)}\cdot\frac{1}{8}\\
&=&\frac{1}{32}\\
\\
P(p\mbox{ ends with {\tt 75}})&=&P(A_7 \cap B_5)\\
&=&P(A_7|B_5)P(B_5)\\
&=&\underbrace{(1-\frac{1}{7})\cdot2\cdot\frac{1}{7}}_{P(A_7|B_5)}\cdot2\cdot\frac{7}{64}\\
&=&\frac{3}{56}\\
\end{eqnarray*}

Therefore, $P(p$ is a multiple of 25$)=\frac{3}{28}+\frac{1}{32}+\frac{3}{56}=\frac{43}{224}$  
}

\ppart  the first and the last digits of $p$ are {\tt 2}.

\solution{
{\bf Method 1: Counting}

The number of outcomes that both start and end with a {\tt2} is
$\frac{7!}{1!2!2!2!}=630$. Therefore the probability that the first and the
last digits of $p$ are both {\tt2} is $\frac{630}{3360}=\frac{3}{16}$.


{\bf Method 2: Conditional Proability}

In this part, let $A_i$ be the event that
``The first digit of $p$ is {\tt $i$}''.
Let $B_i$ be the event that ``The last digit of $p$ is {\tt $i$}''. Note that
{\tt 0} cannot be the first digit of $p$. Therefore the remaining eight
integers have equal chance of $\frac{1}{8}$ to be the first digit.

\begin{eqnarray*}
P(p\mbox{ starts and ends with {\tt 2}})&=&P(A_2 \cap B_2)\\
&=&P(A_2|B_2)P(B_2)\\
&=&\underbrace{3\cdot\frac{1}{7}}_{P(A_2|B_2)}\cdot4\cdot\frac{7}{64}\\
&=&\frac{3}{16}
\end{eqnarray*}
}

\ppart $p$ is symmetric. (i.e., the number does not change if the sequence
of digits is reversed)

\solution{
In this part counting is a much simpler method to use. 

For $p$ to be symmetric, the $5^{th}$ digit of $p$ has to be 0. The first four
digits must consist of {\tt 2},{\tt 2},{\tt 5},{\tt 7} permuted in any way,
with the last four digits being the reverse of the permutation. 

Therefore, the total number of symmetric numbers is $\frac{4!}{2!1!1!}=12$.
On the other hand, the number of all possible permutations of the 9 integers is
$\frac{8\cdot8!}{4!2!2!1!}$. Since each number is equally likely to appear, the
probability that $p$ is symmetric is
$\frac{12}{\frac{8\cdot8!}{4!2!2!1!}}=\frac{1}{280}$. 
}
\eparts
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset9 problem5 spring98
\problem \goals{Discrete Probability, teams}
There are 4 coins in a box, namely $c_1, c_2, c_3, c_4$. The probability
$p_i$ that the coin $c_i$ gives a Head is $\frac{1}{i}$ for $1\leq i\leq4$.
A coin is selected from the box randomly, and is being tossed until a Head is
seen. 

\bparts
\ppart
Write down the sample space of the experiment
\solution{
The sample space is
$\{(c_1,H)\}\cup\{c_2,c_3,c_4\}\times\{H,TH,TTH,TTTH,\dots\}$
}
\ppart
What is the probability that a Head is first seen in the $2^{nd}$ toss? 
\solution{
For this part and the following part, let $H_i$ be the event that ``a Head is first seen in the $i^{th}$ toss''. Let $C_i$ be the event that ``$c_i$ is drawn from the box''.

\begin{eqnarray*}
P(H_2)  &=&P(H_2|C_1)P(C_1)+P(H_2|C_2)P(C_2)+P(H_2|C_3)P(C_3)+P(H_2|C_4)P(C_4)\\
        &=&0\cdot\frac{1}{4}+\underbrace{\frac{1}{2}\cdot\frac{1}{2}}_{P(H_2|C_2)}\cdot\frac{1}{4}+\underbrace{\frac{2}{3}\cdot\frac{1}{3}}_{P(H_2|C_3)}\cdot\frac{1}{4}+\underbrace{\frac{3}{4}\cdot\frac{1}{4}}_{P(H_2|C_4)}\cdot\frac{1}{4}\\
        &=&\frac{95}{576}\\
\end{eqnarray*}
}
\ppart
Given that a Head is first seen in the $2^{nd}$ toss, what is the 
probability that $c_i$ is selected from the box?
\solution{
\begin{eqnarray*}
P(C_i|H_2)&=&\frac{P(C_i\cap H_2)}{P(H_2)}\\
         &=&\frac{P(H_2|C_i)P(C_i)}{P(H_2)}\\
         &=&\frac{\frac{i-1}{i}\cdot\frac{1}{i}\cdot\frac{1}{4}}{\frac{95}{576}}\\
         &=&\frac{144(i-1)}{95i^2}
\end{eqnarray*}

{\bf Checking:} $P(C_1|H_2)+P(C_2|H_2)+P(C_3|H_2)+P(C_4|H_2)=0+\frac{144}{95\cdot4}+\frac{144\cdot2}{95\cdot9}+\frac{144\cdot3}{95\cdot16}=1$. This makes sense.
}
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem \goals{Discrete Probability, teams}
Each person carries a certain, rare disease
with probability 1 in 1000.  Two doctors claim to be able to test for
the disease before symptoms appear.

\begin{problemparts}

\problempart Doctor $A$ was educated at Harvard Medical School and
employs the latest high-tech test.  If a patient has the disease, then
the test comes back positive 99\% of the time.  If the patient does
not have the disease, then the test comes back negative 97\% of the
time.  What is the probability that Doctor $A$ correctly diagnoses a
patient?

\solution{
\begin{eqnarray*}
\Pr(\text{$A$ is correct})
    & = &   \Pr(\text{is diseased} \cap \text{test positive}) \\
    &   &   \mbox{} +
        \Pr(\text{not diseased} \cap \text{test negative}) \\
    & = &   \Pr(\text{is diseased}) \cdot
        \Pr(\text{test positive} \mid \text{is diseased}) \\
    &   &   \mbox{} +
        \Pr(\text{not diseased}) \cdot
        \Pr(\text{test negative} \mid \text{not diseased}) \\
    & = &   0.001 \cdot 0.99 + 0.999 \cdot 0.97 \\
    & \approx & 0.970
\end{eqnarray*}
}

\problempart Doctor $B$ (a quack from MIT) murmurs strange chants and burns incense.
With probability 1 in 1000, Doctor $B$ says that a patient has the
disease, regardless of whether or not the patient actually does.  What
is the probability that Doctor $B$ correctly disgnoses a patient?

\solution{
\begin{eqnarray*}
\Pr(\text{$B$ is correct})
    & = &   \Pr(\text{is diseased} \cap \text{test positive}) \\
    &   &   \mbox{} +
        \Pr(\text{not diseased} \cap \text{test negative}) \\
    & = &   \Pr(\text{is diseased}) \cdot
        \Pr(\text{test positive} \mid \text{is diseased}) \\
    &   &   \mbox{} +
        \Pr(\text{not diseased}) \cdot
        \Pr(\text{test negative} \mid \text{not diseased}) \\
    & = &   0.001 \cdot 0.001 + 0.999 \cdot 0.999 \\
    & \approx & 0.998
\end{eqnarray*}
}

\problempart Which doctor makes more errors? And how often, 
compared to the other?

\solution{

\textbf{Solution:}\\
Doctor $A$ makes about 15 times more errors than Doctor
$B$.}

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\ignore{
\problem {\bf Testing for Defective Chips and False Positives}

Intel has discovered a flaw in their newest mircoprocessor which
causes division errors, with catastrophic results. Luckily for them,
it only affects 1 chip in 1000, so they do not have to redesign the
whole thing -- they can just test each chip for the flaw and throw out the
bad ones. 

They have devised a {\it chip test} with  the
following accuracy: in 99 percent of the cases where the flaw is
present, the test will return ``Positive: chip flawed'' in which case the
chip is thrown out, and in 95 percent of the
cases in which the flaw is not present, the test will return ``Negative: chip OK''.

What percentage of the chips that they throw out will actually divide
without any problems (or borrowing terminology from the medical world,
what is the percentage of false positives for the chip-test)?

\solution{

We are given that $\prob{\text{chip is flawed}} = 0.001$ and
$\prob{\text{chip is OK}} = 0.999$.  We also know the following
probabilities:
\begin{eqnarray*}
\prob{\text{Test outcome is ``Positive: chip flawed''} \mid \text{chip is flawed} } &=& 0.99 \\
\prob{\mbox{Test outcome is ``Negative: chip OK''} \mid \text{chip is flawed} } &=& 0.01 \\
\prob{\mbox{Test outcome is ``Positive: chip flawed''} \mid \text{no flaw present}} &=& 0.05\\
\prob{\mbox{Test outcome is ``Negative: chip OK''} \mid \text{no flaw present}} &=& 0.95
\end{eqnarray*}
With these probabilities, we can construct a tree as in Lecture Notes
\#19 (see Figure~\ref{flaw}).  Then, we use the product rule to determine:

\begin{figure}[ht]\label{flaw}
\centerline{\resizebox{!}{4in}{\includegraphics{figures/chip-flaw}}}
\caption{Possibility Tree for a Chip Test}
\end{figure}

\begin{eqnarray*}
\lefteqn{\prob{\text{chip is flawed} \mid \text{Test outcome was ``Positive: chip flawed''}}}\\
& = & \frac{\prob{\mbox{chip is flawed and test outcome is
``Positive: chip flawed''}}}{\prob{\mbox{Test outcome was ``Positive: chip flawed''}}} \\ 
& = & \frac{0.00099}{0.04995 + 0.00099} \\ 
& = & \frac{0.00099}{0.05094} = 0.019
\end{eqnarray*} \\ 
Thus, the percentage of false positives is 98.1\% --
which may come as a surprise!
}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset9 problem7 spring98
\ignore{%
\problem

A house is installed with a fire alarm to prevent fire accidents. If there 
is a fire, the probability for the fire alarm being turned on is 96\%. 
Even without a fire, the alarm may be turned on with a probability of 2\%. 
Suppose the probability for a fire accident to happen in the house is 1\%. 
If the fire alarm is now on, what is the conditional probability that there
is really a fire accident?

\solution{
{\bf Solution}

Let $F$ be the event that ``a fire accident happens''. Then let $A$ be the
event that ``the alarm is on''.

From the question, we have:
\begin{itemize}
\item $P(A|F)=0.96$
\item $P(A|\overline{F})=0.02$
\item $P(F)=0.01$
\end{itemize}

We want to find:
\begin{eqnarray*}
P(F|A)&=&\frac{P(F\cap A)}{P(A)}\\
      &=&\frac{P(A|F)P(F)}{P(A|F)P(F)+P(A|\overline{F})P(\overline{F})}\\
      &=&\frac{0.96\times 0.01}{0.96\times0.01+0.02\times0.99}\\
      &=&\frac{16}{49}
\end{eqnarray*}
}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%  Fall 2000  PS 10   %%%%%%%%%%%%%%   %%%%%%%%%%%%%%%

\problem \goals{Discrete Probability, teams}

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 $C$ is independent of $A$, and $C$ is independent of $B$, then
$C$ is independent of $A \union B$.

\solution{
\medskip\textbf{Solution:}

The statement is false.  For example, let $A$ and $B$ be unbiased
independent bits, \ie $A$ and~$B$ are independent events such that
$\Pr(A) = \Pr(B) = 1/2$ and let $C = A \oplus B$, \ie an event which
occurs iff exactly one of $A$ and~$B$ occurs. Then $C$ is independent
from both $A$ and $B$, but it is not independent from $A \cup B$, the
latter being an event occurring when either $A$ or~$B$ occurs. For,
\begin{gather*}
  \Pr(C \mid A) = \frac{\Pr(C \intersect A)}{\Pr(A)}
  = \frac{1/4}{1/2} = \frac{1}{2}\,, \\
  \Pr(C \mid B) = \frac{\Pr(C \intersect B)}{\Pr(B)}
  = \frac{1/4}{1/2} = \frac{1}{2}\,.
\end{gather*}
However,
\begin{displaymath}
  \Pr(C \mid (A \union B))
  = \frac{\Pr(C \intersect (A \union B))}{\Pr(A \union B)}\,.
\end{displaymath}
Obviously, $\Pr(A \union B) = 1 - \Pr(\bar{A} \intersect \bar{B}) =
3/4$. Furthermore
\begin{displaymath}
  \Pr(C \intersect (A \union B))
  =
  \Pr((C \intersect A) \union (C \intersect B))
  =
  \Pr(C \intersect A) + \Pr(C \intersect B) - 
  \Pr(A \intersect B \intersect C)
  =
  \frac{1}{4} + \frac{1}{4} - 0
  =
  \frac{1}{2}\,,
\end{displaymath}
which implies that
\begin{displaymath}
  \Pr(C \mid (A \union B)) = \frac{1/2}{3/4} = \frac{2}{3}\,.
\end{displaymath}
For a more pictorial description, consider Figure \ref{counterexample}.
\begin{figure}
  \begin{center}
    \includegraphics[height=4cm,keepaspectratio=true]{figures/ps9-counterexample}
    \caption{A counterexample for 5a}
    \label{counterexample}
  \end{center}
\end{figure}

}

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

\solution{ \ssl
The statement is true. Now let's prove it.
From what we are given, we know that \[
\Pr[C]=\Pr[C|A]=\Pr[C|B]=\Pr[C|A\intersect B]=\frac{\Pr[C\intersect A]}{\Pr[A]}=\frac{\Pr[C\intersect B]}{\Pr[B]}=\frac{\Pr[C\intersect(A\intersect B)]}{\Pr[A\intersect B]}
\]

We want to prove that $C$ is independent of $A\cup{B}$, that is
\[
\Pr[C]=\Pr[C|A\union B]=\frac{\Pr[C\intersect(A\union B)]}{\Pr[A\union B]}
\]
We observe that the denominator $\Pr[A\union B]$ looks suspiciously ``related'' to the denominators of the last 3 fractions above. We recall from high school that if $\frac{a}{b}=\frac{c}{d}=\frac{e}{f}\ldots$ then $\frac{a}{b}=\frac{c}{d}=\frac{e}{f}\ldots =\frac{a+c+e+\ldots}{b+d+f+\ldots}$. In other words, if we have a bunch of equal fractions, we can add all the numerators together and all the denominators together, and we still get the same fraction. Applying this to the first relation above we get:
\[
\Pr[C]=\frac{\Pr[C\intersect A]}{\Pr[A]}=\frac{\Pr[C\intersect B]}{\Pr[B]}=\frac{-\Pr[C\intersect(A\intersect B)]}{-\Pr[A\intersect B]}=\frac{\Pr[C\intersect A]+\Pr[C\intersect B]-\Pr[C\intersect(A\intersect B)]}{\Pr[A]+\Pr[B]-\Pr[A\intersect B]}
\]
Well, we observe that the denominator is just $\Pr[A\union B]$, and the numerator, after some manipulation, is indeed $C\intersect(A\union B)$. Therefore, we have just proven that
\[
\Pr[C]=\frac{\Pr[C\intersect A]+\Pr[C\intersect B]-\Pr[C\intersect(A\intersect B)]}{\Pr[A]+\Pr[B]-\Pr[A\intersect B]}=\frac{\Pr[C\intersect(A\union B)]}{\Pr[A\union B]}=\Pr[C|A\union B]
\]
Therefore, $C$ is independent of $A\cup{B}$.

\remove{
It is true.  To prove it, observe by the Sum Rule that
\begin{eqnarray*}
\lefteqn{\prob{x\in(C\cap(A\cup B))}}\\
& = &  \prob{x\in(C\cap(A- B))} +\prob{x\in(C\cap(B- A))} + \prob{x\in(C\cap(A\cap B))},
\end{eqnarray*}
and then that 
\[
\prob{x\in(C\cap(A - B))} + \prob{x\in(C\cap (A \cap B))}
= \prob{x \in (C\cap A)}
\]
also by the Sum Rule.  Then use the fact that $C$ is independent of
both $A$ and $A \cap B$ to get that $C$ is independent from $A - B$, and
similarly that it is independent from $B - A$.
}
}
\eparts
 
\ignore {
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%                     
\problem \goals{Discrete Probability, teams}
Compute the probabilities of the following
three events and determine which one is most likely.  Assume that the
dice are fair, 6-sided, and mutually independent.

\begin{problemparts}
\problempart Rolling at least one 6 when six dice are rolled.

\solution{
\medskip
\textbf{Solution:}
\medskip
The probability of rolling a 6 on a particular die is
$\frac{1}{6}$.  The probability of not rolling a 6 on a particular die
is $\frac{5}{6}$, since this is the complementary event.  The
probability of not rolling a 6 on any of six dice is
$(\frac{5}{6})^6$, since the numbers rolled are mutually independent.
The probability of rolling a 6 on some die is therefore $1 -
(\frac{5}{6})^6 = 0.665\ldots$.  }

\problempart Rolling at least two 6's when twelve dice are rolled.

\solution{
\medskip
\textbf{Solution:}
\medskip
The probability of rolling two or more 6's is 1 minus the
probability of rolling zero or one 6's.  The probability of rolling
zero 6's is $(\frac{5}{6})^{12}$, arguing as before.  The probablity
of rolling exactly one 6 is

\[
12 \cdot \frac{1}{6} \cdot \left(\frac{5}{6}\right)^{11}
\]

since there are 12 ways to choose the die that comes up 6, the
probability of this die coming up 6 is $\frac{1}{6}$, and the
probability of the remaining dice all coming up in the range 1 to 5 is
$(\frac{5}{6})^{11}$.

Overall, the probability of rolling two or more sixes is therefore

\begin{eqnarray*}
1 - \left(\frac{5}{6}\right)^{12} -
    12 \cdot \frac{1}{6} \cdot \left(\frac{5}{6}\right)^{11}
        & = &   0.618\ldots.
\end{eqnarray*}
}

\problempart Rolling at least three 6's when eighteen dice are rolled.

\solution{
\medskip
\textbf{Solution:}
\medskip
Arguing as before, the probability of rolling at least three 6's is

\begin{eqnarray*}
1   - \left(\frac{5}{6}\right)^{18}
    - 18 \cdot \frac{1}{6} \cdot \left(\frac{5}{6}\right)^{17}
    - \binom{18}{2} \cdot \left(\frac{1}{6}\right)^2 \cdot
        \left(\frac{5}{6}\right)^{16}
    & = &   0.597\ldots.
\end{eqnarray*}
}

\end{problemparts}

\solution{
\medskip
\textbf{Solution:}
\medskip
The first event is most likely.}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem \goals{Discrete Probability, teams} %{\bf Independence}
\textbf{The Flippant Juror}

A three-person jury has two responsible members, each of whom
independently has a probability $p> 1/2$ of making the correct decision.
The third juror flips a 50-50 coin for each decision.  So a one-person
jury with a responsible juror has probability $p$ of making the correct
decision.  Suppose the three-person jury decides by majority.  Which jury
has the better probability of making the correct decision, a
one-repsonsible-person jury or the three-person jury?

\solution{

Suppose the members of the 3-person jury are Socrates, Plato, and
Homer Simpson.  Socrates and Plato have both independently a probability
$p$ of making the right choice, and Homer just flips a coin.
Here are the events in which case the 3-person jury could be right:
\begin{itemize}
\item
Socrates and Plato are both right, (in which case what Homer says is irrelevant, as the
majority rules): probability of this event is  $p^2$;

\item
Socrates is right, Plato is wrong, and Homer is right: probability of this event is $\frac{1}{2}
p (1-p)$;

\item
Socrates is wrong, Plato is right, and Homer is right: probability of this event is $\frac{1}{2}
p (1-p)$.
\end{itemize}

These events are disjoint, so the probability that one of them occurs
is the sum $p^2 + p(1-p) = p$.  Thus the 3-person jury and the
1-person jury have the {\it same} probability of making the correct
decision.

}

\ignore{
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem \textbf{Birthdays Again}

Suppose there are 120 people in a room. Assume that their
birthdays are independent and uniformly distributed. As stated in
lecture notes, with probability $> 99\%$ there will be two that have
the same birthday.

Now suppose you find out the birthdays of all the people in the room
except one---call her ``Jane''---and find all 119 dates to be different.

\begin{problemparts}

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

\solution{

Here's the problem with the argument: Let $A$ be the event that some two
people in the room have the same birthday.  Let $B$ be the event that the
119 people we asked all have different birthdays.

It is true that $\prob{A} > 0.99$ (that is indeed the probability
spoken about in the lecture notes). However, that is the \emph{a
priori} probability, i.e., assuming all the birthdays are
uniform and independent, with no other constraints. The argument
above makes the erroneous assumption that event $A$ has
probability of at least $99\%$ even once we know that event $B$
holds. But once we know that event $B$ holds, the birthdays are
no longer independent. Thus $\prob{A \mid B}$ is not necessarily
equal to $\prob{A}$ (in our case, they are actually quite
different, as will be computed in part~(b)).
}


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

\solution{
Let $S$ be the set of birthdays of the 119 people in the room
other than Jane. By assumption, $|S| = 119$. 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
\begin{align*}
\prob{b\in S\mid B} = \frac{|S|}{365} = \frac{119}{365} \approx
32.6\%,
\end{align*}
where $B$ is the event that the 119 people we asked all have
different birthdays.
}
\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem  %Mutually Independent Events: modified from 96

Suppose $n$ balls are thrown randomly into $n$ boxes, so each ball lands
in each box with uniform probability.  Also, suppose the outcome of each
toss is independent of all the other tosses.

\bparts

\ppart Let $X_i$ be an indicator random variable whose value is $1$ if box
$i$ is empty and $0$ otherwise.  Write a simple closed form expression for
the probability distribution of $X_i$.   Are $X_1, X_2, \ldots, X_n$
independent random variables?

\solution{

The probability that box $i$ is empty is the
probabilility that all $n$ balls land in other boxes, which is
$(\frac{n-1}{n})^n=(1 - \frac{1}{n})^n$.  Thus $\prob{X_i=1}= (1 -
\frac{1}{n})^n$ and $\prob{X_i=0}=1 - (1 - \frac{1}{n})^n$.

The $X_i$'s are not independent as $\prob{X_1=X_2=\cdots =
X_n=0}=0$, whereas $\prod_{i=1}^n \prob{X_i = 0}\neq 0$.  }

\ppart Show that $\prob{\text{at least $k$ balls fall in the first box}}
\leq {\binom{n}{k}} \left(\frac{1}{n}\right)^k$ \\

\solution{
For any subset $S$ of $k$ balls, let $E_S$ be the event that 
each of these balls falls in box~1.
There are $\binom{n}{k}$ such events, corresponding to each subset of 
$k$ balls, and these events intersect.
We are intestested in the probability of the union of these events,
which is at most the sum of their individual probabilities:
$\prob{ \bigcup_S E_S} \leq \sum_S \prob{E_S}$.
For any fixed set $S$, $\prob{E_S}=\left(\frac{1}{n}\right)^k$, 
since we don't care where other balls land.
Thus, the probability that at least $k$ balls fall in box 1 is at most
${\binom{n}{k}} \cdot \left( \frac{1}{n}\right)^{k}$.
}

\ppart Let $R$ be the maximum of the numbers of balls that land in each of
the boxes.  Use Stirling's formula and the result from the previous
problem part to give an upper bound for $\prob{R\geq k}$.  (Hint: Use the
previous part to show that $\prob{\text{$k$ or more balls fall in some
box}}\leq n/k!$.)

\solution{
From previous part we know that for any $1\leq i\leq n$,
\begin{equation*}
\prob{\text{at least $k$ balls fall in the $i$th box}}\leq
\binom{n}{k} \cdot \left( \frac{1}{n}\right)^{k}.      
\end{equation*}

Expanding, we get 
\begin{equation*}
\binom{n}{k} \cdot \left(\frac{1}{n}\right)^k =
\frac{n(n-1)\cdots(n-k+1)}{k!n^k}
= \frac{n}{n} \cdot \frac{n-1}{n} \cdots \frac{n-k+1}{n}
\cdot \frac{1}{k!} \leq \frac{1}{k!}.
\end{equation*}
Therefore, 
\begin{equation*}
\prob{\text{at least $k$ balls fall in some box}}\leq 
\sum_{i=1}^n \prob{\text{at least $k$ balls fall into the $i$th
box}}\leq \frac{n}{k!}.
\end{equation*}

$R \geq k$ exactly when some box has at least $k$ balls, 
so using Stirling's formula, 
\begin{equation*}
\prob{{R\geq k}} \leq n \frac{1}{\sqrt{2\pi k}}
\left(\frac{e}{k}\right)^k.
\end{equation*}
}
\eparts
}

\end{problems}

\end{document}                            

