\documentstyle[12pt,twoside,macpsfig,amssymb,epsf]{article}
\input{macros-course}

\addtolength{\topmargin}{-.35in}
\setlength{\textheight}{9in}

\newcommand{\problm}{\problem \rm}
\renewcommand{\ppart}{\problempart \rm}
\newcommand{\soln}{\sf}
\newcommand{\mystrut}{\rule{0pt}{14pt}}

\begin{document}

\psol{9}{November 21, 1997}

\bigskip

\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 1
\problem{\bf [5 points]} 

Consider playing the {\it Lets Make a Deal}, where there are three prizes:
a ``Gift Certificate'' from Toscanini, a ``Nerd Pocket Protector'', and a 
``Nerd Pride Button''. Your goal is to win the gift certificate. 

\bparts
\ppart
Suppose you (the contestant) happen
to know that Carol always reveals the ``Nerd Pocket Protector'', if you 
did not choose the box covering it.

Does this additional information change the odds of winning for you? 
Is there a better strategy? By how much (if any) does this information
increase your chances of winning?

\bigskip

The probability of winning the game remains the same but now there is
more than one optimal strategy.  If Carol reveals the ``Nerd Pride
Button'' it means that you must have chosen the box covering the
``Nerd Pocket Protector''.  In this case, you win with probability 1
if you switch. If Carole shows you the ``Nerd Pocket Protector'' then
there is $1/2$ probability that you have picked the prize box, so you
win with probability $1/2$ whether you switch or not.  Let NPB be the event
that Carole shows the ``Nerd Pride Button'', and NPP be the event that
Carole shows the ``Nerd Pocket Protector''. Then the 
total probability of winning is:
\begin{eqnarray*}
Pr(win) &=& Pr(win \mid \mbox{NPB})Pr(\mbox{NPB}) + Pr(win \mid\mbox{NPP})
Pr(\mbox{NPP}) \\
        &=& 1 \cdot \frac{1}{3} + \frac{1}{2} \cdot \frac{2}{3} \\
        &=& \frac{2}{3}
\end{eqnarray*}

\ppart

You are playing according to the original assumptions, but before
you make your initial choice, you happen to see Carol placing a 
``Nerd Pride Button'' underneath Box~1.  What should you do to try to win 
the prize (the ice cream)?  What is the probability that you win?

\bigskip

In this case, you should always pick Box 1.  Monty 
will be forced to reveal the location of the other ``Nerd Pride'' pin.
Upon switching, you will be guaranteed to win the ice cream (i.e.
the probability of winning is 1).  If you
pick a box besides 1, Monty can always reveal Box 1 (giving you no
additional information), and you will have a 1/2 chance of winning.

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 2
\problem{\bf [10 points]}

Consider a three by three array of squares as in the game of tic-tac-to.

\bparts
\ppart
If three squares are picked at random (independently and with the same
probability), what is the probability that these squares will form a line?
(horizontal, vertical, or diagonal)

\bigskip

There are ${9 \choose 3}$ ways to choose three squares in the grid.
There are three ways three squares can form a horizontal line, three ways
they can form a vertical line, and two ways they can form a diagonal line.
So the probability that three randomly selected squares form a line is

${8 \over {9 \choose 3}} = {2 \over 21}$


\ppart
If you pick four squares at random, what is the probability that three
of them will be on a line?

\bigskip

There are ${9 \choose 4}$ ways to pick the squares.  For each line formed 
there are 6 ways to choose the position of the fourth square, so there are
$48$ that the squares will form a line.  The probability is

${48 \over {9 \choose 4}} = {8 \over 21}$.

\eparts
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 3
\problem{\bf [10 points]}\\

\bparts

\ppart
You roll two dice.  What is the probability that their sum is not 6?

\bigskip

There are five ways the sum can be 6: 
$(1,5),(5,1),(2,4),(4,2),(3,3)$

There are $6 \cdot 6 = 36$ ways the dice can land, so the probability 
that their sum is six is ${5 \over 36}$. Therefore the probability that the
sum is not six is $31 \over 36$.

\ppart 
You roll three dice. What is the probability that that any of the 
{\em pairwise} sums is not 6?

\bigskip

There are $6^3 = 216$ possible dice rolls.
Define the events:

$A_1 =  \{d_1 + d_2 \} = 6$\\
$A_2 =  \{d_2 + d_3 \} = 6$\\
$A_3 =  \{d_3 + d_1 \} = 6$\\

For each $A_i$, $P(A_i) = 5/36$.

We also have  $P(A_i \cap A_j) = 5/216$, while 
$P(A_1\cap A_2 \cap A_3) = 1/216$.

So

\begin{eqnarray*}
P(A_1 \cup A_2 \cup A_3) &= &
3P(A_i) - 3P(A_i \cap A_j) + P(A_1\cap A_2 \cap A_3)\\
&  = & { 90 - 15 +1 \over 216} = {76 \over 216}\\
\end{eqnarray*}

