\documentclass[11pt, twoside]{article}
\usepackage{epsf}
\usepackage{psfig}
\input{macros-course}
\usepackage{graphics}
\usepackage[pdflatex]{graphicx}

\newcommand{\nand}{|}
\renewcommand{\implies}{\longrightarrow}

\askaboutsolutions

\begin{document}
\psol{9}{November 14, 2000}{2:35pm in lecture, Tuesday, November 21, 2000}

\textbf{Be sure to indicate your TA's name clearly on the solutions
your turn in}.

-----------------------------------------------------------------------------\\

\textbf{Self-study}
Read: Rosen Sections 4.4
Self-study problems (not to be handed in): 19, 21, 28, 31, 33.

-----------------------------------------------------------------------------\\

\textbf{Reading:}
Lecture notes;  Rosen 4.4

\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.
 
\medskip
\begin{problems}

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

\problem {\bf Lets Make a Deal {\em differently}}  

\begin{problemparts}

\problempart 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 compute
this probability.

\solution{
\textbf{Solution:}\\
For the ``stick'' strategy, the probability of winning the pig is clearly
$\frac{1}{3}$.

Let us now analyze the ``switch'' case.
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 shown below illustrates the various cases.

\bigskip
\begin{figure}[htbp]
\centerline{\psfig{figure=/a/class/6.042/fall00/handouts/fig/Sol9-pigfind.eps,height=3in}}
%\centerline{\includegraphics[height=3in]{/a/class/6.042/fall00/handouts/fig/Sol9-pigfind.pdf}}
\end{figure}
\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.}

\problempart Suppose that the gameshow is now 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. \\

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

