\documentstyle[12pt,twoside]{article}

\newcommand{\problem}{%
  \paragraph{Problem}}
\newcommand(\solution}{%
  \paragraph{Solution}}

\begin{document}


\begin{problems}

%BEGIN Kavita's problems
% Fall 1998


%**************
%   PSET 9    *
%**************


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

\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)}  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)} 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}

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

\problem {\bf (15 points)} 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{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{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{
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{The first event is most likely.}

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

\problem {\bf (20 points)} 6.042 TA Alex Duran is teaching Theory Pig
a fun new game.  Theory Pig is very excited because he finally has a
friend who will ``play nice''.  Here is how the game works.  Alex
repeatedly flips a fair coin.  If the sequence $HTT$ comes up on three
consecutive throws, then the game is over and Theory Pig wins.
However, if the sequence $HHT$ comes up on three consecutive throws,
then the game is over and Alex wins.  Though the game seems completely
fair, Theory Pig is still a slightly suspicious of Alex because of an
earlier duct tape incident.

Find the probability that Theory Pig wins the game; that is, find the
probability that the sequence $HTT$ appears before the sequence $HHT$
in a sequence of fair coin tosses.

\solution{Let $p$ be the probability that $HTT$ appears before $HHT$.
For the first two flips, the sequences $HH$, $HT$, $TH$, and $TT$ are
equally likely.  Let $p_{xy}$ be the probability that the sequence
$HTT$ appears before the sequence $HHT$, given that the two most
recent flips were $x$ and $y$.  Therefore, we have:

\begin{eqnarray*}
p	& = &	\frac{1}{4}(p_{HH} + p_{HT} + p_{TH} + p_{TT})
\end{eqnarray*}

We can interrelate the four variable on the right side of this
equation by considering the outcome of the next flip.  For example,
suppose the last two flips were $HT$.  With probability $\frac{1}{2}$,
the next flip is a $T$.  Conditioned on this sequence of flips, $HTT$
appears before $HHT$ with probability 1.  On the other hand, with
probability $\frac{1}{2}$, the next flip is $H$.  In this case, $HTT$
appears before $HHT$ with probability $p_{TH}$, since the last two
flips were $TH$.  This reasoning gives the equation $p_{HT} =
\frac{1}{2} + \frac{1}{2} p_{TH}$.  By similar arguments, we obtain
the following system of linear equations.

\begin{eqnarray*}
p_{HH}	& = &	\frac{1}{2} \cdot 0 + \frac{1}{2} \cdot p_{HH} \\
p_{HT}	& = &	\frac{1}{2} \cdot 1 + \frac{1}{2} \cdot p_{TH} \\
p_{TH}	& = &	\frac{1}{2} \cdot p_{HT} + \frac{1}{2} \cdot p_{HH} \\
p_{TT}	& = &	\frac{1}{2} \cdot p_{TT} + \frac{1}{2} \cdot p_{TH}
\end{eqnarray*}

The solution to this system is $p_{HH} = 0$, $p_{TH} = \frac{2}{3}$,
$p_{TH} = \frac{1}{3}$, and $p_{TT} = \frac{2}{3}$.  Substituting
these four values into the first equation gives $p = \frac{1}{3}$ for
Theory Pig's chance of winning the game.

There are at least two alternative approaches.  First, one could find
the set of all winning outcomes for one player and sum the
probabilites of these outcomes.  Second, one could find the sets of
winning outcomes for both players and show that one has twice the
probability of the other.
}

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

\problem {\bf (10 points)} The 6.042 staff received the following
comment about the midterm exam.

\begin{verbatim}
From: grzzwk@xoros19.gammaquad.plnt
To: 6042-staff@theory.lcs.mit.edu
Subject: midterm exam

Thank you for announcing our state military secrets on your midterm
exam.

Well, you might as well know that each of our ferocious Tostitomatics
has a million components.  True, each component has a 50% chance of
failing during the arduous flight from Xoros 19 to Earth.  However,
failures occur mutually independently, and only 51% of the components
must remain functional for a Tostitomatic to survive the journey.

Clearly the number of component failures on a typical Tostitomatic
will be right around 50%--- maybe a bit more, maybe a little less.
Since the number of compoments that must remain functional is also
very close to 50%, obviously about half of our massively armed
Tostitomatics will entering earth orbit shortly.  Won't that be fun!

\Grzzwk
\end{verbatim}

Give a good estimate of the probability that a Tostitomatic survives
the journey.

\solution{A Tostitomatic survives the journey if at most 49\% of the
components fail.  This is equal to $F_{1000000, \frac{1}{2}}(0.49n)$, where
$F$ is the cumulative distribution function for the binomial
distribution.  We use the following bound and approximation:

\begin{eqnarray*}
F_{n, p}(\alpha n)
	& \leq &	\frac{1 - \alpha}{1 - \frac{\alpha}{p}}
				\cdot f_{n, p}(\alpha n)
\\
f_{n, p}(\alpha n)	& \approx &
\frac{2^{\left(
	\alpha \log_2\left(\frac{p}{\alpha}\right) +
	(1 - \alpha) \log_2 \left(\frac{1-p}{1-\alpha}\right)
	\right) \cdot n}}
	{\sqrt{2 \pi \alpha (1 - \alpha) n}}
\end{eqnarray*}

By substitution, the probability that a Tostitomatic survives the
journey is about $2.78 \cdot 10^{-89}$.}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%**************
%   PSET 10    *
%**************


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

\problem {\bf (10 points)} Several statements involving probability
are listed below.  Assume that $A$ and $B$ are events, $S$ and $T$ are
random variables, and the underlying sample space is countable.
Furthermore, assume that all expectations exist.  For each statement,
describe restrictions on $A$, $B$, $S$, and $T$ sufficient to ensure
that the statement is true.  Make your restrictions as minimal as you
can.  No proofs are necessary.

\begin{problemparts}
\problempart $\Pr(A \cup B) = \Pr(A) + \Pr(B)$

\solution{This statement is true provided that the event $A \cap B$
has probability zero.}

\problempart $\Pr(A \cup B) = \Pr(A) + \Pr(B) - \Pr(A \cap B)$

\solution{
This statement is always true.
}

\problempart $\Pr(A \cap B) = \Pr(A) \cdot \Pr(B)$

\solution{
This statement is true provided that events $A$ and $B$ are independent.
}

\problempart $\Pr(A \cap B) < \Pr(A)$

\solution{
This statement is true provided $\Pr(A \cap \overline{B}) > 0$.
}

\problempart $\Ex(S + T) = \Ex(S) + \Ex(T)$

\solution{
This statement is always true.
}

\problempart $\Ex(S \cdot T) = \Ex(S) \cdot \Ex(T)$

\solution{This statement is true provided that random variables $S$
and $T$ are independent.}

\end{problemparts}

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

%END   Kavita's problems

%BEGIN Joe's problems
%END   Joe's problems

%BEGIN Ray's problems


%%%%%%%%%%%%%%  S99 ps9



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

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

\solution{Doctor $A$ makes about 15 times more errors than Doctor
$B$.}

\end{problemparts}


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

\problem {\bf (15 points)} There are three prisoners, $A$, $B$, and
$C$.  The parole board will to release two of the prisoners, but has
not yet announced which two.  The pair to be released is selected by
the board uniformly at random; that is, each of the three pairs of
prisoners has a $\frac{1}{3}$ probability of being chosen.

Prisoner $A$ figures that he will be released with probability
$\frac{2}{3}$.  A guard offers to tell prisoner $A$ the name of one of
the other prisoners who will be released (either $B$ or $C$).
However, prisoner $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 be released, and these two
events are equally likely.

Either prove that prisoner $A$ has reasoned correctly or prove that he
is wrong.  Assume that if the guard has a choice of saying either $B$
or $C$, because both are to be released, then he picks one at random
with equal probability for each.

\solution{Prisoner $A$ is wrong.  He is conditioning on the event that
prisoner $B$ is to be released and not on the event that the guard
says prisoner $B$ is to be released.  A correct calculation is given
below.

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

Thus, the probability that prisoner $A$ will be released is not
changed by what the guard tells him.
}

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

\problem {\bf (10 points)} What is the probability that a random poker
hand contains cards from at most two suits?

\solution{The sample space consists of the $\binom{52}{5}$ possible
hands.  Each hand is equally likely and comes up with probability $1 /
\binom{52}{5}$.  Therefore, the probability that a hand contains at
most two suits is equal to the number of different hands of this type
multiplied by $1 / \binom{52}{5}$.  All that remains is to count the
number of poker hands with at most two suits.

There are $\binom{4}{2}$ ways to choose two suits and $\binom{26}{5}$
ways to choose five cards from these two suits.  However, this
triple-counts hands containing cards from a single suit.  (For
example, a hand with all 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.)  The number of hands with a single suit is $4
\cdot \binom{13}{5}$.  Therefore, 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*}
\Pr(\text{hand has at most two suits})
	& = & \frac{\binom{4}{2} \cdot \binom{26}{5} -
			2 \cdot 4 \cdot \binom{13}{5}}
		{\binom{52}{5}} \\
	& \approx & 0.15
\end{eqnarray*}
}



%%%%%%%%%%%%%%%%% S99 ps10


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


\problem{\bf (10 points)} 

Roll five ordinary unbiased dice.  On the first two, consider the
numbers modulo $3$, and on the other three, consider the numbers
modulo $2$.  Denote by $T$ the sum of these five numbers.

Compute the probability distribution function and the cumulative
distribution function for this random variable.

\solution{The possible values of $T$ are $0,1,2,3,4,5,6,7$, the the
distribution is 
\\
$\frac{1}{72}, \frac{5}{72}, \frac{12}{72},
\frac{18}{72}, \frac{18}{72}, \frac{12}{72}, \frac{5}{72},
\frac{1}{72}$ 
\\ 
and the cumulative distribution is 
\\
$\frac{1}{72},
\frac{6}{72}, \frac{18}{72}, \frac{36}{72}, \frac{54}{72},
\frac{66}{72}, \frac{71}{72}, \frac{72}{72}$
}


\problem{\bf (12 points)} 

A Dungeons and Dragons player rolls several dice and sums the results
to determine how many points of damage his warrior does to a
fire-breathing dragon.  If the warrior does $20$ or more points of
damage, then the dragon is slain.  If the warrior does fewer than $20$
points of damage, then the dragon survives and makes a nice pot-roast
out of the warrior.  What is the probability that the warrior survives
if:

\bparts
\ppart The player rolls two 12-sided dice.
\solution{${15}/{12^2} = 0.104$}
\ppart The player rolls three 8-sided dice.
\solution{$35/8^3 = 0.068$}
\ppart The player rolls four 6-sided dice.
\solution{$70/6^4=0.054$}
\eparts

\ignore{
Consider a variation of Dungeons and Dragons where you can choose
between different sets of dice before rolling them to determine the
points your character gets to attack some creature.  Say that you are
facing a certain $20$-point-resistant dragon, which means that to
survive this encounter you need to roll at least $20$ points of
``dragon damage'' with the set of dice you pick.  Treat this matter
seriously because if you roll less then $20$ points, the dragon
breathes fire on you and you die!
\bparts 
\ppart What is the probability of defeating the dragon using two
$12$-sided dice?
\ppart
How about using three $8$-sided dice?  
\ppart
How about four $6$-sided dice?
\eparts
}


\ppart Consider the following: 
\begin{itemize}
\item
If you roll the first set of dice you will get
$2*(\frac{12-1}{2}+1)=13$ points on the average.  
\item
Using the second set you will get $3*(\frac{8-1}{2}+1)=13.5$ points on
the average.  
\item
Using the third set you will get $4*(\frac{6-1}{2}+1)=14$ points.
\end{itemize}
Considering the above and your answers to parts (a)-(c), what can you
infer about the distribution of points given by these three sets of
dice?
\solution{ The mean gets slightly higher but the variance gets
smaller, and therefore there is lesser chance of hitting some fixed
upper part of the distribution.}




%END   Ray's problems

%BEGIN Ivan's problems (spring '98)
%END   Ivan's problems

%BEGIN George's problems
%END   George's problems

%BEGIN Josh's problems
%END   Josh's problems

%BEGIN Tina's problems
%END   Tina's problems


\end{problems}

\end{document}



