\documentclass[12pt]{article}
\input{macros-course}

\askaboutsolutions

\begin{document}

\ifshowsolutions
  \psetsol{10}{November 14, 2001}{\stamp}
\else
  \pset{10}{November 5, 2001}{Wednesday November 14, beginning of lecture}{\stamp}
  \collaborationnote
\fi

\reading
\href{http://theory.lcs.mit.edu/classes/6.042/fall01/lectures/l10.pdf}
{Week 10 Notes}.  Rosen \S 4.4, \S 4.5 up to Random Variables, p.274.

\begin{problems}

%Spring 98
%monty hall variation

%\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.
%
%\solnospace{
%For the ``stick'' strategy, the probability of winning the pig is clearly
%$\cfrac{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 in
%Figure~\ref{pigfind}
%illustrates the various cases.
%
%\begin{figure}[htbp]
%%\centerline{\psfig{figure=/a/class/6.042/fall00/handouts/fig/Sol9-pigfind.eps,height=3in}}
%\centerline{\includegraphics[height=3in]{figures/Sol9-pigfind}}
%\label{pigfind}
%\end{figure}
%
%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 $\cfrac{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.
%}
%
%\ppart
%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?
%
%\solnospace{
%Stu guesses the right door initially with probability
%$\cfrac{1}{4}$ and guesses the wrong door with probability
%$\cfrac{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?
%
%\solnospace{
%Zelda also guesses the right door initially with probability
%$\cfrac{1}{4}$ and guesses the wrong door with probability
%$\cfrac{3}{4}$.  If she was right initially, then she can not win.  If
%she was wrong initially, then she wins with probability $\cfrac{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 94
% Another Monty Hall
%\problem
%Suppose you are playing the {\it Lets Make a Deal} game with
%4 doors rather than~3.
%Say Monty and you choose doors according to the uniform distribution.
%After your initial choice, Monty reveals a loser and offers you the
%chance to switch.  Subsequently, he reveals another loser and again offers
%you the chance to switch.   Compute the probability of winning for
%each of the four possible strategies:  (1) stick both times, (2)
%switch both times, (3) stick the first time, switch the second time,
%and (4) switch the first time, stick the second time.
%Which strategy is the best?%
%
%\solnospace{
%
%\textbf{Stick both times:}
%
%You will win only if you pick the correct box initially.
%This happens with probability 1/4.
%
%\textbf{Switch both times:}
%
%You will win only if you have selected a bad box before the last
%switch.  This can occur two different ways.
%\begin{enumerate}
%\item You first pick the good box and then switch to a bad box.
%The probability of picking the good box is 1/4.
%After your first switch, you will always pick a bad box.
%\item You first pick a bad box (with probability 3/4) and then
%switch to another bad box.  At this point, you have the choice
%of switching to either the good box or another bad box.  The probability
%of picking the bad box is 1/2.  Thus, the probability of this entire
%event is 3/8.
%\end{enumerate}

%Therefore, the probability of winning with this strategy
%is $1/4+3/8=5/8$.
%
%\textbf{Stick the first time, switch the second time:}
%
%Again, you will win if you have selected a bad box before the switch.
%Since you sticked the first time, this occurs with probability 3/4.
%
%\textbf{Switch the first time, stick the second time:}%
%
%You will win if you switch onto the good box.  In order to do this,
%you must first pick a bad box (with probability 3/4) and then switch
%onto the good box (with probability 1/2).  Thus, your probability of winning
%is 3/8.
%
%By comparing probabilities, it is best to ``Stick the first time, and
%switch the second''.  This strategy gives you a 3/4 chance of winning.
%}

% FALL 98
% Basic probability
\problem 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.

\solnospace{The probability of rolling a 6 on a particular die is
$1/6$.  The probability of not rolling a 6 on a particular die is
$5/6$, since this is the complementary event.  The probability of
not rolling a 6 on any of six dice is $(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.

\solnospace{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 $(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 $\cfrac{1}{6}$, and the probability of the
remaining dice all coming up in the range 1 to 5 is $(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.

\solnospace{
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}

\solnospace{The first event is most likely.}

% FALL 2000
\problem
In London, half of the days have some rain. The weather forecaster is
correct 2/3 of the time -- i.e. the probability that it rains, given
that she has predicted that it will rain, and the probability that it
does not rain given that she has predicted that it does not rain, are
both equal to 2/3. When rain is forecast, Mr.Paddington takes his
umbrella. When rain is not forecast, he takes it with probability
1/3.
\bparts

\ppart Find the probability of the weather forecaster forecasting rain.
\solution{

\textbf{Solution:}
To compute this probability, first we define the following events:

\begin{eqnarray*}
F & \eqdef & \text{the weather forecaster forecasts rain},\\
R & \eqdef & \text{there is rain in London} ,\\
U & \eqdef & \text{Mr.Paddington takes his umbrella  }.
\end{eqnarray*}

Using the law of total probability, we have

\[
\prob{R} = \prob{R \mid F} \prob{F} + \prob{R \mid {\overline F}} \prob{{\overline F}}
\]

Plugging in values we get:
\begin{eqnarray*}
\frac{1}{2} &= & \frac{2}{3}\pr{F} +\frac{1}{3}\pr{{\overline F}}\\
&= & \frac{2}{3}\pr{F} + \frac{1}{3}(1-\pr{F}) \\
&= & \frac{1}{3}\pr{F} + \frac{1}{3}
\end{eqnarray*}

Therefore, $\pr{F} = \frac{1}{2}$.
}

\ppart Find the probability that Paddington has no umbrella, given that it rains.

\solnospace{We construct a tree as shown below. 

\begin{figure}[htb]
\begin{center}
\includegraphics[width=4in]{figures/Probability_Tree_Figure}
\end{center}
\caption{Probability Tree}
\label{fig:Probability_Tree_Figure}
\end{figure}


We wish to find
\begin{eqnarray*}
\prob{\text{no umbrella}  \mid \text{rain}}
  & = &\frac{\prob{\mbox{no umbrella} \wedge \mbox{rain}}}{\prob{\mbox{rain}}}\\
& = & \frac{1/9}{1/2} = 2/9.
\end{eqnarray*}
}

\ppart Find the probability that it doesn't rain, given that he brings his
umbrella.

\solnospace{
we wish to find
\begin{eqnarray*}
\prob{\text{no rain} \mid \text{umbrella}} & = &
 \frac{\prob{\mbox{no rain} \wedge \mbox{umbrella}}}{\prob{\mbox{umbrella}}}\\
& = & \frac{1/6 + 1/9}{1/9 + 1/6 + 1/3 + 1/18} = 5/12
\end{eqnarray*}
}

\eparts


% fall 00 
% tournament probabilities
\problem
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}%[htbp]
%\centerline{\psfig{figure=/a/class/6.042/fall00/handouts/fig/H64-tennis.eps,height=4in}}
\centerline{\includegraphics[height=4in]{figures/H64-tennis}}
\label{tennis}
\end{figure}

\bparts

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

\solnospace{
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?

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


% Spring 98
% Probability - different ways of computing
%\problem
%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.
%
%\solnospace{
%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 2nd, 3rd, \dots, 9th position. So there are 8 ways to
%put the number {\tt 0}.  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\cfrac{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
%\[
%\cfrac{8!}{4!\, 2!\, 2!}=420.
%\]
%This is because once {\tt 0} 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 {\tt 2} is%
%\[
%7 \cdot \frac{7!}{3!\, 2!\, 2!}=1470.
%\]
%This is because with the number {\tt 2} fixed at the 9th digit, the number
%{\tt0} has to choose among the 2nd, 3rd, \dots, 8th positions.  Therefore
%there are 7 choices to put {\tt 0}. The remaining 7 numbers can permute in
%the remaining 7 positions in $\cfrac{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 $\cfrac{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
%$\cfrac{1}{8}$, the probability that $p$ ends with other numbers is
%$\cfrac{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
%$\cfrac{7}{8} \cdot \cfrac{1}{8}=\cfrac{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 \cfrac{7}{64} = \cfrac{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*}
%\pr{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 25.
%
%\solnospace{
%{\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\cfrac{6!}{3!1!2!}=360$.
%The number of outcomes that end with {\tt50} is $\cfrac{7!}{4!1!2!}=105$. The
%number of outcomes that end with {\tt75} is $6 \cdot \cfrac{6!}{4!1!1!}=180$.
%Therefore the probability that $p$ is a multiple of 25 is
%$\cfrac{360+105+180}{3360}=\cfrac{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*}
%\Pr{p\mbox{ ends with {\tt 25}}}&=&\Pr{A_2 \cap B_5}\\
%&=&\Pr{A_2|B_5}\Pr{B_5}\\
%&=&\underbrace{(1-\frac{1}{7})\cdot4\cdot\frac{1}{7}}_{\Pr{A_2|B_5}}\cdot2\cdot\frac{7}{64}\\
%&=&\frac{3}{28}\\
%\\
%&=&\underbrace{2\cdot\frac{1}{8}}_{\Pr{A_5|B_0}}\cdot\frac{1}{8}\\
%&=&\frac{1}{32}\\
%\\
%\Pr{p\mbox{ ends with {\tt 75}}}&=&\Pr{A_7 \cap B_5}\\
%&=&\Pr{A_7|B_5}\Pr{B_5}\\
%&=&\underbrace{(1-\frac{1}{7})\cdot2\cdot\frac{1}{7}}_{\Pr{A_7|B_5}}\cdot2\cdot\frac{7}{64}\\
%&=&\frac{3}{56}\\
%\end{eqnarray*}
%
%Therefore, $\Pr{p$ is a multiple of 25$} = \cfrac{3}{28} + \cfrac{1}{32} +
%\cfrac{3}{56} = \cfrac{43}{224}$.
%}
%
%\ppart the first and the last digits of $p$ are {\tt 2}.
%
%\solnospace{
%{\bf Method 1: Counting}
%
%The number of outcomes that both start and end with a {\tt2} is
%$\cfrac{7!}{1!2!2!2!}=630$. Therefore the probability that the first and the
%last digits of $p$ are both {\tt2} is $\cfrac{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 $\cfrac{1}{8}$ to be the first digit.
%
%\begin{eqnarray*}
%\Pr{p\mbox{ starts and ends with {\tt 2}}}&=&\Pr{A_2 \cap B_2}\\
%&=&\Pr{A_2|B_2}\Pr{B_2}\\
%&=&\underbrace{3\cdot\frac{1}{7}}_{\Pr{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)
%
%\solnospace{
%%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 $\cfrac{4!}{2!1!1!}=12$.
%On the other hand, the number of all possible permutations of the 9 integers is
%$\cfrac{8\cdot8!}{4!2!2!1!}$. Since each number is equally likely to appear, the
%probability that $p$ is symmetric is
%$\cfrac{12}{\frac{8\cdot8!}{4!2!2!1!}}=\frac{1}{280}$.
%}
%\eparts


% Spring 00 
% Bayes
%\problem %source: spring00 ps8
%We know from statistics that when a policeman gets shot he/she survives with
%probability $0.8$ if he/she wears a bullet-proof vest and survives with
%probability $0.12$ if the policeman doesn't wear a vest.
%Given that 15\% of the policemen wear bullet-proof vests, what is the
%probability that a random policeman was wearing a bullet-proof vest if he/she
%survived a firearm attack?
%
%\solnospace{
%Let $B$ be the event the policeman wears a vest.  Let $W$ be the
%event the policeman survives an attack.
%We want to compute $Pr(B|W)$.  By Bayes' theorem,
%\[
%Pr(B|W)=\frac{Pr(W|B)Pr(B)}{Pr(W|B)Pr(B)+Pr(W|\overline{B})Pr(\overline{B})}
%= \frac{(0.8)(.15)}{(0.8)(0.15)+(0.12)(0.85)} =0.54
%\]
%
%An equally valid solution would be to draw out a tree of the
%conditional probabilities and to calculate the solution
%``graphically''.
%}
%
% spring 98 
% false positive
%\problem [10 pts]
%
%A house is installed with a fire alarm to prevent fire accidents. If there
%is a fire, the probability for the fire alarm being turned on is 96\%.
%Even without a fire, the alarm may be turned on with a probability of 2\%.
%Suppose the probability for a fire accident to happen in the house is 1\%.
%If the fire alarm is now on, what is the conditional probability that there
%is really a fire accident?

%\solnospace{
%{\bf Solution}
%
%Let $F$ be the event that ``a fire accident happens''. Then let $A$ be the
%event that ``the alarm is on''.
%
%From the question, we have:
%\begin{itemize}
%\item $\Pr{A|F}=0.96$
%\item $\Pr{A|\overline{F}}=0.02$
%\item $\Pr{F}=0.01$
%\end{itemize}
%
%We want to find:
%\begin{eqnarray*}
%\Pr{F|A}&=&\frac{\Pr{F\cap A}}{\Pr{A}}\\
%      &=&\frac{\Pr{A|F}\Pr{F}}{\Pr{A|F}\Pr{F}+\Pr{A|\overline{F}}\Pr{\overline{F}}}\\
%      &=&\frac{0.96\times 0.01}{0.96\times0.01+0.02\times0.99}\\
%      &=&\frac{16}{49}
%\end{eqnarray*}
%}

%FAll 99
% conditional prob
%\problem %{\bf Independence}
%\textbf{The Flippant Juror}
%
%A three-person jury has two responsible members, each of whom
%independently has a probability $p> 1/2$ of making the correct decision.
%The third juror flips a 50-50 coin for each decision.  So a one-person
%jury with a responsible juror has probability $p$ of making the correct
%decision.  Suppose the three-person jury decides by majority.  Which jury
%has the better probability of making the correct decision, a
%one-repsonsible-person jury or the three-person jury?%
%
%\solnospace{
%
%Suppose the members of the 3-person jury are Socrates, Plato, and
%Homer Simpson.  Socrates and Plato have both independently a probability
%$p$ of making the right choice, and Homer just flips a coin.
%Here are the events in which case the 3-person jury could be right:
%\begin{itemize}
%\item
%Socrates and Plato are both right, (in which case what Homer says is irrelevant, as the
%majority rules): probability of this event is  $p^2$;

%\item
%Socrates is right, Plato is wrong, and Homer is right: probability of this event is $\cfrac{1}{2}
%p (1-p)$;

%\item
%Socrates is wrong, Plato is right, and Homer is right: probability of this event is $\cfrac{1}{2}
%p (1-p)$.
%\end{itemize}

%These events are disjoint, so the probability that one of them occurs
%is the sum $p^2 + p(1-p) = p$.  Thus the 3-person jury and the
%1-person jury have the {\it same} probability of making the correct
%decision.
%
%}

% Spring 98 
%\problem There are 4 coins in a box, namely $c_1, c_2, c_3, c_4$. The
%probability $p_i$ that the coin $c_i$ gives a Head is $\cfrac{1}{i}$ for
%$1\leq i\leq 4$.  A coin is selected from the box uniformly at random, and
%is being tossed until a Head is seen.
%
%\bparts
%\ppart
%Write down the sample space of the experiment. 
%
%\solnospace{
%The sample space is
%$\{(c_1,H)\}\cup\{c_2,c_3,c_4\}\times\{H,TH,TTH,TTTH,\dots\}$
%}
%
%\ppart
%What is the probability that a Head is first seen in the $2\text{nd}$ toss?
%\solnospace{
%For this part and the following part, let $H_i$ be the event that ``a Head is first seen in the $i^{th}$ toss''. Let $C_i$ be the event that ``$c_i$ is drawn 
%from the box''.
%
%\begin{eqnarray*}
%\Pr{H_2}  &=&\Pr{H_2|C_1}\Pr{C_1}+\Pr{H_2|C_2}\Pr{C_2}+\Pr{H_2|C_3}\Pr{C_3}+\Pr{H_2|C_4}\Pr{C_4}\\
%        &=&0\cdot\frac{1}{4}+\underbrace{\frac{1}{2}\cdot\frac{1}{2}}_{\Pr{H_2|C_2}}\cdot\frac{1}{4}+\underbrace{\frac{2}{3}\cdot\frac{1}{3}}_{\Pr{H_2|C_3}}\cdot\
%frac{1}{4}+\underbrace{\frac{3}{4}\cdot\frac{1}{4}}_{\Pr{H_2|C_4}}\cdot\frac{1}{4}\\
%        &=&\frac{95}{576}\\
%\end{eqnarray*}
%}
%
%\ppart
%Given that a Head is first seen in the $2\text{nd}$ toss, what is the
%%probability that $c_i$ is selected from the box? 
%
%\solnospace{
%\begin{eqnarray*}
%\Pr{C_i|H_2}&=&\frac{\Pr{C_i\cap H_2}}{\Pr{H_2}}\\
%         &=&\frac{\Pr{H_2|C_i}\Pr{C_i}}{\Pr{H_2}}\\
%         &=&\frac{\frac{i-1}{i}\cdot\frac{1}{i}\cdot\frac{1}{4}}{\frac{95}{576}}\\
%         &=&\frac{144(i-1)}{95i^2}
%\end{eqnarray*}
%
%%{\bf Checking:} $\Pr{C_1|H_2}+\Pr{C_2|H_2}+\Pr{C_3|H_2}+\Pr{C_4|H_2}=0+\frac{144}{95\cdot4}+\frac{144\cdot2}{95\cdot9}+\frac{144\cdot3}{95\cdot16}=1$. This makes sense.
%}
%
%\eparts

%\problem
% 18.313 Quiz I, problem 3
%
%A population consists of $c_1$ members of type 1, $c_2$ members
%of type $2,\cdots ,c_n$ members of type $n$.  A set of $k$ members is
%drawn from the population without replacement.
%
%\bparts
%\ppart Find the probability that exactly $i$ members of type 1
%were chosen.
%
%\solnospace{
%Let $N_{1i}$ be the event that exactly $i$ members of class 1 were
%chosen.  $\prob{N_{1i}} = \frac{\binom{c_1}{i} \times \binom{c_2+\cdots +
%c_n}{k-i}}{\binom{c_1+\cdots +c_n}{k}}$.
%}
%
%\ppart Find the probability that exactly $i$ members of class 1
%and exactly $j$ members of class 2 were chosen.
%
%\solnospace{
%Let $N_{2j}$ be the event that exactly $j$ members of class 2 were
%chosen.  Then $ \prob{N_{1i} \cap N_{2j}} = \frac{\binom{c_1}{i} \binom{c_2}{j}
%\binom{c_3 +\cdots + c_n}{k-i-j}}{\binom{c_1 + \cdots +c_n}{k}} $}
%
%\eparts

\iffalse

% Modified Inclusion-Exclusion form fall 00
% Product rule, trees
\problem 

Given a bit string of length 10, what is the probability the string contains either five consecutive $0$s or five consecutive $1$s?

\solnospace{There are $2^{10}$ bit strings of length 10.  First, let's
see how many of those contain five consecutive $0$'s (denote this as
$E_1$). The sequence of the 5 $0$'s can start at position $1,2,3,4,5$ or
$6$. In each case, the remaining $5$ bits are allowed to be anything, so,
as a ``first approximation'', we can say that there are $6*2^5$ different
strings of consecutive $0$'s. \par However, if we do this, we are
\emph{overcounting} since, for example, the string that has its first $8$
bits equa l to $0$ and the last $2$ equal to $1$ (that is, $0000000011$)
will be counted as a valid string \emph{four times} by our method:
\underline{00000}00011, 0\underline{00000}0011, 00\underline{00000}011 and
000\underline{00000}11. We need to eliminate these duplicates, which occur
whenever we are dealing with strings that have more than 5 consecutive
$0$'s. \par

We can do this by calculating the number of strings with $6$ or more
consecutive $0$'s using the same method as above. This will give us
$5*2^4$ such strings, and for each sequence of $0$'s, we will be
overcounting exactly one time less than we overcounted above: for example,
going back to the string of $8$ consecutive $0$'s that was counted 4 times
above, we see that this method will count it exactly $3$ times
\underline{000000}0011, 0\underline{000000}011, 00\underline{000000}11.
The same will hold for all strings of length $\geq 6$ because the number
of allowed starting positions for a sequence of $6$ $0$'s is exactly one
less than the number of allowed starting positions for a sequence of $5$
consecutive $0$'s. Thus, it suffices to subtract this number from the
number we got before to get rid of duplicates. Therefore, the number of
strings containing 5 or more consecutive $0$'s is
\[
6*2^5-5*2^4=112
\]
So $|E_1|$ is 112.  The probability of any string having 5 consecutive
$0$'s is then $\Pr{E_1} = 112/2^{10}$.

By symmetry, the probability that our string contains five consecutive $1$'s
is $\Pr{E_2} = 112/2^{10}$. 

The question was to determine the probability that our string has either 5
$0$'s or 5 $1$'s so what we are looking for is $\pr{E_1\cup E_2}$.  The
intersection of $E_1$ and $E_2$ (i.e, sequences that contain \emph{both} 5
$0$'s and 5 $1$'s) contains 2 elements: $0000011111$ and
$1111100000$. Therefore, $\pr{E_1\cap E_2} = 2/2^{10}$.

We then apply Inclusion-Exclusion
\begin{eqnarray*}
\pr{E_1\cup E_2} & = &
        \pr{E_1} + \pr{E_2} - \pr{E_1\cap E_2} \\
& = &   112/2^{10} + 112/2^{10} - 2/2^{10} \\
& = &   222/2^{10} \\
& = &   0.2168
\end{eqnarray*}
}
\fi


% Another inclusion-exclusion
%\problem %(5 points)
%
%In a survey of 270 college students, it is found that:
%\begin{itemize}
%\item 64 like brussels sprouts
%%\item 94 like broccoli
%\item 58 like cauliflower
%\item 26 like both brussels sprouts and broccoli
%\item 28 like both brussels sprouts and cauliflower
%\item 22 like both broccoli and cauliflower
%\item 14 like all three vegetables
%\end{itemize}

%What is the probability a student does not like \emph{any} of the
%aforementioned vegetables?

%\solnospace{Let $E_0$ be the event that a selected student likes all
%three vegetables.  What we are then looking for is $1-\pr{E_0}$.

%Let $E_1$ be the event a selected student is a sprout-lover, $E_2$ be the
%event a selected student is a Cauliflower-lover, and $E_3$ be the event a
%selected student is a broccoli-lover.

%By Inclusion-Exclusion: 
%
%\begin{eqnarray*}
%\pr{E_0} 
%& = &  \pr{E_1\cup E_2\cup E_3} \\
%& = &   \pr{E_1} + \pr{E_2} + \pr{E_3} - \pr{E_1\cap E_2} - \pr{E_1\cap E_3} - \pr{E_2\cap E_3} + \pr{E_1\cap E_2\cap E_3}\\
%& = &   64/270 + 58/270 + 94/270 - 28/270 - 26/270 - 22/270 + 14/270 \\
%& = &   154/270 \\
%& = &   0.57
%\end{eqnarray*}

%Therefore, $1-\pr{E_0} = 1-0.57 = 0.43$.
%}

\problem
\begin{theorem*}[Relative Probability]

Let $\mathcal{P} \eqdef (S, \pr{})$ be a probability space and $C$ be an
event with nonzero probability.  Then
\[
\mathcal{P}_C \eqdef (S, \prsub{C}{})
\]
is also a probability space, where for any event $A$,
\begin{equation}\label{defprc}
\prsub{C}{A} \eqdef \prcond{A}{C}.
\end{equation}
\end{theorem*}
We call $\prsub{C}{}$ the \emph{probability relative to $C$}, and
$\mathcal{P}_C$ the \emph{probability space relative to $C$}.

\bparts 

\ppart Prove the Relative Probability Theorem. (Hint: Review the
definition of a probability space in
\hyperref{http://theory.lcs.mit.edu/classes/6.042/fall01/lectures/l10.pdf}{l10}{probsp}{Notes 10, Definition 4.2}.

\solnospace{
A probability space is defined to be a sample space $S$ and a probability function $\pr{}$ which satisfies two properties:
\begin{enumerate}
\item $\pr{S} =1$, and

\item if $A$ is the disjoint union of a sequence of events
$A_0,A_1,\dots$, then $A$ is an event, $\sum_{i\in\nats} \pr{A_i}$
converges and
\begin{equation}\tag{Sum Rule}
\pr{A} = \pr{\lgunion_{i\in\nats}A_i} = \sum_{i\in\nats} \pr{A_i}.
\end{equation}
\end{enumerate}

First, we see that the sample space for the new probability space has not 
changed.  We must then just show that the new probability function $\prsub{C}{}$
still satisfies the two conditions.

\begin{enumerate}
\item 
To show this:
\begin{align*}
\prsub{C}{S} &= \prcond{S}{C} & \text{definition~(\ref{defprc}) of $\prsub{C}{}$}\\
             &= \frac{\pr{S \cap C}}{\pr{C}} & \text{definition of $\prcond{S}{C}$}\\
             &= \frac{\pr{C}}{\pr{C}} & \text{since $C \subseteq S$}\\
             &= 1 & \text{since $\pr{C} \neq 0$.}
\end{align*}

\item
The Sum Rule can be verified as follows:

\begin{align*}
\prsub{C}{\lgunion_{i\in\nats}A_i}
    &= \pr{\lgunion_{i\in\nats}A_i \biggm| C} &
          \text{definition~(\ref{defprc}) of $\prsub{C}{}$}\\\\
    &= \frac{\pr{(\lgunion_{i\in\nats}A_i) \cap C}}{\pr{C}} &
           \text{definition of $\prcond{\cdot}{C}$}\\
    &= \frac{\pr{\lgunion_{i\in\nats}(A_i \cap C)}}{\pr{C}}&
             \text{distributive law}\\
    &= \sum_{i \in \nats} \frac{\pr{A_i \cap C}}{\pr{C}} & \text{Sum Rule}\\
    &=  \sum_{i \in \nats} {\prcond{A_i}{C}} &
           \text{definition of $\prcond{\cdot}{C}$}\\\\
    &= \sum_{i \in \nats} {\prsub{C}{A_i}}&
          \text{definition~(\ref{defprc}) of $\prsub{C}{}$}
\end{align*}

\end{enumerate}
}

\ppart Explain why the two-set Inclusion-Exclusion Law for conditional
probabilities,
\[
\prcond{A\union B}{C} = \prcond{A}{C} + \prcond{B}{C} - \prcond{A
\intersect B}{C},
\]
now follows immediately from ordinary two-set Inclusion-Exclusion
(without having to mimic the ordinary proof using conditional
probabilities).

\solnospace{
Now that we have this nifty theorem about relative probability, we no
longer have to re-derive formulas and laws with conditional probabilities and
treat them differently. 
The new probability space we defined was different from the original in that
the probability function now represents probabilities that are conditioned on
event $C$. These are exactly the conditional probabilities used in the Inclusion-Exclusion Law for conditional probabilities.  Since in part a, we have shown that the original sample space together with the probability function representing these probabilities form a valid probability space, we are able to extend
any laws for probability spaces to conditional probabilities. 
}
\eparts      

\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


%fall 00
% i remember this problem from when i took the class =)
\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}$.

\solnospace{

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.

\solnospace{ We can use the results from a directly by figuring out what
the $p_i$'s and the $q_i$'s are in this situation.  In this case, we care
about if a woman will develop cancer for the ages of 20, 30, 40, 50 and
60.  Therefore, $i$ in this case is such that $i \subseteq \set{20, 30,
40, 50, 60}$.

The $p_i$'s are the probabilities that a woman will develop cancer in the next
10 years. (analogous to the letter being in the next envelope)

The $q_i$'s are the probabilities of a woman in the U.S eventually
developing cancer sometime in the future given that she does not have it
now.  (analogous to the letter being somewhere left in the drawer).

As seen from part a, the $p_i$'s increase while the $q_i$'s decrease.}
\eparts

\end{problems}

\end{document}                            
