\documentclass[12pt,twoside]{article}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{graphics}
\input{macros-course}
\begin{document}

%\newcommand{\solution}[1]{}
%\pset{9}{November 10, 1998}{Start of class on November 17, 1998}

\newcommand{\solution}[1]{\bigskip #1}
\psol{9}{November 20, 1998}

\begin{problems}

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

\problem {\bf (10 points)}  Suppose that you are the contestant on a
variant of {\em Lets Make a Deal} where the keys to a new Corvette are
behind one door, tickets for a dream vacation are behind a second
door, and there is a diminutive, stuffed pig behind a third door.  You
do not know which door conceals which prize.  Your objective is to
maximize your probability of winning the pig.

As before, you pick a door initially.  Carol then opens a different
door.  Specifically, if you picked the door concealing the pig or the
keys, then she reveals the tickets.  If you picked the door concealing
the tickets, then she reveals the keys.  You can then either stay with
your original door or switch to the remaining, closed door.  You are
awarded the prize behind the door that you choose at this second
stage.

In substance, this variant differs from the original in that you know
Carol's door-opening rules.  This may give you a slight edge.  Give a
strategy that maximizes your probability of winning the pig and prove
that no better strategy exists.

\solution{Let $p$ be the probability that you switch if you are shown
the tickets, and let $q$ be the probability that you switch if you are
shown the keys.  The tree diagram below illustrates the various cases.

\bigskip
\centerline{\resizebox{!}{3.0in}{\includegraphics{Sol9-pigfind.eps}}}
\bigskip

Your probability of winning is therefore

\begin{eqnarray*}
\frac{p}{3} + \frac{q}{3} + \frac{1-p}{3}
	& = &	\frac{1}{3} + \frac{q}{3}.
\end{eqnarray*}

This expression achieves its maximum value of $\frac{2}{3}$ when $q =
1$.  This means that in an optimal strategy, you always switch if you
are shown the keys.  Your action when you are shown the tickets
does not affect your chance of winning.}

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

\problem {\bf (10 points)} In each problem part, either define a probability
space and events $A$, $B$, and $C$ such that all the equations hold
simultaneously, or else prove that no such probability space and
events exist.

\begin{problemparts}

\problempart
\begin{eqnarray*}
\Pr(A \mid B)		& = &	\frac{1}{4} \\
\Pr(A \mid C)		& = &	\frac{1}{4} \\
\Pr(A \mid B \cap C)	& = &	\frac{3}{4}
\end{eqnarray*}

\solution{These events can exist, as indicated in the diagram below.
Empty regions have zero probability.

\bigskip
\centerline{\resizebox{!}{1.5in}{\includegraphics{Sol9-set1.eps}}}
\bigskip
}

\problempart
\begin{eqnarray*}
\Pr(A \mid B)		& = &	\frac{3}{4} \\
\Pr(A \mid C)		& = &	\frac{3}{4} \\
\Pr(A \mid B \cap C)	& = &	\frac{1}{4}
\end{eqnarray*}

\solution{These events can exist, as indicated in the diagram below.

\bigskip
\centerline{\resizebox{!}{1.5in}{\includegraphics{Sol9-set2.eps}}}
\bigskip
}

\problempart
\begin{eqnarray*}
\Pr(A \mid B)		& = &	\frac{3}{4} \\
\Pr(A \mid C)		& = &	\frac{3}{4} \\
\Pr(A \mid B \cup C)	& = &	\frac{1}{4}
\end{eqnarray*}

\solution{These events can not exist.  At least one of the events $B$ or
$C$ must be at least half as likely as $B \cup C$.  Without loss of
generality, assume that this is true for event $B$; that is,

\begin{eqnarray*}
\frac{\Pr(B)}{\Pr(B \cup C)}	& \geq &	\frac{1}{2}.
\end{eqnarray*}

The first equation implies that

\begin{eqnarray*}
\frac{\Pr(A \cap B)}{\Pr(B)}	& = &		\frac{3}{4}.
\end{eqnarray*}

Multiplying the equation and the inequality above gives

\begin{eqnarray*}
\frac{\Pr(A \cap B)}{\Pr(B \cup C)}	& \geq &	\frac{3}{8}.
\end{eqnarray*}

Note that the set $A \cap (B \cup C)$ contains the set $A \cap B$.
Therefore, $\Pr(A \cap (B \cup C)) \geq \Pr(A \cap B)$.  Substituting
this fact into the preceding inequality gives

\begin{eqnarray*}
\frac{\Pr(A \cap (B \cup C))}{\Pr(B \cup C)}	& \geq &	\frac{3}{8}.
\end{eqnarray*}

Consequently, $\Pr(A \mid B \cup C) \geq \frac{3}{8} > \frac{1}{4}$,
contradicting the third equation.
}

\end{problemparts}

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

\problem {\bf (10 points)}  Suppose that I pick a pair of distinct numbers in
the range $1$ to $10$ uniformly at random.

\begin{problemparts}

\problempart If one of the numbers is even, then
what is the probability that the other number is even?

\solution{The sample space consists of the $\binom{10}{2} = 45$ pairs
of distinct numbers in the range $1$ to $10$.  Since the sample space
is uniform, each outcome has probability $\frac{1}{45}$.  With this
observation, we can compute the probability of an event by counting
the number of outcomes in the event and then multiplying by
$\frac{1}{45}$.

Let $E$ be the event that at least one number is even, and let $B$ be
the event that both numbers are even.  We must compute

\begin{eqnarray*}
\Pr(B \mid E)	& = &	\frac{\Pr(B \cap E)}{\Pr(E)} \\
		& = &	\frac{\Pr(B)}{\Pr(E)}
\end{eqnarray*}

The second equality holds because $B$ is contained in $E$; that is, if
both number are even, then at least one of the numbers is even.

Since there are 5 even numbers in the range 1 to 10, the event $B$
contains $\binom{5}{2} = 10$ outcomes and thus has probability $10
\cdot \frac{1}{45} = \frac{2}{9}$.  The event $E$ consists of all pairs of
numbers in the range 1 to 10 that are not both odd.  That is, event
$E$ contains $45 - \binom{5}{2} = 35$ outcomes, and thus has
probability $35 \cdot \frac{1}{45} = \frac{7}{9}$.

Substituting these probabilities into the above equation gives

\begin{eqnarray*}
\Pr(B \mid E)	& = &	\frac{\Pr(B)}{\Pr(E)} \\
		& = &	\frac{\frac{2}{9}}{\frac{7}{9}} \\
		& = &	\frac{2}{7}.
\end{eqnarray*}
}

\problempart If one of the numbers is a 2, then
what is the probability that the other number is even?

\solution{ Let $T$ be the event that one number is 2, and let $U$ be
the event that one number is 2 and the other is even.  We must compute

\begin{eqnarray*}
\Pr(U \mid T)	& = &	\frac{\Pr(U \cap T)}{\Pr(T)} \\
		& = &	\frac{\Pr(U)}{\Pr(T)}
\end{eqnarray*}

The event $T$ consists of 9 outcomes, since every pair must contain 2
and there are 9 choices for the other number ($1, 3, 4, \dots, 10$).
The event $U$ consists of 4 outcomes, since every pair must contain a
2 and there are 4 choices for the other number ($4, 6, 8, 10$).
Therefore, we have:

\begin{eqnarray*}
\Pr(U \mid T)	& = &	\frac{\Pr(U)}{\Pr(T)} \\
		& = &	\frac{\frac{4}{45}}{\frac{9}{45}} \\
		& = &	\frac{4}{9}.
\end{eqnarray*}
}

\end{problemparts}

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

\problem  {\bf (10 points)}  Three gunfighters, $A$, $B$, and $C$, plan
to fight a three-cornered pistol duel.  They all 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$.  On his turn, a gunfighter may target either
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.  What should
gunfighter $A$ do on his first shot and what probability of survival
does this give him?

\solution{Suppose that $A$ shoots into the air.  Then $B$ shoots $C$,
and $A$ gets one shot to kill $B$ before he himself is killed.
Therefore $A$ has a $0.3$ chance of survival.

Suppose that $A$ shoots at $B$.  If he hits, then he enters a duel
with $C$, where $C$ gets the first shot.  In this case, let $p$ be the
probability that he 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{eqnarray*}
p	& = &	0.5 \cdot 0.3 + 0.5 \cdot 0.7 \cdot p \\
	& = &	\frac{3}{13}
\end{eqnarray*}

Thus, If $A$ hits $B$, then his odds of survival are lower than if he
fires into the air.  On the other hand, suppose that $A$ shoots at
$C$.  If he hits, then $B$ immediately kills him.

Therefore, $A$'s best strategy is to fire into the air.  This gives
him a $0.3$ chance of survival.}

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

\problem {\bf (10 points)}  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{Sol9-prisoner.eps}}}
\bigskip