so the probability of not getting a six is $140/216$.
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 4
\problem{\bf [10 points]}

\bparts
\ppart 

\bigskip

Prove that $Pr(\overline{A}|C) = 1 - Pr(A|C)$ for any events $A$ and $C$.

\begin{eqnarray*}
1 - Pr(A|C) &=& 1 - {{Pr(A\cap C)}\over {Pr(C)}} \\
            &=& {{Pr(C) - Pr(A\cap C)}\over {Pr(C)}} \\
            &=& {{Pr(\overline{A}\cap C)}\over {Pr(C)}}\\
            &=& Pr(\overline{A}|C)
\end{eqnarray*}
\ppart

Is it possible for $Pr(A|B)$ and $Pr(A|C)$ to be very small, if 
$Pr(A|B\cap C)$ is large? Give a counterexample or a proof to justify 
your answer.

\bigskip

Yes, it is.  
Consider the uniform sample space $S=\{1,2,\ldots, 2 \cdot 10^6\}$. \\
Let $A = \{1\}, B = \{1,2,\ldots,10^6 \}, C = \{1,10^6+1,\ldots,2 \cdot 10^6 -1\}$. \\
Then $Pr(A \mid  B)  = Pr(A \mid C) = 10^{-6}$, while $Pr(A \mid B \cap C) = 1$.
 
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 5
\problem{\bf [5 points]}

Three Prisoners $A$,$B$, and $C$ have applied for parole.  The parole
board has decided to randomly choose two of the three to be released,
 and the prisoners know
this but not which two.  A warder friend of prisoner $A$ knows who are
to be released.  $A$ realizes that it would be unethical to ask if he
is going to be released, but thinks of asking for the name of {\em one
  prisoner other than himself} who is to be released. Before he asks
his chances are $2/3$, but he thinks that if he asks and the warder
says ``$B$ will be released'', his own chances will become $1/2$ since
either $A$ or $C$ will be the only remaining candidates.  So $A$
decides not to reduce his chances by asking.  Is $A$'s argument correct?
Show what his chances are after asking.
You may assume that if the warder has a choice of which name to reveal,
then he picks one at random.

\bigskip

\begin{figure}[htbp]
\centerline{\psfig{figure=ps9.eps,height=2.0in}}
\caption{Probability that Warder says B}
\label{fig:prisoner}
\end{figure}

Let $W_B$ be the event that the Warder says $B$.
From picture 1 we see that 
$P(W_B) = (1/3)(1/2) +(1/3)1 = 1/2$.

$A \cap W_B$ is the event that $A$ is released and the warder says $B$, which
is the same as the event that $A$ and $B$ are released, so 
$P(A \cap W_B) = 1/3$.

$P(A|W_B) = {P(A \cap W_B) \over P(W_B)} = 2/3$
so the chances of $A$ are not reduced by asking after all.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 6
\problem {\bf [10 points]}

We know from statistics that when a policeman gets shot he survives with
probability $0.8$ if he/she wears a bullet-proof vest and survives with
probability $0.12$ if the policeman doesn't wear a vest.
Given that 15\% of the policemen wear bullet-proof vests, what is the
probability that a random policeman was wearing a bullet-proof vest if he/she
survived a firearm attack?

\bigskip

Let $B$ be the event the policeman wears a vest.  Let $W$ be the
event the policeman survives an attack.
We want to compute $Pr(B|W)$.  By Bayes' theorem,
\[
Pr(B|W)=\frac{Pr(W|B)Pr(B)}{Pr(W|B)Pr(B)+Pr(W|\overline{B})Pr(\overline{B})}
= \frac{(0.8)(.15)}{(0.8)(0.15)+(0.12)(0.85)} =0.54
\]

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem {\bf [10 poiints]}

$A$, $B$, and $C$ are to fight a three-cornered pistol duel.  They all know 
that $A$'s chance of hitting the target is $0.3$, $C$'s is $0.5$ and $B$ 
never misses.  They are to shoot in the sequence $A,B,C$ and fire at their 
choice of target until one person is left standing.  Show that $A$ is better
off missing deliberately the first shot than attempting to hit either $B$ or 
$C$.

\bigskip

First consider a scenario where only $A$ and $C$ are left.
Let $S$ be the event that $A$ survives if $C$ shoots first.


$$
P(S) = 0.5(0.3+0.7 \cdot P(S)) \Rightarrow P(S) = 0.23
$$

Let's calculate $A$'s chances of survival under the three possible strategies.

\begin{enumerate}
\item If $A$ shoots $B$ first, then with probability $0.3$ he kills him and
 then we are in the above scenario.  If $A$ misses $B$, then $B$ kills $C$ and 
