\documentstyle[12pt,twoside]{article}

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

\begin{document}

\begin{problems}


%nikos
%TUT10 - last used Spring 2000, Miniquiz 12
%LEARNING OUTCOMES:8 (calculate probabilities)
%                  10 (study in a small group)
%New problem added this term


\problem
Suppose a game involves tossing a fair coin until a head first arises.
\bparts
\ppart
What is the probability that a head first arises on an
even-numbered throw?

\solnospace{
The probability that a head first arises on an even-numbered throw can be
easily broken into two cases based on the first flip.  Half the time, a
head comes up on the first flip and thus the first head does not appear on
an even toss.  The other half of the time, the first head will be on an
even toss only if it is on a odd toss in the remaining sequence of tosses.
Thus:
\begin{eqnarray*}
p & = & \frac{1}{2}(1 - p) \\
p & = & \frac{1}{2} - \frac{1}{2}p \\
\frac{3}{2}p & = & \frac{1}{2} \\
p & = & \frac{1}{3} 
\end{eqnarray*}
}

\ppart What is a probability space for this experiment?

\solnospace{One reasonable probability space has as outcomes the strings
of the form $\mathtt{T}^k\mathtt{H}$, where $\mathtt{T}^k$ is a string of
$k$ \texttt{T}'s.  We define
\[
\pr{\mathtt{T}^k\mathtt{H}} \eqdef (\frac{1}{2})^{k+1}.
\]

To verify that this is a probability space, we must check that the sum of
the outcome probabilities is 1, namely,
\[
\sum_{k = 0}^{\infty} (\frac{1}{2})^{k+1} = 1.
\]
This follows straightforwardly from our formula for the sum of an infinite
geometric series.}

\ppart Does your probability space model the possibility of flipping an
infinite sequence of Tails?  If so, what is the probability of this event,
and what would happen if you removed this event?  If not, how do you
justify leaving it out?

\solnospace{ The probability space above does not have an event
corresponding to flipping Tails forever.  Nevertheless, it is a legitimate
probability space according to the formal definitions.  We could also add
an outcome or outcomes corresponding to flipping forever, but since the
probabilities of the events that end when the first Head is flipped
already total 1, the total probability of any flip-forever outcomes must
be zero.

How do we select the ``right'' probability space in this case?  In fact,
could it be that both of these spaces or wrong?  There is no mathematical
way to settle this question.  The spaces described here are mathematically
well-formed probability spaces, and ``rightness'' or ``wrongness'' is not
meant in a mathematical sense but in an empirical (experimental) sense.
Namely, can we use it to predict the results of actual coin flipping?

This is actually a subtle, and philosophically controversial, question,
since there is no experimental observation that could prove the model was
wrong.  For example, if in some experiment we flipped 1000 Tails before
flipping a Head, we still can't say that this \emph{proves} we have chosen
the wrong probability space, because the observation of 1000 tails is
\emph{possible} in our model, just very unlikely.  In practice, if we saw
1000 Tails in row, we would reject the model.  }

\iffalse

\ppart Does our probabilistic model make sense because of the
algebra, or the algebra makes sense because of our model?

\solnospace{ The algebra makes sense because of our model: Probability
is a tool to model real experiments. If two people were sitting on a
table flipping a coin forever we never know whether they would keep
bringing tails forever in reality, but we can model their game using a
probability space.  Within this probability space we assign
probabilities that make sense to us. Instead of claiming (falsely)
that TTH has probability 1/2, we are more rational and say ``Since my
coin is fair for each throw then I better assign $(1/2)^3$. Therefore
the algebra makes sense after we define a probability space.  }
\fi

\eparts


%nikos
%TUT10 - last used Spring 99 Tutorial 11, Problem 2
%LEARNING OUTCOMES:8 (calculate probabilities)
%                  10 (study in a small group)
%New problem added this term


\problem

\bparts

\ppart Suppose you repeatedly flip a fair coin until you see the sequence
\texttt{HHT} or the sequence \texttt{TTH}.  What is the probability you
will see \texttt{HHT} first?

\hint Symmetry between Heads and Tails.

\solnospace{In this case the answer is $1/2$.  The proof is by a bijection
argument on the sample space.  Let $A$ denote the event that you see
\texttt{HHT} before \texttt{TTH}, and $B$ denote the event that you see
\texttt{TTH} before \texttt{HHT}.

We will define a bijection, $g$, between $A$ and $B$ so that the
probability of $g(w)$ is equal to the probability of $w$.  The bijection
is quite simple.  Given a sample point $w \in A$, define $g(w) = \bar{w}$,
where $\bar{w}$ is the outcome where every \texttt{H} is replaced by a
\texttt{T} and vice versa.  For example $g(\mathtt{HHT}) =
\overline{\mathtt{HHT}} = \mathtt{TTH}$.

To show that $g$ is a bijection, we first observe that $g:A \rightarrow
B$.  This follows from the fact that \texttt{HHT} precedes \texttt{TTH} in
$w$ iff $\overline{\mathtt{HHT}} = \mathtt{TTH}$ precedes
$\overline{\mathtt{TTH}} = \mathtt{HHT}$ in $\bar{w}$.  And $g$ is onto by
the same reasoning.  Since $g$ is clearly an injection, we can conclude
that it is a bijection.

Then we observe that $\prob{w} = \prob{g(w)}$ for any $w$.  This is because
$\prob{\mathtt{H}} = \prob{\mathtt{T}}$ and $g(w)$ has the same length as
$w$.  Hence,
\[
\prob{A} = \sum_{w \in A} \prob{w} = \sum_{w\in A} \prob{g(w)}
= \sum_{w' \in B} \prob{w'}  =  \prob{B}.
\]
The second equality is valid because $g$ preserves the probability, and
the third by the bijection property with $w' = g(w)$.  Note that the fact
that \texttt{H} and \texttt{T} are equally likely is critical in these
calculations; this analysis would fail for a biased coin.

Finally we have to show that $\prob{A \cup B} = 1$.  This follows from the
fact that the only way never to throw either pattern is to throw all
\texttt{H}'s or all \texttt{T}'s after the first toss, and we know that
the probability of there being an unbounded number of tosses of only H or
only T is zero.  That is, $\prob{\overline{A \cup B}} = 0$ and so $\prob{A
\cup B} = 1$.  Since $A$ and $B$ are disjoint, this means that $\prob{A} +
\prob{B} = 1$ and hence
\[
\prob{A} = \frac{1}{2}.
\]
}