\solution{

\textbf{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{

\textbf{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 Probability Spaces} 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{

\textbf{Solution:}\\
These events can exist, as indicated in the diagram below.
Empty regions have zero probability.

\bigskip
\begin{figure}[htbp]
\centerline{\psfig{figure=/a/class/6.042/fall00/handouts/fig/Sol9-set1.eps,height=2in}}
%\centerline{\includegraphics[height=2in]{/a/class/6.042/fall00/handouts/fig/Sol9-set1.pdf}}
\end{figure}
\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{

\textbf{Solution:}\\
These events can exist, as indicated in the diagram below.

\bigskip
\begin{figure}[htbp]
\centerline{\psfig{figure=/a/class/6.042/fall00/handouts/fig/Sol9-set2.eps,height=2in}}
%\centerline{\includegraphics[height=2in]{/a/class/6.042/fall00/handouts/fig/Sol9-set2.pdf}}
\end{figure}
\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{

\textbf{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  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{

\textbf{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{ 

\textbf{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 Tennis Tournaments.} A tennis tournament has 8 players. The
players are assigned randomly to positions in the first round of a
tournament ladder (see Figure 1).

\begin{figure}[htbp]
\centerline{\psfig{figure=/a/class/6.042/fall00/handouts/fig/H64-tennis.eps,height=4in}}
%\centerline{\includegraphics[height=4in]{/a/class/6.042/fall00/handouts/fig/H64-tennis.pdf}}
\end{figure}

\bparts
\ppart
Suppose the {\it best player} always defeats everybody else, and
the {\it second-best player} always defeats everybody but the best. What
is the chance that the second-best player makes it to the final round? 

\solution{
\textbf{Solution:}\\
In order to make it to the final round, the 
second-best player has to meet
the winner in the final round and not earlier.  
That happens if and only if the best
player and the second-best player start out in different brackets of
four; in other words, if the best player starts in position 1-4 of the
first round, then the second-best must start in positions 5-8, and
vice versa.

Here are two ways to determine the probability.  The first way counts
complete assignments: there are 8 ways to place the best player in the
first round, then 4 ways to place the second-best, then $6!$ ways to
place the remaining players.  Divide by the size of the sample space
($8!$, the total number of ways to assign all eight players with no
constraints) to get $4/7$.

The second way treats the second player's position as a random selection.
The best player can be placed anywhere.  Given the best player's position,
the second-best player will meet the first player in the final round
only if he is placed in 4 of the remaining 7 positions---not 4 out of 8,
because the best player is already occupying one (this is a common error
-- the positions of the players can't be treated like independent coin
flips or dice rolls, because no two players can occupy the same
position.)!  Since all placements are equally likely, there is a $4/7$
chance of this happening.

}


\ppart Suppose the 8 tennis players are equally good, i.e.,
for any two players A and B, 
\[
\prob{A \mbox{ wins}}=\prob{B \mbox{ wins}}= 1/2,
\]
and the twins Tom and Mot are amongst the 8 players.  What is the chance
that Tom and Mot ever meet in a match during the tournament?

\solution{
\textbf{Solution:}\\
The probability that Tom and Mot will meet in the first round is $1/7$
(Tom can be placed anywhere, but given Tom's position, Mot has only 1
choice in 7).

Tom and Mot will meet in the second round if and only if both win
their first-round matches (with probability $1/2 \cdot 1/2$) and both
are in different groups of two but the same group of four (probability
$2/7$).

Tom and Mot will meet in the third round if and only if both win two
matches (with probability $1/2^2 \cdot 1/2^2$) and both are in different
groups of four (probability $4/7$).

Since these events are disjoint, the probability that Tom and Mot meet in
any round is just the sum:
\[
\frac{1}{7} + \frac{1}{2} \cdot \frac{1}{2} \cdot \frac{2}{7} 
+ \frac{1}{4} \cdot \frac{1}{4} \cdot \frac{4}{7} = \frac{1}{4}
\]
}

\eparts


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

\problem Consider the following procedure for
generating a small, positive integer.  I flip a coin.  If the outcome
is heads, then I roll one die and take the result.  If the outcome is
tails, then I roll two dice and take the sum.  Assume that the coin is
fair and the dice are fair and 6-sided.

\begin{problemparts}
\problempart Define a probability space that describes this experiment.

\solution{The sample space consists of 42 outcomes.  Six of these are
pairs:

\[
(H, 1), (H, 2), \ldots, (H, 6)
\]

Each of these outcomes occurs with probability $\frac{1}{2} \cdot
\frac{1}{6} = \frac{1}{12}$.  The remaining thirty-six outcomes are
triples:

\[
(T, 1, 1), (T, 1, 2), \ldots, (T, 6, 6)
\]

Each of these outcomes occurs with probabiliy $\frac{1}{2} \cdot
\frac{1}{6} \cdot \frac{1}{6} = \frac{1}{72}$.}

\problempart What is the probability that the procedure generates a 5?

\solution{
\begin{eqnarray*}
\Pr(\text{generates 5})
	& = &	\Pr((H, 5)) + \Pr((T, 1, 4)) + \Pr((T, 2, 3)) \\
	&   &	\mbox{}	+ \Pr((T, 3, 2)) + \Pr((T, 4, 1)) \\
	& = &	\frac{1}{12} + \frac{1}{72} + \frac{1}{72}
		+ \frac{1}{72} + \frac{1}{72} \\
	& = &	\frac{5}{36}
\end{eqnarray*}
}

\problempart What is the probability that the coin was heads given
that the procedure generated a 5?

\solution{
\begin{eqnarray*}
\Pr(\text{coin was heads} \mid \text{generated 5})
	& = &	\frac{\Pr(\text{coin was heads} \cap \text{generated 5})}
			{\Pr(\text{generated 5})} \\
	& = &	\frac{\Pr((H, 5))}{\frac{5}{36}} \\
	& = &	\frac{\frac{1}{12}}{\frac{5}{36}} \\
	& = &	\frac{3}{5}
\end{eqnarray*}
}

\end{problemparts}

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

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

\end{problemparts}


\end{problems}
\end{document}