than $A$ has $0.3$ chance to hit $B$ and survive. So $A$'s probability of
survival under this strategy is $.3*P(S) + .7*.3 = .28$.

\item If $A$ shoots $C$ and kills him then he will be killed by $B$, while
if he misses, $B$ will kill $C$ and then $A$ has $0.3$ probability to get $B$
So $A$'s probability of survival is $0.7*.3 = 0.21$.

\item If $A$ misses deliberately then $B$ will kill $C$ and $A$ has probability
$0.3$ to survive.  

\end{enumerate}

So $A$ best strategy is to shoot in the air.  Under either strategy, $A$'s
chances are slim.  I wonder how he got himself into that.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 8
%Independence
\problem{\bf [10 points]}\\

\bparts

\ppart
Show that if two events $A$ and $B$ are independent, then the events $A$ 
and $\overline B$ are also independent.

\bigskip

$A$ and $B$ independent means $\Pr(A\cap B) = \Pr(A)\cdot \Pr(B)$.
We have to show $\Pr(A\cap \overline B) = \Pr(A)\cdot \Pr(\overline B)$.
Since  $A$ is the disjoint union of $(A\cap B)$ and $(A \cap \overline B)$ 
we have 
\[\Pr(A) = \Pr(A\cap B) + \Pr(A \cap \overline B)\] 
and therefore 
\begin{eqnarray*}
 \Pr(A\cap \overline B) &=& \Pr(A) - \Pr(A\cap B) \\
  &=& \Pr(A) - \Pr(A)\Pr(B) \\
  &=& \Pr(A)(1-\Pr(B)) \\
  &=& \Pr(A)\Pr(\overline B) \\
\end{eqnarray*}
proving that $A$ and $\overline B$ are independent.

\ppart

Two numbers $x$ and $y$ are selected at random from the set
 $\{1,\ldots,100\}$.  Let the events $A$, $B$ and $C$ be defined
 as follows: $A = \{x > 50\}$, $B = \{y > 50\}$ and $C=\{x > y \}$.
 Are the events $A$ and $B$ independent? Are $A$ and $C$ independent?

\bigskip

First of all we compute
$\Pr(A) = \Pr(B) = 50/100 = 0.5$ and 
$\Pr(C) = {100 \choose 2}\cdot 100^{-2} = 0.495$.

Since $\Pr(A\cap B) = (50\cdot 50)/100^2 = 0.25 = \Pr(A)\cdot\Pr(B)$,
$A$ and $B$ are independent.

\begin{eqnarray*}
\Pr(A\cap C) & = & \Pr(x>y \cap x>50)\\
& = & \sum_{i=51}^{100} \Pr(x>y \cap x=i)\\
& = & \sum_{i=51}^{100} \Pr(y<i)\Pr(x=i)\\
& = & (1/100) \sum_{i=51}^{100} \Pr(y<i)\\
& = & (1/100) \sum_{i=51}^{100} {i-1 \over 100}\\
& = & (1/100)(({100 \cdot 101 \over 2}-{50 \cdot 51 \over 2})(1/100)-49/100)\\
& = & 0.3726
\end{eqnarray*}

while $\Pr(A)\Pr(C) = .247$. So $A$ and $C$ are not independent.
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 8
\problem{\bf [10 points]}

You are given a coin of bias $p$ (prob of heads = $p$; tails = 1-$p$,
$0 < p < 1$). The value of $p$ is not known and you are not allowed to guess
by sampling

Using this, how can you get a coin of bias:

\begin{enumerate}

\item $p^2$

\bigskip

Flip twice. Let $B$ be the event that head appears both times.

\item ${1 \over 2} p^2 + {1 \over 4} p$

\bigskip

Here's how to make ${1 \over 2}$.  Flip twice. If the result is
HT you win. If it's TH you loose (note that each of these events occurs with
probability $p(1-p)$. If it's something else you repeat the
experiment.

Let $P_W$ denote the probability that you win.  Then $P_W$ obtains the
 recursion

$P_W = p(1-p)+(1-2p(1-p))P_W$

Solving for $P_W$ we get $P_W = 1/2$.

Let B be the event that you win.  We will refer to the experiment described as 
the ``fair experiment''

To form ${1 \over 2} p^2 + {1 \over 4} p$ conduct the fair experiment.
If you win, flip twice. If both flips are heads you win.  If you lose in the
fair experiment, repeat the fair experiment again and if you succeed flip the
coin.  If you get heads you win.  If the fair experiment fails again or if you
get tails you loose.

Let B be the event that you win.

Now we show that $P(B) = {1 \over 2} p^2 + {1 \over 4} p$.
Let F be the event that the fair experiment succeeds, and H the event
that the coin toss is heads.