\ppart What is the probability you see the sequence \texttt{HTT} before
you see the sequence \texttt{HHT}?
 
\hint Try to find the probability that \texttt{HHT} comes before
\texttt{HTT} conditioning on whether you first toss an \texttt{H} or a
\texttt{T}.  The answer is not $1/2$.

\solnospace{

First, we intuitively see that HHT is more likely than HTT,
because the sequence HHTT has HHT right one toss before HTT
so the appearance of HTT depends in a way in the appearance
of HHT before it. The inverse does not hold, since throwing
HHT is independent of HTT coming before it.
\fi

Let $A$ be the event that \texttt{HTT} appears before \texttt{HHT}, and let
$p \eqdef \prob{A}$.

Suppose our first toss is \texttt{T}.  Since neither of our patterns
starts with \texttt{T}, the probability that $A$ will occur from this
point on is still $p$.  That is, $\prcond{A}{\mathtt{T}} = p$.

Suppose our first toss is \texttt{H}.  To find the probability that $A$
will now occur, that is, to find $q \eqdef \prcond{A}{\mathtt{H}}$, we
consider different cases based on the subsequent throws.

Suppose the next toss is \texttt{H}, that is, the first two tosses are
\texttt{HH}.  Then neither pattern appears if we continue flipping
\texttt{H}, and when we eventually toss a \texttt{T}, the pattern
\texttt{HHT} will then have appeared first.  So in this case, event $A$
will never occur.  That is $\prcond{A}{\mathtt{HH}} = 0$.

Suppose the first two tosses are \texttt{HT}.  If we toss a \texttt{T}
again, then we have tossed \texttt{HTT}, so event $A$ has occurred.
If we next toss an \texttt{H}, then we have tossed \texttt{HTH}.  But this
puts us in the same situation we were in after rolling an \texttt{H} on
the first toss.  That is, $\prcond{A}{\mathtt{HTH}} = q$.

Summarizing this we have:
\begin{align}
\pr{A} &=
\prcond{A}{\mathtt{T}}\pr{\mathtt{T}}+\prcond{A}{\mathtt{H}}\pr{\mathtt{H}}
& \text{(Law of Total Probability)}\\
p & = p\frac{1}{2} + q\frac{1}{2} & \text{so}\\
p & = q.\label{peq}
\end{align}

Continuing, we have
\begin{align}
\prcond{A}{\mathtt{H}} &=
\prcond{A}{\mathtt{HT}}\pr{\mathtt{T}}+\prcond{A}{\mathtt{HH}}\pr{\mathtt{H}} &
\text{(Law of Total Probability)}\\
q &= \prcond{A}{\mathtt{HT}}\frac{1}{2} + 0\cdot\frac{1}{2}\label{here}\\
\prcond{A}{\mathtt{HT}} & =
\prcond{A}{\mathtt{HTT}}\pr{\mathtt{T}}+\prcond{A}{\mathtt{HTH}}\pr{\mathtt{H}}
& \text{Law of Total Probability}\\
\prcond{A}{\mathtt{HT}} & = 1\cdot\frac{1}{2} + q\frac{1}{2} \label{there}\\
q & = (\frac{1}{2} + \frac{q}{2})\frac{1}{2} & \text{by~(\ref{here}) \&~(\ref{there})}\\
q & = \frac{1}{3}.
\end{align}

So \texttt{HTT} comes before \texttt{HHT} with probability $p=q =\cfrac{1}{3}$.

It is an amazing fact that these kind of events are another example of
\emph{intransitivity} of the kind we saw with some
\hyperref{http://theory.lcs.mit.edu/classes/6.042/fall01/lectures/l10.pdf}
{l10}{intrans-dice}{special dice in Notes 10}.  Namely, if you may pick
\emph{any} pattern of three tosses such as \texttt{HTT}, then I can pick a
pattern of three tosses such as \texttt{HHT}.  If we then bet on which
pattern will appear first in a series of tosses, the odds will be in my
favor.  In particular, even if you instead picked the ``better'' pattern
\texttt{HHT}, there is another pattern I can pick that has a more than
even chance of appearing before \texttt{HHT}.  So this intransitivity
phenomenon comes up for real---you could make money on it betting in a
bar---and not just for some contrived dice.}

\eparts

%nikos
%TUT10 - last used Spring 99 Tutorial 10, Problem 1
%LEARNING OUTCOMES:8 (calculate probabilities)
%                  10 (study in a small group)
%New problem added this term



\problem Suppose the game {\em Let's Make A Deal} is changed
slightly. Instead of having 3 doors with 1 grand prize, in the new game
there are 4 doors with 2 grand prizes. The rule of the game remains the
same. Therefore the game now becomes:

\begin{quote}
At one stage of the game, a contestant is shown 4 doors. The contestant
knows that there are 2 grand prizes behind 2 of the doors and that there
are goats behind the 2 other doors. At the beginning, the contestant picks
a door. To build suspense, the assistant of the game then opens a {\em
different} door, revealing a goat. The contestant can then stick with his
original door or switch to another unopened door. He wins a prize only if
he now picks the door with the prize.
\end{quote}

In the new game, what is the probability of winning with the ``stick''
strategy? How about the ``switch'' strategy? Can you explain why the two
probabilities do not sum up to 1?

\solnospace{The player wins with a ``stick'' strategy iff he chooses the
``correct door'' in the first place. Therefore the probability of winning
with the ``stick'' strategy is $1/2$.

Our method for analyzing the ``switch'' strategy is based on (careful,
correct use of) conditional probabilities.  Since we have seen how faulty
conditional reasoning can seem OK in this kind of problem, let's first
illustrate and justify our method to calculate the probability of winning
with the ``switch'' strategy in the \textbf{original game} with 3 doors
and 1 prize.

\begin{figure}[htbp]
\centerline{\includegraphics[height=3.5in]{figures/monty2}}
\caption{This is a tree diagram for the \textbf{original} 3-door Monty
Hall problem.  Each of the 12 leaves of the tree represents an outcome.}
\label{fig:monty}
\end{figure}

Figure~\ref{fig:monty} shows the probability tree we developed for this
game.  We examine the branch in which the prize is located behind door 1.
The winning nodes in this part of the probability tree are $(1,2,3)$ and
$(1,3,2)$ with probabilities that sum up to
\[
\frac{1}{9} +
\frac{1}{9}=\frac{2}{9}.
\]
By symmetry, the same probability applies to the other two branches, and
so the total probability of winning is $3\cdot(2/9)=2/3$.

However we can find a shortcut to calculate these probabilities.
Notice that in the second level of the tree, we can distinguish
between two cases:

(a) The player picks the door that has the prize, \eg $(1,1),(2,2),
(3,3)$.

(b) The player picks the door that does not have the prize, \eg
$(1,2),(1,3),(2,1),(2,3),(3,1),(3,2)$.

These are two disjoint events, and furthermore their union covers the
whole sample space.  Suppose we let $E_1$ be the event in (a).  The event
in (b) is then $\overline{E_1}$.  From the law of total probability
\[
\prob{E}=\prob{E|E_1}+\prob{E|\overline{E_1}},
\]
for every event $E$ in our game.

Let $E_2$ be the event that the player wins---in other words that the door
to which he switches has the prize behind it.  \iffalse Note that it
doesn't matter anymore whether the prize is in door 1,2 or 3.  That
information is not important anymore.\fi
Examining the leaves of the probability tree, we see
\begin{eqnarray*}
\pr{E_2}&=&\prcond{E_2}{E_1}\pr{E_1} + 
    \prcond{E_2}{\overline{E_1}}\pr{\overline{E_1}}\\
   &=& 0\cdot\frac{1}{3}+1\cdot\frac{2}{3} = \frac{2}{3}.
\end{eqnarray*}

So, instead of adding all the $W$ probabilities one by one,  we
group them according to whether $E_1$ occurs or not, and of course
our results match.

\iffalse
So, the fact that we condition on $E_1$ and $\overline{E_1}$ comes
after our observation that we can group all possible outcomes in the
probability tree in just these two cases. 
\fi

Returning to our original problem, for the case with 4 doors and 2
prizes we have:
\iffalse
%To calculate the probability of winning with a ``switch'' strategy, let
%$E_1$ be the event that ``the player chooses the correct door at his first
%chance''. Let $E_2$ be the event that ``the player switches to the correct
%door at his second chance''.
\fi
\begin{eqnarray*}
\pr{\text{winning with ``switch''
strategy}}&=&\prcond{E_2}{E_1}\pr{E_1}+\prcond{E_2}{\overline{E_1}}\pr{\overline{E_1}}\\
&=&\frac{1}{2}\cdot\frac{1}{2}+1\cdot\frac{1}{2} =\frac{3}{4}.
\end{eqnarray*}

This time the two probabilities do not need to sum up to 1 because they
are no longer disjoint events.  It is possible for both the ``switch'' and
the ``stick'' strategy to pick doors that both have a prize behind them,
because there are two prizes.  So the same outcome can be a win for both
strategies.}

%twang
%PSET10 - last used Fall01
%LEARNING OUTCOMES:1 (basic math concepts - prob.)
%                  8 (Calculate prob.)
%New problem added this term

\problem

A gambler has been studying the roulette wheel in a Las Vegas casino over
a long period of time, and his data confirms that the wheel is biased to
come up on a red number about 51\% of the time.  Since a bet on red pays
even money (bet \$1 and either lose it, or win and get back \$2), he
realizes the odds are in his favor.

So with high hopes and an initial stake of \$10,000, the gambler aims to
turn his stake into \$1,000,000.  He plans simply to continue making \$100
bets on red until either he is ahead the \$1,000,000, or he goes bankrupt.
He considers bankruptcy very unlikely because the odds are in his favor,
and the bets are small enough relative to his initial stake that he can
withstand a long run of losses.

\bparts

\ppart
Based on this description, describe a reasonable probability space to
model this situation.

\solnospace{
An easy way to describe an appropriate sample space is to keep track of
the gambler's stake.  So sample points will be all the finite sequences of
nonnegative multiples of 100, that
\begin{itemize}
\item start at 10,000,
\item end at the first occurrence of either 0 or 1,000,000,
\item have successive integers in the sequence differ by exactly 100.
\end{itemize}
For example, the sample point describing two initial wins, followed by 102
losses and bankruptcy would be the length 105 sequence
\[
(10000, 10100,10200, 10100,10000,9900,9800,\dots,200,100,0).
\]
The sample point corresponding to his winning every bet until he reaches
his goal would the length 9,900 sequence
\[
(10000, 10100,10200, 10300,10400,\dots, 999800, 999900, 1000000).
\]
The probability of an outcome is defined to be $(0.51)^k(0.49)^j$ where
$k$ is the number of increases by 100, and $j$ is the number of decreases
by 100.  Note that either $j-k = 100$ for sample points that lead to
bankruptcy or $k-j = 9,900$ for those leading to \$1,000,000.}

\ppart Describe an positive constant, $\epsilon$, such that, at any point
during his play when the gambler has not gone bankrupt, there is a
probability of at least $\epsilon$ that he will reach his goal of
\$1,000,000 within the next 9,999 bets.

\solnospace{ $\epsilon \eqdef (0.51)^{9999}$ will do, since even if the
gambler's stake was down to \$100, there is still this much probability
that he will win the next 9,999 bets in a row and reach his goal of
\$1,000,000.}

\ppart Conclude that the probability that he bets forever---without either
going bankrupt or reaching his \$1,000,000 goal---is zero.

\solnospace{By part~(b) the probability that the gambler does \emph{not}
reach his \$1,000,000 goal during his first 9,999 bets is at most
$1-\epsilon$.  The conditional probability that he reaches \$1,000,000
during his second sequence of 9,999 bets, given that he hasn't already
reached his goal or gone bankrupt, is at most $(1-\epsilon)^2$.  The
conditional probability that he reaches \$1,000,000 during his $n$th
sequence of 9,999 bets, given that he hasn't already reached his goal or
gone bankrupt, is at most $(1-\epsilon)^n$.

This implies that the probability that he bets more than $9999n$ times is
at most $(1-\epsilon)^n$, and so the probability that he bets forever is
at most $(1-\epsilon)^n$ for every $n$.  Since $(1-\epsilon)^n$ approaches
0 as $n \rightarrow \infty$.  The probability that the gambler bets
forever is at most 0.}

\eparts



%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.}

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

% pset8 spring01

\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{\textbf{Solution:}
  
  First note that the optimal strategy for~$B$ is to shoot the most
  accurate gunfighter. So, if $B$~gets to shoot and both $A$ and~$C$
  are still alive, $B$~will shoot~$C$---this gives him a $1-0.3 = 0.7$
  chance of survival---and not~$A$---that would only give him a $1-0.5
  = 0.5$ chance of survival.
  
  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 $A$~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{displaymath}
    p = \frac{1}{2} \cdot \frac{3}{10} + \frac{1}{2} \cdot \frac{7}{10} p,
  \end{displaymath}
  which has the solution $p = 3 /13$.
  
  Thus, If $A$ hits~$B$, his odds of survival are lower than if he
  fires into the air! If he does not hit, his probability of survival
  is the same as if he had started by firing in the air. Since
  $A$~hits with probability~$0.3$, the probability that $A$~survives
  when he begins with shooting at~$B$ is $0.3 \cdot 3 / 13 + 0.7 \cdot
  0.3 = 363 / 1300 < 0.28$.
  
  On the other hand, suppose that $A$ shoots at~$C$. If he hits, then
  $B$~immediately kills him. If he does not hit, his probability of
  survival is, again, the same as if he had started by firing in the
  air. Thus, his probability of survival in this case is $0.3 \cdot 0
  + 0.7 \cdot 0.3 = 0.21$.
  
  To conclude, $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
\problem %source: spring00 ps8
% Fall 97
\problem
\begin{problemparts}
\problempart You roll two dice.  What is the probability that their
sum is not 6?

\problempart You roll three dice. What is the probability that
at least one of the {\em pairwise} sums is something other than 6?
\end{problemparts}

\omitsolution{
\begin{enumerate}
\item 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 $\frac{5}{36}$. Therefore the probability
that the sum is not six is $\frac{31}{36}$.


\item First, we calculate the probability of the complement event,
that all pairwise sums equal 6.  This can only occur when all three
dice show ``3''.  This event occurs with probability $\frac{1}{216}$.
Therefore the probability that at least one of the pairwise sums is
not 6, is $\frac{215}{216}$.

\end{enumerate}
}


%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)

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset8 spring01
\problem [10 pts]

Suppose the game \emph{Let's Make A Deal} is changed slightly. Instead
of having 3 doors with 1 grand prize, in the new game there are 4
doors with 2 grand prizes. The rule of the game remains the
same. Therefore the game now becomes:
\begin{quote}
  At one stage of the game, a contestant is shown 4 doors. The
  contestant knows that there are 2 grand prizes behind 2 of the
  doors and that there are goats behind the 2 other doors. At the
  beginning, the contestant picks a door. To build suspense, the
  assistant of the game then opens a \emph{different} door, revealing
  a goat. The contestant can then stick with his original door or
  switch to another unopened door. He wins a prize only if he now
  picks the door with the prize.
\end{quote}
In the new game, what is the probability of winning with the ``stick''
strategy?  How about the ``switch'' strategy? Can you explain why the
two probabilities do not sum up to 1?

\solution{
{\bf Solution}

The player wins with a ``stick'' strategy iff he chooses the ``correct
door'' in the first place. Therefore the probability of winning with
the ``stick'' strategy is $\frac{1}{2}$.

To calculate the probability of winning with a ``switch'' strategy,
we use a tree diagram.  The prize location can initially be any one of the pairs ${(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)}$ each with probability $\frac{1}{6}$.  Because of the symmetry in the tree, we consider the following sub-tree for the pair $(1,4)$.

\bigskip
\centerline{\resizebox{!}{7.0in}{\includegraphics{figures/ps8-monty}}}
\bigskip

Therefore we get that:

\begin{eqnarray*}
  P(\mbox{winning with ``switch'' strategy})
  &=& \mbox{\# of prize combinations} \cdot P(\mbox{winning with ``switch'' strategy for (1,4)})\\
  &=& 6 \cdot (4 \cdot \frac{1}{48} + 4 \cdot \frac{1}{96})\\
  &=&\frac{3}{4}
\end{eqnarray*}

The two probabilities do not need to sum up to 1. This is because the
two strategies are not mutually exclusive, that is there are some
strategies for which the player would win whether or not he ``sticks''
or ``switches''.  For example, if the prizes are behind doors 1 and 4, and the player chooses 1 first then switches to 4, then he would have won
by either strategy.  Therefore, the same winning event can be counted
in both cases at the same time.  }


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset9 problem2 spring98
\problem [20 pts]

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 problem3 spring98
\problem [10 pts]

In a lottery, 6 distinct integers are drawn randomly from 1 to 45 without replacement. What is the 
probability that the maximum of the 6 numbers is $k$, where $1\leq k\leq45$?

\solution{
{\bf Solution}

{\bf Method 1: Counting}

There are ${45\choose6}$ ways to pick 6 numbers out of 45. For a set of 6
numbers whose maximum element is $k$, it has to have $k$ and all of 5 other
numbers are smaller than $k$. Therefore there are ${k-1\choose5}$ such sets.
Since every set of 6 numbers are equally likely to occur, the desired
probability is simply $\frac{{k-1\choose5}}{{45\choose6}}$.

{\bf Method 2: Conditional Probability}

Let $M$ be the maximum of the 6 drawn numbers. We want to find $P(M=k)$.
Let $A_k$ be the event that ``$k$ is selected''.
Let $B_k$ be the event that ``all selected numbers $\leq k$''. 

For $1\leq k\leq5, P(M=k)=0$ because the maximum number has to be $\geq 6$.

For $6\leq k\leq45$, 
\begin{eqnarray*}
P(M=k)&=&P(A_k\cap B_k)\\
      &=&P(B_k|A_k)P(A_k)\\
      &=&\frac{{k-1\choose5}}{{44\choose5}}\cdot\frac{6}{45}\\
      &=&\frac{\frac{(k-1)!}{5!(k-6)!}}{\frac{44!}{5!39!}}\cdot\frac{6}{45}\\
      &=&\frac{(k-1)!\cdot39!\cdot6}{(k-6)!45!}\\
\end{eqnarray*}

$P(B_k|A_k)$ is the probability that the other 5 numbers are smaller than $k$
given that $k$ is selected. There are ${k-1\choose5}$ ways to choose 5 numbers
from $\{1,2,\ldots,k-1\}$. Since each combination of 6 numbers is equally
likely to appear, the probability is $\frac{{k-1 \choose 5}}{{44\choose 5}}$.

To find $P(A_k)$, notice that the the probability for $k$ to be selected as the
first number is $\frac{1}{45}$. Since $k$ can also appear as the $2^{nd},
3^{rd},\ldots,6^{th}$ number, the probability that $k$ is selected as one of
the six numbers is $\frac{6}{45}$.

To check the answer, try $k=45$. The probability that 45 is the maximum of the
6 numbers is equal to the probability that $45$ is drawn, which is equal to
$\frac{6}{45}$ as explained. From the formula, we have
$P(M=45)=\frac{44!\times39!\times6}{39!45!}=\frac{6}{45}$ as expected.
}

%END   Ivan's problems

%BEGIN George's problems
%%%%%%%%%%%%%%  Fall 2000 PS9    %%%%%%%%%%%%%%   %%%%%%%%%%%%%%%
\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}
                               
%%%%%%%%%%%%%%  Fall 2000 PS9    %%%%%%%%%%%%%%   %%%%%%%%%%%%%%%
 \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}    
%%%%%%%%%%%%%%  Fall 2000 PS9    %%%%%%%%%%%%%%   %%%%%%%%%%%%%%%
\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}    
%%%%%%%%%%%%%%  Fall 2000  PS 9   %%%%%%%%%%%%%%   %%%%%%%%%%%%%%%