Plugging these probabilities into the preceding equation gives

\begin{eqnarray*}
\Pr(\text{$A$ released} \mid \text{guard says $B$ released})
	& = &	\frac{\frac{1}{3}}{\frac{1}{2}} \\
	& = &	\frac{2}{3}
\end{eqnarray*}

If the guard says that $B$ will be released, then $A$ still has a
$\frac{2}{3}$ chance of release.
}

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

\problem {\bf (10 points)} Suppose that {\em Let's Make a Deal} is modified
so that there are four doors.  As before, a prize is hidden behind one
door.  The contestant picks a door, Carol opens a different door to
reveal no prize, and then the contestant is allowed to stay with his
or her original door or to pick one of the other two that are still
closed.  If the contestant chooses the door concealing the prize in
this second stage, then he or she wins it.

\begin{problemparts}

\problempart Contestant Stu, a sanitation engineer from Trenton, New Jersey,
stays with his original door.  What is the probability that he wins
the prize?

\solution{Stu guesses the right door initially with probability
$\frac{1}{4}$ and guesses the wrong door with probability
$\frac{3}{4}$.  If he was right initially, then he surely wins the
prize.  If he was wrong initially, then he surely does not win the
prize.  Therefore, his probability of winning is $\frac{1}{4} \cdot 1
+ \frac{3}{4} \cdot 0 = \frac{1}{4}$.
}

\problempart Contestant Zelda, an alien abduction researcher from Helena,
Montana, randomly picks one of the other two doors with equal
probability.  What is the probability that she wins the prize?

\solution{Zelda also guesses the right door initially with probability
$\frac{1}{4}$ and guesses the wrong door with probability
$\frac{3}{4}$.  If she was right initially, then she can not win.  If
she was wrong initially, then she wins with probability $\frac{1}{2}$.
Therefore, her probability of winning is $\frac{1}{4} \cdot 0 +
\frac{3}{4} \cdot \frac{1}{2} = \frac{3}{8}$.
}

\end{problemparts}

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

\problem {\bf (10 points)} Even if he is very, very careful, the probability
that Theory Pig can avoid ``provoking'' 6.042 TA Brian Dean is only a
small, positive constant $\epsilon$.  If Theory Pig does ``provoke''
Brian, then the probability that Brian will refrain from doing
something really wicked to our porky pal is only a small, positive
constant $\delta$.

\begin{problemparts}

\problempart Compute a tight lower bound on the probability that Brian does
something really wicked to Theory Pig.

\solution{
Let $P$ be the event that Theory Pig provokes Brian.  Let $W$ be the
event that Brian does something wicked to Theory Pig.  From the
problem statement, we have:

\begin{eqnarray*}
\Pr(P)		& = &	1 - \epsilon \\
\Pr(W \mid P)	& = &	1 - \delta
\end{eqnarray*}

We can now reason as follows:

\begin{eqnarray*}
\Pr(W)		& \geq &	\Pr(W \cap P) \\
		& = &		\Pr(W \mid P) \cdot \Pr(P) \\
		& = &		(1 - \delta) \cdot (1 - \epsilon)
\end{eqnarray*}

The first step uses a fact that the event $W \cap P$ is a subset of the
event $W$.  The second step uses the definition of conditional
probability, and the final step is substitution.
}

\problempart Prove that your lower bound is tight; that is, describe
circumstances consistent with the problem statement such that the
probability that Brian does something wicked to Theory Pig is equal to
your lower bound.

\solution{
Suppose that Brian never does something really wicked unless he is
provoked.  That is, the event $W$ is contained in the event $P$.  Then
$W = W \cap P$, and the only inequality in the solution to the
previous problem part is an equality.  }

\end{problemparts}

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

\problem {\bf (15 points)}  Each morning Theory Pig pops out of his desk
drawer home--- all bright and perky--- and goes bounding off to play
around the Laboratory for Computer Science.  The desk drawer is
located at position $(0, 0)$.  At each time step, Theory Pig is
equally likely to bound north or east.  A northward bound increments
the first coordinate of his position, and an eastward bound increments
the second coordinate of his position.  (Assume that his direction at
one time step is independent of his direction at all other time
steps.)

At position $(4, 4)$, 6.042 TA Brian Dean is waiting with a bat, for
some reason.  What is the probability that Theory Pig visits position
$(4, 4)$ within his first 10 bounds?

\solution{
There are $2^{10}$ equally likely routes for Theory Pig.  He visits
position $(4, 4)$ if 4 of his first 8 bounds are north, 4 of his first
8 bounds are east, and his remaining two bounds are in any direction.
Therefore, Theory Pig visits $(4, 4)$ in

\begin{eqnarray*}
\binom{8}{4} \cdot 2^2	& = &	280
\end{eqnarray*}

of these outcomes.  Therefore, the probability that Theory Pig visits
position $(4, 4)$ within his first 10 bounds is

\begin{eqnarray*}
\frac{280}{2^{10}}	& = &	\frac{35}{128}.
\end{eqnarray*}
}

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

\problem {\bf (15 points)}  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{
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{
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{
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{
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}

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

\end{problems} \end{document}