\begin{eqnarray*}
P(B) & = & P(B|F)P(F) + P(B|\bar{F})P(\bar{F}) \\
&= & {1 \over 2} p^2 + {1 \over 2}P(B|\bar{F})\\
\end{eqnarray*}

Now $P(B|\bar{F}) = P(\text{both fair experiment and coin toss succed}) =
P(F \cap H) =  {1 \over 2}p$. So,

$$
P(B)  = {1 \over 2} p^2 + {1 \over 2}{1 \over 2}p =
{1 \over 2} p^2 + {1 \over 4}p
$$

\item ${1\over 2} - {1 \over 4}p$

\bigskip

Note that ${1\over 2} - {1 \over 4}p = 1 - \left( {1\over 2} + {1 \over 4}p
\right)$.

Perform the fair experiment.  If it succeeds you win. If it fails, perform
the fair experiment again. If it fails you lose. If it succeeds you flip 
the coin and win if you get heads.

Let $B$ be the event that you lose.

To prove that this works, let's calculate $P(\bar{B})$.

\begin{eqnarray*}
P(\bar{B}) & = & P(\bar{B}|F)P(F)+P(\bar{B}|\bar{F})P(\bar{F})\\
& = & {1 \over 2} + {1 \over 2}P(H)\\
& = & {1 \over 2} + {1 \over 2}p
\end{eqnarray*}
 
\end{enumerate} 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem{\bf [10 points]}

Consider three loaded dice such that

Die A always comes up 3\\
Die B is 2 with prob $p$ and 5 otherwise\\
Die C is 4 with prob $p$ and 1 otherwise.\\

Find a value for $p$ such that $A$ beats $B$, $B$ beats $C$, and $C$ beats $A$
 all with probability $p$.
 
\bigskip

It's clear that $A$ beats $B$ and $C$ beats $A$ with probability $p$. 
In order for $B$ to beat $C$ with probability $C$ we must have:

$$
(1-p)+p(1-p) = p \Rightarrow p^2+p-1 =0
$$

Solving this quadratic (and observing the restriction $0 \leq p \leq 1$),
we obtain $p = {\sqrt{5}-1 \over 2}$.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 11
\problem{\bf [10 points]}

In a complex system with 100,000 different components.
The system contains 10 critical components, each failing with probability
$1/1000$ and 100 secondary components each failing with probability $1/100$.
It is known that secondary failures are pairwise independent.
The system crashes if one critical component or two secondary components
fail. 

\bparts

\ppart
Determine an upper
bound on the probability that the system will crash.

\bigskip

Let $C_i$ be the event that critical component $i$ fails.
Let $S$ be the event that two secondary components fail.
We know that $P(C_i) = 1/1000$. 
There are $100^2 = 10000$ ways that to distribute failures among the
secondary components, and ${100 \choose 2}$ ways to choose the two components
that fail, so the probability that two components will fail is
${{100 \choose 2} \over 10000} = 99/200$.

$$
P(\text{system crashes}) = P(\cup_{i=1}^{10} C_i \cup S) 
\leq \sum_{i=1}^{10} P(C_i) + P(S) = .01 + .495 = .505
$$

\ppart 
Determine a lower bound on the probability that the system will crash.

\bigskip

In the best possible case all the critical components will fail
if and only if a critical component fails. In this case the probability 
that the system crashes is at least $1/1000$.  We will show that we can make
it exactly $1/1000$ as follows.

Suppose that $1/10$ of the time that a critical component fails,
all the secondary component's will fail.  (Thus all the secondary components
fail with probability $1/10000$).

Now let the probability of a a secondary component failing {\em conditioned}
on the event that no critical component fails be $99/9990$ and make these
events disjoint (so that no two secondary components can fail conditioned on 
the event that no critical component fails).

We have

$P(\text{A critical component fails}) = 1/1000$

$P(\text{A pair of secondary component fails}) = 
P(\text{All secondary component fail}) = 1/10000$

Let $S_i$ be the event that the $i$th secondary component fails.
Let $C$ be the event that some critical component (and therefore all of them)
fails.

\begin{eqnarray*}
P(S_i)& = & P(S_i \cap C) +P(S_i  \cap \bar{C})\\
& = & 1/1000 + P(S_i | \bar{C})P(\bar{C})\\
& = & 1/10000 + (99/9990) \cdot (999/1000)\\
& = & 1/10000 + (99/10000)\\
& = & 1/100
\end{eqnarray*}

So the system specifications are met and the probability that the system will
crash is $1/1000$.

\ppart
Where is the biggest weakness? In the critical, or in the secondary components?

\bigskip

In the secondary components.  The probability that a primary component fails 
is bounden above by $.01$ while the probability that some two secondary 
components will fail is almost 1/2.
\eparts

\end{problems}

\end{document}


% Local Variables: 
% mode: latex
% TeX-master: t
% End: 