\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


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

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

%BEGIN Tina's problems
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% FALL 1999 %%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%% Problem Set 9 %%%%%%%%%%%5

\problem \textbf{r-Permutations.}
% Based on Example given in Introductory Combinatorics (Brualdi), pg. 62

How many 7-letter words can be constructed using the 26 letters of the
English alphabet if each word contains exactly 2,3, or 5 vowels?  There is
no restriction on the number of times a letter can be used in a word.

\solution{Let us count the number of words according to the number of
vowels they contain and then sum them up using the sum rule.
There are 5 vowels and 22 cononants.

\textit{2 vowels}: The 2 positions occupied by the vowels can be chosen in
$\binom{7}{2}$ ways; the other 5 positions are occupied by consonants.
The vowel positions can then be completed in $5^2$ ways and the consonant
positions in $21^5$ ways.  Thus the number of words with 2 vowels is
\[\binom{7}{2}5^2 21^5 = \frac{7!}{2!5!}5^2 21^5 \]

\textit{3 vowels}: \[\binom{7}{3}5^3 21^4 = \frac{7!}{3!4!}5^3 21^4 \]

\textit{5 vowels}: \[\binom{7}{5}5^5 21^2 = \frac{7!}{5!2!}5^5 21^2 \]

Hence the total number of words is \[\frac{7!}{2!5!}5^2 21^5 + \frac{7!}{3!4!}5^3 21^4 + \frac{7!}{5!2!}5^5 21^2 \]}


\problem \textbf{r-Combinations with repetitions.}
% 

\bparts 

\ppart The coffee shop in building 4 has 15 kinds of donuts
available. The number available is not infinite, but we assume it's
large enough that I can buy any 10 I wish. How many different
combinations of 10 donuts can I buy?

\solution{Each combination of 10 donuts is a 10-combination from a
       multiset having 15 kinds of objects. The number of such
       combinations is $\binom{10+15-1}{10} = \binom{24}{10}$.}

\ppart Now suppose I'm going to buy 20 donuts, and I want to make sure
to buy at least one of each of the 15 kinds.  How many collections of
20 are possible?

\solution{First choose one of each kind: that's 15 doughnuts. Now I
       choose a 5-combination to complete the set. I can do that in
       $\binom{5+15-1}{5} = \binom{19}{5}$ ways.  No wonder it takes
       so long to get out of the coffee shop...}

\ppart More donuts... What if I'm going to buy 20 donuts, and I want
to be sure to get 5 glazed and 6 old-fashioned donuts. The rest can be
anything. How many possible ways are there for me to do so?

\solution{Choose the 5+6 we really want first, and then choose a
       9-combination for the rest. We can do this in $\binom{9+15-1}{9}
       = \binom{23}{9}$ ways.}

\eparts

\problem \textbf{Binomial Coefficients.  The Binomial Theorem.}

\bparts

\ppart Define a \textit{composition} of $x$ as an
\textit{ordered} sum of positive integers that equal $x$.  I.e., the
compositions of $4$ are

\begin{center}
\begin{tabular}{ll}
$1+1+1+1$ & $3+1$ \\
$2+1+1$ & $1+3$ \\
$1+2+1$ & $2+2$ \\
$1+1+2$ & $4$ \\
\end{tabular}
\end{center}

For any $n$, count the number of compositions of $n$.

\solution{We can use a dot/bar diagram to conceptualize this.  Note
that a composition of $x$ can be viewed as a way to place bars between
$x$ dots; for example, for $x=4$:

\begin{center}
\begin{tabular}{lc}
$1+1+1+1$ & $\cdot|\cdot|\cdot|\cdot$ \\
$2+1+1$ & $\cdot\ \cdot|\cdot|\cdot$ \\
$1+3$ & $\cdot|\cdot\ \cdot\ \ \cdot$ \\
\end{tabular}
\end{center}

Thus, there are $2^{n-1}$ such compositions.}

\ppart Define a $k$-\textit{composition} of $x$ as a composition of
$x$ with exactly $k$ elements.  Count the number of $k$-compositions
of $n$.  Use part (a) and your answer
to derive \[ \sum_{i=0}^{m} \binom{m}{i} = 2^m \]

\solution{Using the dot/bar diagram from the previous part, it is
clear that you are choosing $k-1$ positions to place bars out of $n-1$
possible positions.  This is $\binom{n-1}{k-1}$.

Since the set of $k$-compositions is disjoint from the set of $j$
compositions for $k\not=j$, we can simply add them up: 
\[ \sum_{k=1}^{n} \binom{n-1}{k-1} = 2^{n-1} \]  

Cleaning this up by setting $m:=n-1$ and $i:=k-1$, we have 
\[ \sum_{i=0}^{m} {\binom{m}{i}} = 2^m \]

}

\ppart Give a combinatorial proof\footnote{Recall examples of
combinatorial proofs from lecture} for 
$$\sum_{k=0}^{\lfloor \frac{n}{2} \rfloor} {\binom{n}{2k}} = 2^{n-1} $$

\solution{The above sum corresponds to how many ways
are there to choose an even number of
elements from $n$ elements.

Think of the selection process as follows:
for each element $x_1$, $x_2, \ldots, x_{n-1}$ we have two 
choices of whether we select it or not, and 
when we get to $x_n$, we have only 1 choice.  Namely,
if thus far we have chosen an
even number of the elements $x_1$, $x_2, \ldots, x_{n-1}$, we must
leave $x_n$ out; if we have chosen an odd number of the elements $x_1$,
$x_2, \ldots, x_{n-1}$, we must put $x_n$ in.  Hence the number of
combinations of S with an even number of elements equals $2^{n-1}$. }

\ppart Use the previous part to conclude that 
\[\sum_{k=0}^{n} {(-1)^k \binom{n}{k}} = 0 \]

\solution
{
Notice that 
\[\sum_{k=0}^{\lfloor{ \frac{n-1}{2} \rfloor}} \binom{n}{2k+1} \]
is the number of ways to choose an odd number of elements from
$n$. Thus, by the same reasoning above, it is also equal to $2^{n-1}$.
Subtracting the number of ways to choose an even number of
elements from the number of ways to choose an odd number of elements
we get 0.

Written differently, 
\[\sum_{k=0}^{\lfloor n/2\rfloor} \binom{n}{2k}   - 
\sum_{k=0}^{\lfloor{ \frac{n-1}{2} \rfloor}} \binom{n}{2k+1} = \]
\[\sum_{k=0}^{n} (-1)^k \binom{n}{k} = 0 \]  
}

\eparts

\problem
You are at point $(0,0,0)$ in three-dimensional space, and you need to get to 
point $(i,j,k)$. You can only make unit-length moves parallel
to three coordinate axes, and only moves that get you closer to
your goal. How many different paths can you take?

\solution{
No matter how you arrive at $(i,j,k)$, you must have taken $i+j+k$
steps.  Of these steps, $i$ must be along one dimension, $j$ must be
along another, and $k$ must be along the third.  The question becomes
how to distribute the three types of steps amongst the $i+j+k$ total
steps.  There are $\binom{i+j+k}{i}$ ways to choose which of the
$i+j+k$ steps will be along the first dimension, $\binom{j+k}{j}$
ways to choose which of the $j+k$ remaining steps will be along the
second dimension, and ${\binom{k}{k}} = 1$ way to choose which of the
$k$ remaining steps will be along the third dimension.  By the product
rule, the total number of different paths is ${\binom{i+j+k}{i}}
{\binom{j+k}{j}}$.

Alternatively, you could argue as follows:
No matter how you arrive at $(i,j,k)$, you must have taken $i+j+k$ steps.  Of
these steps, $i$ must be along one dimension, $j$ must be along
another, and $k$
must be along a third.  The question becomes how to arrange these steps in
order.  This can be done in $\binom{i+j+k}{i, j, k}$ ways.  (Consult the 
multinomial definition for the factorial form of this.)
}

%%%%%PROBLEM SET 10 %%%%%%%%%%

\problem(Rosen p. 305, problem 40)

Suppose that $A$ and $B$ are events in a probability space
with $\prob{B}\neq 0$.
Prove the following identity, 
\iffalse
Using the fact that $A = (A \cap B) \cup (A \cap \overline{B})$, prove
that the probability of A is the weighted average of the
probaility of A given B and the probability of A given the complement
of $B, \overline{B}$ where the weights are the
probabilities of B and $\overline{B}$ , respectively.
Namely,
\fi
\[
\prob{A} = \prob{A \mid B} \cdot \prob{B} + \prob{A \mid  \overline{B}} \cdot
\prob{\overline{B}}.
\]
\hint $(A\cap B)$ and $(A\cap \overline{B})$ are disjoint.


\solution{
\begin{eqnarray*}
\lefteqn{\prob{A \mid  B} \cdot \prob{B} + \prob{A \mid  \overline{B}} \cdot \prob{\overline{B}}}\\
& = & \frac{\prob{A \cap B}}{\prob{B}} \prob{B} + \frac{\prob{A \cap \overline{B}}}{\prob{\overline{B}}} \prob{\overline{B}} \\
& = & \prob{A \cap B} + \prob{A \cap \overline{B}} \\
& = & \prob{(A \cap B) \cup (A \cap \overline{B})}  \qquad \mbox{(since $A \cap B$ and $A \cap \overline{B}$ are disjoint}) \\
& = & \prob{A}
\end{eqnarray*}

}
       

\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~\ref{tennis}).

\begin{figure}[ht]\label{tennis}
\centerline{\resizebox{!}{3in}{\includegraphics{H64-tennis.eps}}}
\caption{A Tennis Tournament Ladder}
\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{
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{
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 {\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{H64-flaw.eps}}}
\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!
}

\problem {\bf Craps.} The game of craps is played with a pair of dice.
The player rolls both dice, winning immediately if the total is 7 or 11,
and losing immediately if the total is 2, 3, or 12.  Any other total is
called the ``point.''  If the first roll is a point, then the player
continues rolling repeatedly until rolling the point again (which wins),
or rolling 7 (which loses).
\bparts

\ppart What is the chance of winning on the first roll?

\solution{

As the sample space of elementary events for the first roll we can take
$D^2 = \{(1,1), (1,2),\ldots,(6,6)\}$.  The following table summarizes in
the second column what is the probability of having rolled the total value
in the first column.

\begin{center}
\begin{tabular}{r|r}
Roll & Prob \\
\hline
2 & $1/36$ \\
3 & $2/36$ \\
4 & $3/36$ \\
5 & $4/36$ \\
6 & $5/36$ \\
7 & $6/36$ \\
8 & $5/36$ \\
9 & $4/36$ \\
10 & $3/36$ \\
11 & $2/36$ \\
12 & $1/36$ \\
\end{tabular}
\end{center}

So the probability of rolling a 7 or 11 on the first roll is just
$6/36 + 2/36 = 2/9$.

}

\ppart What is the probability of losing immmediately on the first roll?

\solution{$1/36 + 2/36 +1/36 = 1/9$.}

\ppart What is the overall chance of winning?  Explain in your answer how
you model the sample space.  (For this part, it may be useful to refer to
Handout 63 ``Probabilities in a Dice Game.'')

\solution{

The first way to win is by rolling 7 or 11 on the first roll, which we
now know has probability $2/9$.  Otherwise, we must win by rolling a
point: getting 4, 5, 6, 8, 9, or 10 on the first roll, then eventually
rolling the same number again without rolling 7 first.  Since the odds
of rolling each point value is different, let $w_r$ be the probability
of winning with point $r$, for $r \in \{4, 5, 6, 8, 9, 10\}$.

One way to compute $w_r$ is by summing over all possible roll
sequences:
\[
w_r = \prob{\mbox{first roll is $r$}} 
\sum_{i=0}^{\infty} \prob{\mbox{the next $i$ rolls are neither $r$ nor 7}}
                    \prob{\mbox{the final roll is $r$}}.
\]

Let $p_r$ be the probability of rolling $r$ on a single roll (e.g.,
$p_4 = 3/36$). Then the formula for $w_r$ reduces to:
\begin{eqnarray*}
w_r & = & p_r \sum_{i=0}^{\infty} (1-p_r-p_7)^i p_r \\
    & = & p_r p_r \sum_{i=0}^{\infty} (1-p_r-p_7)^i \\
    & = & p_r \frac{p_r}{1-(1-p_r-p_7)}\\
    & = & p_r \frac {p_r}{p_r+p_7}.
\end{eqnarray*}

So the probability of winning with point 4 (for example) is 
\begin{eqnarray*}
w_4 & = & {3/36}\cdot{\frac{3/36}{3/36 +  6/36}} \\
    & = & {3/36}\cdot{3/9} \\
    & = & {1/36}.
\end{eqnarray*}
By similar calculations we get
\begin{eqnarray*}
w_5 & = & {4/36}\cdot \frac{4/36}{4/36 + 6/36} = {2/45}, \\
w_6 & = & {5/36}\cdot \frac{5/36} {5/36 + 6/36} = {25/396}.
\end{eqnarray*}

Note that the chance of rolling 8 is the same as rolling 6, so $w_8=w_6$,
$w_9=w_5$, and $w_{10} = w_4$, so we can simply double the probability
$w_4+w_5+w_6$ to find the total probability of winning with a point.  So
the overall chance of winning is $2/9 + 2\cdot (1/36 + 2/45 + 25/396 )
\approx 0.493$.  In other words, the odds of winning are slightly worse
than 50-50.  A similar series calculation shows that the chance of losing
with point $r$ is
\[
p_r \frac {p_7}{p_r+p_7} = p_r(1-w_r).
\]

The underlying sample space for the above solution is the set of all
sequences of possible rolls.  For example, if a player rolls a total of 8
on the first roll, 9 on the second, 3 on the third, and 7 on the 4th, then
the game ends with player losing because he rolled a 7, and the
corresponding sequence in the sample space is $8 \cdot 9 \cdot 3 \cdot 7$,
(where $\cdot$ denotes concatentation of numerals, not multiplication of
numbers).  The probability of a sequence $r_1 \cdot r_2 \cdots r_n$ in the
sample space is defined to be $\prod_{i=1}^n p_{r_i}$.  This definition
meets the formal requirements for a probability space because the sum of
the probabilities of all the points is exactly one.  This fact can be
verified by combining the series used above to determine the probabilities
of win or loss with a given point; we omit the details.

Note that it is also logically possible for the game to run forever when a
point is rolled first and neither the point nor a seven comes up in later
rolls.  However, since the other sample points have total probability one,
the ``run forever'' possibility could only be assigned probability zero,
and it could be omitted from a model sample space without affecting
anything.  Perhaps it makes the model more realistic to acknowledge the
``run forever'' possibility by adding a single sample point for this
outcome to which we assign probability zero.

METHOD 2: 

Here's a way of computing $w_r$ that neatly avoids an infinite sample
space and infinite sums.  When you're trying to roll your point, none of
the rolls matter except the last one, when you either roll your point and
win, or roll 7 and lose.  So we can {\it ignore} the intermediate rolls,
and just consider the probability of rolling your point given that you
rolled either your point or 7.  This way there are just seventeen points
in the sample space, namely, five sequences of length one: $7,11,2,3,12$,
and twelve sequences of length two: six winning ones of the form $r \cdot
r$ and six losing ones of the form $r \cdot 7$ for $r = 4,5,6,8,9,10$.
The probability of a length one sample point $r= 7,11,2,3,12$ will be
defined to be $p_r$ as above.  Now the reasoning that leads us to this
sample space implies that we should define the probability for a sample
point of the form $r \cdot r$ to be
\[
p_r \frac{p_r}{p_r+p_7}.
\]
This, of course, is exactly the $w_r$ calculated using the infinite sample
space.  Likewise, the probability of the sample points of the form $r
\cdot 7$ will be
\[
p_r \frac{p_7}{p_r+p_7}.
\]

}


\eparts

\problem

\bparts

\ppart Suppose that you are looking in your desk for a letter from some
time ago.  Your desk has eight drawers, and you assess the probability that
it is in any particular drawer as 10\% (so there is a 20\% chance that it
is not in the desk at all). Suppose now that you start searching
systematically through your desk, one drawer at a time.  In addition,
suppose that you have not found the letter in the first $i$ drawers, where
$0 \leq i \leq 7$.  Let $p_i$ denote the probability that the letter will
be found in the next drawer, and let $q_i$ denote the probability that the
letter will be found in some subsequent drawer (both $p_i$ and $q_i$ are
conditional probabilities, since they are based on the assumption that the
letter is not in the first $i$ drawers).  Show that the $p_i$'s increase
and the $q_i$'s decrease.

\hint Observe that if event $A$ implies event $B$ then $\prob{A \mid B} =
\prob{A}/ \prob{B}$.

\solution{

First, we verify the hint.  Saying that $A$ implies $B$ is the same as
saying that that $A \cap B = A$, so
\[
\prob{A \mid B} = \frac{\prob{A \cap B}}{\prob{B}} = \frac{\prob{A}}{\prob{B}}.
\]

Now, we define the following events:
\begin{eqnarray*}
E_i & \eqdef & \text{letter is in drawer } i,\\
N_i & \eqdef & \text{letter is not in drawers } 1, 2, \ldots i,\\
R_i & \eqdef & \text{letter is in one of drawers } i+1, i+2, \ldots 8.
\end{eqnarray*}
Now we wish to find
\begin{eqnarray*}
p_i & = & \prob{E_{i+1} \mid N_i}\\
&  = & \frac{\prob{E_{i+1} \cap N_i}}{\prob{N_i}}\\
&  = & \frac{\prob{E_{i+1}}}{\prob{N_i}} \qquad
   \text{(from the hint, since $E_{i+1} \Rightarrow N_i$)}\\
& = & \frac{0.1}{0.2 + 0.1(8-i)} = \frac{1}{10-i},
\end{eqnarray*}
which clearly increases as $i$ increases, since the denominator gets
smaller while the numerator remains constant.

Now,
\begin{eqnarray*}
q_i & = & \prob{R_i \mid N_i}\\
& = & \frac{\prob{R_i \cap N_i}}{\prob{N_i}}\\
& = & \frac{\prob{R_i}}{\prob{N_i}} \qquad\text{(from the hint, since $R_i \Rightarrow N_i$)}\\
& = & \frac{0.1(8-i)}{0.2 + 0.1(8-i)}\\
& = & \frac{8-i}{10-i} = \frac{10-i}{10-i} - \frac{2}{10-i} = 1 - \frac{2}{10-i}
\end{eqnarray*}
which decreases as $i$ increases, since the denominator of the fraction
shrinks, so the fraction becomes greater, so the negation of the fraction
becomes lesser.

}

\ppart
The following data appeared in an article in the Wall Street Journal.
For the ages 20, 30, 40, 50, and 60, the probability of a woman in the
U.S. developing cancer in the next ten years is 0.5\%, 1.2\%, 3.2\%,
6.4\%, and 10.8\%, respectively. At the same set of ages, the
probability of a woman in the U.S. eventually developing cancer is
39.6\%, 39.5\%, 39.1\%, 37.5\%, and 34.2\%, respectively.  This seems
strange, but use the previous part of the problem to give an
explanation for these data.

\eparts


\problem
{\bf Extra credit}
You are given two urns and 50 balls. Half of the balls are white and
half are black. You are asked to distribute the balls in the urns with
no restriction placed on the number of either type in an urn. How
should you distribute the balls in the urns to maximize the
probability of obtaining a white ball if an urn is chosen at random
and a ball drawn out at random? Justify your answer.

\solution{\\ Let $w_1$ be the number of white balls in urn 1, and
$b_1$ be the number of black balls in urn one. Consider the strategy
of $w_1 = b_1$. This gives probability of 1/2 of selecting a white
ball once either urn is selected, and thus 1/2 overall probability of
selecting a white ball. Now consider $w_1 = 1$ and $b_1 = 0$. This
gives probability 1 of selecting a white ball from urn 1, and $24/25$
of selecting a white ball from urn 2. Thus, the overall probability of
selecting a white ball is $1/2 \cdot 1 + 1/2 \cdot 24/50 = 0.74$,
which is greater than 1/2. So clearly, the optimal strategy must have
$w_1 \neq b_1$. That is, one urn must have more white balls than
black, and the other must have more black than white. In the urn with
more white balls, the best we can do is to have probability 1 of
choosing a white ball. In the other urn, which must have fewer white
balls than black, the best we can do is to have only 1 fewer. So, the
$w_1 = 1, b_1 = 0$ strategy is best for both urns, and therefore best
overall. }


%END   Tina's problems


\end{problems}

\end{document}



