\documentclass[11pt,twoside]{article}   
\usepackage{latex-macros/course}

\renewcommand{\coursecopyrightnames}
{\href{http://theory.lcs.mit.edu/~meyer}{Prof.~Albert~R.~Meyer}}

\renewcommand{\reading}{\textbf{For this Problem Set:}
\href{http://theory.lcs.mit.edu/classes/6.042/fall02/handouts/lectures/ln10.pdf}
{Week 10 Notes}, \S1--9; Optional: Rosen \S \S 4.4 \& 4.5 through Example
4, p.271.

\textbf{For this Week's Lectures and Class Problems:} 
Complete \href{http://theory.lcs.mit.edu/classes/6.042/fall02/handouts/lectures/ln10.pdf}
{Week 10 Notes}; Optional: Rosen \S \S 4.4 \& 4.5 through Example 9, p. 274.
}

\begin{document}
\problemset{10}

\begin{problem}
There are 4 different coins in a box.  The probability of Heads when
flipping the $i$th coin is $1/i$ for $1\leq i\leq4$.  A coin is selected
from the box randomly, and gets tossed until a Head appears.

\begin{problemparts}
\problempart
Write down a probability space for the experiment.  Be sure to verify that
the sum of the probabilities of the sample points is 1.

\solution{
A possible sample space is
\[
\set{1,2,3,4} \times \set{H,TH,TTH,TTTH,\dots},
\]
indicating the number of the coin was selected and the flip outcomes where
until a head appeared.  Define
\[
\pr{(i,T^{n} H)} \eqdef \frac14 \cdot \frac{1}{i} \cdot \left(\frac{i-1}{i}\right)^{n}.
\]
Then
\begin{align*}
\sum_{i \in \set{1,2,3,4}, n \ge 0} \pr{(i,T^{n} H)}
  = & \sum_{i \in {1,2,3,4}}  \sum_{n \ge 0}   \frac14 \cdot \frac{1}{i} \cdot \left(\frac{i-1}{i}\right)^{n}\\
  = & \sum_{i \in {1,2,3,4}} \frac14 \cdot \frac{1}{i} \sum_{n \ge 0} \left(\frac{i-1}{i}\right)^{n}\\
  = & \sum_{i \in {1,2,3,4}} \frac14 \cdot \frac{1}{i} \cdot \frac{1}{1-\frac{i-1}{i}}\\
  = & \sum_{i \in {1,2,3,4}} \frac14 \cdot \frac{1}{i} \cdot \frac{1}{\frac{1}{i}}\\
  = & 4 \cdot \frac14 = 1.
\end{align*}
}

\problempart What is the probability that a Head is first seen in the
$2$nd toss?

\solution{For this part and the following part, let $H_i$ be the event
that ``a Head was first seen on the $i$th toss''. Let $C_i$ be the event
that ``the $i$th coin was drawn from the box''.

\begin{eqnarray*}
\pr{H_2}  &=& \prcond{H_2}{C_1}\pr{C_1} + \prcond{H_2}{C_2}\pr{C_2} + 
               \prcond{H_2}{C_3}\pr{C_3} + \prcond{H_2}{C_4}\pr{C_4}\\
          &=& 0 \cdot \frac{1}{4} +
               \underbrace{\frac{1}{2}\cdot\frac{1}{2}}_{\prcond{H_2}{C_2}}
               \cdot \frac{1}{4} +
               \underbrace{\frac{2}{3}\cdot\frac{1}{3}}_{\prcond{H_2}{C_3}}
               \cdot \frac{1}{4} +
               \underbrace{\frac{3}{4}\cdot\frac{1}{4}}_{\prcond{H_2}{C_4}}
               \cdot \frac{1}{4}\\
        &=& \frac{95}{576}
\end{eqnarray*}
}

\problempart\label{CiH2}

Given that a Head is first seen in the 2nd toss, what is the
probability that $i$th coin was selected from the box?

\solution{
\begin{eqnarray*}
\prcond{C_i}{H_2}&=&\frac{\pr{C_i \cap H_2}}{\pr{H_2}}\\
  &=&\frac{\prcond{H_2}{C_i}\pr{C_i}}{\pr{H_2}}\\
  &=& \frac{\dfrac{i-1}{i} \cdot \dfrac{1}{i} \cdot\ \dfrac{1}{4}}{\dfrac{95}{576}}\\
  &=&\frac{144(i-1)}{95i^2}
\end{eqnarray*}
}

\ppart  Check your answer to part~(\ref{CiH2}) to be sure it satisfies:
\[
\prcond{C_1}{H_2} + \prcond{C_2}{H_2} + \prcond{C_3}{H_2} +
\prcond{C_4}{H_2} = 1.
\]

\solution{
\begin{eqnarray*}
\lefteqn{\prcond{C_1}{H_2} + \prcond{C_2}{H_2} + \prcond{C_3}{H_2} +
\prcond{C_4}{H_2}} \\
 & = & 0 + \frac{144}{95\cdot4} + \frac{144\cdot 2}{95\cdot9}
+ \frac{144\cdot3}{95\cdot16}\\
 & = & \frac{144 \cdot 4 \cdot 9}{95\cdot 16 \cdot 9}
      + \frac{144\cdot 2 \cdot 16}{95\cdot 16 \cdot 9} 
      + \frac{144\cdot 3 \cdot 9}{95\cdot 16 \cdot 9}\\
  & = & \frac{4 \cdot 9}{95}
      + \frac{2 \cdot 16}{95} 
      + \frac{3 \cdot 9}{95}\\
  & = & \frac{95}{95} = 1.
\end{eqnarray*}
}

\end{problemparts}

\end{problem}


\iffalse

\begin{problem}

There is a course---not 6.042, naturally---in which $10 \%$ of the
assigned problems contain errors.  If you pick a random problem and ask
your TA and your Lecturer whether the problem has an error, then your TA
will answer correctly $80\%$ of the time.  This $80 \%$ accuracy holds
regardless of whether or not a problem has an error.  Likewise for your
Lecturer, but with only $75 \%$ accuracy.  (This is consistent with the
view that Lecturers are chosen for their theatrical personalities, not
their mastery of the material \texttt{:-)})

Furthermore, \emph{the correctness of the lecturers' answer and the TA's
answer are independent of each other, regardless of whether there is an
error}.\footnote{This assumption is questionable: by and large, we would
expect the lecturer and the TA's to spot the same glaring errors and to be
fooled by the same subtle ones.}

Is the event that ``the TA says that there is an error'', independent
of the event that ``the lecturer says that there is an error''?

In writing your solution, designate events as follows:
\begin{eqnarray*}
T & \eqdef & \mbox{``the TA says the problem has an error,''}\\
L & \eqdef & \mbox{``the lecturer says the problem has an error.''}\\
E & \eqdef & \mbox{``the problem has an error,''}
\end{eqnarray*}

\solution{
The answer is no.  Because the TA is usually right, when the TA
says that the problem has an error, the likelihood that there really is an
error is increased.  But the lecturer is also usually right, so increasing
the likelihood of there \emph{being} an error also increases the
likelihood that the lecturer will \emph{report} an error.

We verify this informal argument by actually calculating the probability
of each of these events and their intersection, and then observing that
the probability that the two events occur is different from the product of
the probabilities.

The assumptions above tell us:
\begin{align}
\pr{E}        = & \frac{10}{100} = \frac{1}{10},\label{E10}\\
\prcond{T}{E} = & \prcond{\bar{T}}{\bar{E}} = \frac{80}{100} =
     \frac{4}{5},\label{TE}\\
\prcond{L}{E}  = & \prcond{\bar{L}}{\bar{E}}
       = \frac{75}{100} = \frac{3}{4}\label{LE}.
\end{align}

Also, $T$ and $L$ are independent given $E$, and given $\bar{E}$:
\begin{align}
\prcond{T \intersect L}{E}  = & \prcond{T}{E} \prcond{L}{E}\label{TLE}\\
\prcond{T \intersect L}{\bar{E}}  = & \prcond{T}{\bar{E}}
                      \prcond{L}{\bar{E}}  \label{TLbarE}. 
\end{align}

Note that while we know that $T$ and $L$ are independent \emph{given} $E$
or \emph{given} $\bar{E}$, we will show that they are not independent by
themselves.  In fact, we will show:
%\begin{claim*}
\[
\pr{L \intersect T} > \pr{L}\pr{T}.
\]
%\end{claim*}

We have:

\begin{align*}
\pr{T} = & \pr{T \cap E} + \pr{T \cap \bar{E}}
        & \text{(Law of Total Probability)}\\
 = & \prcond{T}{E} \pr{E}  + \prcond{T}{\bar{E}} \pr{\bar{E}}
        & \text{(Product Rule)} \\
 = & \prcond{T}{E} \pr{E}  + (1- \prcond{\bar{T}}{\bar{E}})(1- \pr{E})
        & \text{(Complement Rule)} \\
 = & \prcond{T}{E} \pr{E}  + (1- \prcond{T}{E})(1- \pr{E})
        & \text{(by~(\ref{TE}))} \\
 = & \frac{4}{5} \frac{1}{10} + (1 - \frac{4}{5})(1 - \frac{1}{10})
        = \frac{13}{50}, & \text{(by~(\ref{TE}) and~(\ref{E10}))}\\
\end{align*}

A similar argument proves that
\begin{equation}
\pr{L} =  \pr{L \cap E} + \pr{L \cap \bar{E}}
  = \frac{3}{4} \frac{1}{10} + (1 -\frac{3}{4})(1 - \frac{1}{10}) = \frac{3}{10}.
\end{equation}

Finally,
\begin{align*}
\pr{L \cap T} = & \pr{L \cap T \cap E} + \pr{L \cap T \cap \bar{E}}
        & \text{(Law of Total Probability)}\\
= & \prcond{L \cap T}{E} \pr{E} + \prcond{L \cap T}{\bar E} \pr{\bar E}
        & \text{(Product Rule)} \\
= & \prcond{L}{E}      \prcond{T}{E}       \pr{E} + 
      \prcond{L}{\bar{E}} \prcond{T}{\bar{E}} \pr{\bar E} &
        \text{(by~(\ref{TLE}) and~(\ref{TLbarE}))}\\
= & \frac{3}{4} \cdot \frac{4}{5} \cdot \frac{1}{10}
        + (1 - \frac{3}{4}) (1 - \frac{4}{5}) (1 - \frac{1}{10}) =
        \frac{105}{1000} = 0.105. & \text{(by~(\ref{LE}) and~(\ref{TE}))}
\end{align*}
which is higher than 
\[
\pr{L}\pr{T} = \frac{3}{10} \cdot \frac{13}{50} = .078.
\]
}

\end{problem}
\fi


\iffalse

\begin{problem} 
\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{

For the ``stick'' strategy, the probability of winning the pig is clearly
$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.

\begin{figure}[htbp]
\begin{center}
\includegraphics[width=2.5in]{figures/sol9-pigfind}
\end{center}
\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 $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{

Stu guesses the right door initially with probability
$1/4$ and guesses the wrong door with probability
$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 $1/4 \cdot 1
+ 3/4 \cdot 0 = 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
$1/4$ and guesses the wrong door with probability
$3/4$.  If she was right initially, then she can not win.  If
she was wrong initially, then she wins with probability $1/2$.
Therefore, her probability of winning is $1/4 \cdot 0 +
3/4 \cdot 1/2 = 3/8$.
}

\end{problemparts}
\end{problem}
\fi


\begin{problem}
We consider a variation of Monty Hall's game.  The contestant still picks
one of three doors, with a prize randomly placed behind one door and goats
behind the other two.  But now, instead of always opening a door to reveal
a goat, Monty instructs Carol to \emph{randomly} open one of the two doors
that the contestant hasn't picked.  This means she may reveal a goat, or
she may reveal the prize.  If she reveals the prize, then the entire game
is \emph{restarted}, that is, the prize is again randomly placed behind
some door, the contestant again picks a door, and so on until Carol
finally picks a door with a goat behind it.  Then the contestant can
choose to stick with his original choice of door or switch to the other
unopened door.  He wins if the prize is behind the door he finally chooses
at this point; otherwise he loses.

To analyze this setup, define two events:
\begin{description}
\item[$GP$:] The event that the contestant \textbf{g}uesses the door with
the \textbf{p}rize behind it on his first guess.

\item[$OP$:] The event that the game is restarted at least once.  Another
way to describe this is as the event that the door Carol first
\textbf{o}pens has a \textbf{p}rize behind it.
\end{description}

\bparts

\ppart\label{GPnOP} What is $\pr{OP}$?\dots $\prcond{GP}{\bar{OP}}$?

\solution{
\begin{align*}
\pr{GP} = & \frac13,\\
\prcond{OP}{GP} = & 0,\\
\prcond{OP}{\bar{GP}} = & \frac12,\\
\pr{OP} = & \prcond{OP}{GP}\pr{GP} + \prcond{OP}{\bar{GP}}\pr{\bar{GP}}\\
        =& 0\cdot \frac13 + \frac12 \cdot \frac23 = \frac13,\\
\prcond{GP}{\bar{OP}} \eqdef & \frac{\pr{GP \intersect
                                 \bar{OP}}}{\pr{\bar{OP}}}\\
         & = \frac{\pr{GP}}{\pr{\bar{OP}}},
                    & \text{(since $\bar{OP} \subset GP$)}\\
         & = \frac{1/3}{(1- 1/3)} = \frac12.
\end{align*}
}

\iffalse
\ppart Let $R$ be the number of times the game is restarted before Carol
picks a goat.

What is $\expect{R}$?\brule{0.8in}\\
You may express the answer as a simple closed form in terms of $p \eqdef
\pr{OP}$.

\solution{
$1/(1-p) - 1 = 3/2 -1 = 1/2$.

Think of \emph{not} having to restart as a failure.  So
$\pr{\text{failure}} = 1-p$, and $\expect{R}$ is mean time to failure
minus one---because we are only counting the number of
``successes''---namely, $1/\pr{\text{failure}} - 1$.}
\fi

\ppart\label{en} What is the probability the game will end after
\emph{exactly} $n\ge 1$ guesses by the contestant?

\solution{
The game ends after \emph{exactly} $n$ guesses by the contestant providing
Carol opens the prize door $n-1$ times, and then does not open it after
the $n$th guess.  So
\[
\pr{\text{end after exactly $n$ guesses}} = \pr{OP}^{n-1} \cdot \pr{\bar{OP}} =
(1/3)^{n-1} \cdot \frac23 = 2(1/3)^{n}.
\]
}

\ppart\label{sum1} Is it possible for the game never to end?  What is the
probability that the game will end?

\solution{The game could go on forever if the contestant keeps not
guessing the prize and Carol does keep guessing it.  However, the
probability the game will end is 1.  That's because by~(\ref{en})
\[
\pr{\text{game ends}} = \sum_{n =1}^\infty 2(1/3)^{n}
= \frac23 \sum_{n =0}^\infty \left(\frac13\right)^{n} =
\frac23 \cdot \frac{1}{1-1/3} = \frac23 \cdot \frac32 = 1.
\]
}

\eparts
        
When Carol finally picks the goat, the contestant has
the choice of sticking or switching.  The contestant figures that since
this is a 6.042 problem with the Monty Hall rules changed to mislead him
\texttt{:-)}, it's a good guess that the better strategy in the original
game will not be better in this game.  So he decides to use the
\emph{sticking strategy}: when Carol gives him a chance to switch, he will
stick with the door he last guessed.

\bparts

\ppart Describe a simple probability space modelling this game, and verify
that the sum of the probabilities of the sample points is 1.  The space
should have enough sample points to describe the event, $W_n$, that the
game contestant wins after making \emph{at least} $n$ guesses, for every
$n\ge 1$.  Describe the outcomes in $W_n$.

\solution{There are various satisfactory ways to model the game.  The
simplest is to use part~(\ref{en}) and let the outcomes be the number of
guesses in the game, along with an indication of whether the contestant
won.  That is, $\sspace \eqdef \naturals \times \set{\texttt{win},
\texttt{lose}}$ and,
\[
\pr{(n,\texttt{win})} = \pr{(n,\texttt{lose})} \eqdef (1/3)^{n}.
\]
which in part~(\ref{sum1}) we already proved sum to 1.  In this case, $W_n =
\set{(j, \texttt{win}) \suchthat j \ge n}$.

Assuming the contestant chose each door with equal probability, it would
be possible to define a more detailed model indicating at each round
exactly which door the goat was behind and which door the contestant
chose.  For example, the sample point could be all finite sequences of one
or more pairs of the form $(z,g)$ where $z \in \set{1,2,3}$ describes the
number of the door with the prize on some round of the game, and $g \in
\set{1,2,3}$ is the number of the door guessed by the contestant on that
round.  Since this sequence could occur only if Carol chose the prize door
on every round except on the last one, we require $z\neq g$ in all
pairs except possibly for the last one, where $z=g$ is allowed.
A sequence describes a win for the contestant iff $z=g$ in the last pair.

Each pair is equally likely to occur on a given round, so the probability
of each sequence of length $n$ should be the $(1/9)^{n}$ times the
probability that the sequence describes a game that ends.  The probability
of ending will $(1/2)^n$ for sequences ending with $z \neq g$, since that
is the probability Carol that picks the prize door the first $n-1$ times
and the nonprize door on the last round.  For sequences ending with $z=g$,
it will be $(1/2)^{n-1}$ since she is sure to pick the nonprize door on
the final round.  So the probability of a sequence of length $n$ that ends
with $z=g$ is \emph{defined} to be $(1/9)^n(1/2)^{n-1}$ and is defined to
be $(1/9)^n(1/2)^n$ for sequences ending with $z \neq g$.  The event $W_n$
would consist of all sequences of length $\ge n$.  Using the fact that
there are $6^{n-1}\cdot 3$ such sequences ending with $z=g$ and $6^{n}$
ending with $z\neq g$, a small calculation using the formula for the sum
of a infinite geometric series implies the probabilities sum to 1.}

\ppart
Let $w \eqdef \pr{W}$, where $W$ is the event that the contestant
\emph{w}ins with the sticking strategy.  Express the following
probabilities as simple closed forms in terms of $w$.
\begin{enumerate}
\renewcommand{\labelenumi}{\roman{enumi})}

\item $\prcond{W}{\bar{GP}\intersect \bar{OP}}$
\solution{0}

\item $\prcond{W}{\bar{GP}\intersect OP}$
\solution{$w$}

\item $\prcond{W}{GP}$
\solution{1}

\item $\pr{W}$

\solution{1/2.

One argument is based on the values of preceding probabilities:
\begin{align*}
w  = & \prcond{W}{GP}\pr{GP}
          + \prcond{W}{\bar{GP}\intersect OP} \pr{\bar{GP}\intersect OP}
          + \prcond{W}{\bar{GP}\intersect \bar{OP}} \pr{\bar{GP}\intersect \bar{OP}}
          & \text{(Law of Total Probability)}\\
   = & 1 \cdot \frac13 + w \cdot \prcond{\bar{GP}}{OP}\pr{OP} + 0\\
   = & \frac13 + w \cdot 1 \cdot \frac13
   = & 1/3 + w/3.
\end{align*}
So $w(1- 1/3) = 1/3$ and hence $w = 1/2$.

Alternatively, we can observe that when the game ends exactly when Carol
opens a door that does not have the prize.  At this point, the contestant
wins iff he last guessed the door with the prize.  So
\[
\pr{W} = \prcond{GP}{\bar{OP}},
\]
and by part~(\ref{GPnOP}), $\pr{W} = 1/2$.}

\end{enumerate}

\ppart For any final outcome where the contestant wins with a ``stick''
strategy, he would lose if he had used a ``switch'' strategy, and vice
versa.  In the original Monty Hall game, we concluded immediately that the
probability that he would win with a ``switch'' strategy was $1-\pr{W}$.
Why isn't this conclusion quite as obvious for this new, restartable game?
Is this conclusion still sound?  Briefly explain.

\solution{Switching strategies turns wins to losses for games that
\emph{end}.  So the probability of win with switch is $t-\pr{W}$ where $t$
is the probability the game will end.  The original Monty Hall game
terminates after one door-opening, so $t$ was 1.

The extra complication here is that it is possible for the game to run
forever.  But this event has probability 0, so $t$ is still 1, and the
conclusion is still sound.}

\eparts

\end{problem}


\begin{problem}


\begin{problemparts}

\problempart 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).

Find formulas for $p_i$ and $q_i$, and conclude that $p_i$ is a strictly
increasing function of $i$, and $q_i$ is strictly decreasing.

\hint Observe that if event $A$ implies event $B$ then $\prcond{A}{B} =
\pr{A}/\pr{B}$

\solution{
First, we verify the hint.  Saying that event $A$ implies $B$
is the same as saying that that $A \cap B = A$, so
\[
\prcond{A}{B} \eqdef \frac{\pr{A \cap B}}{\pr{B}} = \frac{\pr{A}}{\pr{B}}.
\]

For $1 \le i \le 8$, 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, \dots i.
\end{eqnarray*}

We are given that
\[
\pr{E_i} = 0.1.
\]
But $N_i$ fails to occur iff the letter is in some drawer $j \le i$, so
\[
\pr{N_i} = 1 - \sum_{1 \le j \le i} \pr{E_j} = 1- (0.1)i.
\]
Hence,
\begin{align*}
p_i \eqdef & \prcond{E_{i+1}}{N_i}\\
  \eqdef & \frac{\pr{E_{i+1} \intersect N_i}}{\pr{N_i}} \\
  = & \frac{\pr{E_{i+1}}}{\pr{N_i}} & \text{(since $E_{i+1} \text{ implies } N_i$)}\\
  = & \frac{0.1}{1 - (0.1)i}\\
  = & \frac{1}{10-i},
\end{align*}
which clearly increases as $i$ increases, since the denominator gets
smaller while the numerator remains constant.

Now define for $0 \le i \le 7$,
\[
R_i  \eqdef  \text{letter is in one of drawers } i+1, i+2, \dots 8,
\]
so
\[
\pr{R_i} = \sum_{i < j \le 8} \pr{E_j} = 0.1(8-i).
\]
Hence,
\begin{align*}
q_i \eqdef & \prcond{R_i}{N_i}\\
 = & \frac{\pr{R_i \intersect N_i}}{\pr{N_i}}\\
 = & \frac{\pr{R_i}}{\pr{N_i}} & \text{(since $R_i$ implies $N_i$)}\\
 = & \frac{0.1(8-i)}{1- (0.1)i}\\
 = & \frac{8-i}{10-i}\\
 = & 1 - \frac{2}{10-i},
\end{align*}
which decreases as $i$ increases, since the denominator of the fraction
shrinks, so the fraction becomes greater, so the negation of the fraction
becomes smaller.
}

\problempart
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.

\solution{
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.}
\end{problemparts}
\end{problem}


\iffalse
\begin{problem}

\textbf{More on Birthdays.}  The setting is that we have $q$ balls. View
them as numbered, $1,\dots,q$.  We also have $N$ bins, where $N\geq q$.
We throw the balls at random into the bins, one by one, beginning with
ball~1.  At random means that each ball is equally likely to land in any
of the $N$ bins, and the probabilities for all the balls are independent.
A \emph{collision} is said to occur if some bin ends up containing at
least two balls.  We are interested in the probability, $\text{Col}(N,q)$, of a
collision.

The Birthday ``paradox'' is the case where $N=365$ and we ask what the
chance is that, in a group of $q$ people, there are two people with the
same birthday, assuming birthdays are randomly and independently
distributed over the days of the year.  It turns out that when $q$ gets
near $\sqrt{365}$, the chance of a birthday collision is nearly $1/2$.

This fact can seem surprising when first heard.  The reason it is true is
that the collision probability $\text{Col}(N,q)$ grows roughly proportional to
$q^2/N$. This is the fact to remember.  The following gives a more exact
rendering, providing both upper and lower bounds on this probability.

\begin{proposition}\label{fc-bday} Let $\text{Col}(N,q)$ denote the probability of at 
least one collision when we throw $q\geq 1$ balls at random into $N\geq q$
buckets.  Then
\begin{eqnarray}
 \text{Col}(N,q) & \leq & \frac{q(q-1)}{2N}  \label{eq1}\\
 \text{Col}(N,q) & \geq & 1- e^{-q(q-1)/2N}  \label{eq2}
\end{eqnarray}
for $1\leq q\leq\sqrt{2N}$.
\end{proposition} 

\begin{problemparts}
\problempart
Prove equation \ref{eq1}, which provides an upper bound for $\text{Col}(N,q)$.

\solution{
Let $C_i$ be the event that the $i$-th 
ball collides with one of the previous ones. Then $\pr{C_i}$ is at most
$(i-1)/N$, since when the $i$-th ball is thrown in, there are at most $i-1$
different occupied slots and the $i$-th ball is equally likely to land in any
of them. Now
\begin{eqnarray*}
\text{Col}(N,q) & = & \pr{C_1\vee C_2\vee\cdots\vee C_q} \\
 & \leq & \pr{C_1} + \pr{C_2} + \cdots + \pr{C_q} \\
 & \leq & \frac{0}{N} + \frac{1}{N} + \cdots + \frac{q-1}{N} \\
 & = &  \frac{q(q-1)}{2N} \;.
\end{eqnarray*}
This proves the upper bound. 
}

\problempart
Prove equation \ref{eq2}, which provides a lower bound for $\text{Col}(N,q)$.
You will find
the following inequality useful:
\begin{eqnarray*}
     1 - e^{-x} \:\leq\:  x \;. \nonumber
\end{eqnarray*}
is true for any real number $x$ with $0\leq x\leq 1$.

\solution{
For the lower bound we let $D_i$ be the event
that there is no collision after having thrown in the $i$-th ball. If there is
no collision after throwing in $i$ balls then they must all be occupying
different slots, so the probability of no collision upon throwing in the
$(i+1)$-st ball is exactly $(N-i)/N$. That is,
\[
 \prcond{D_{i+1}}{D_{i}}  = \frac{N-i}{N}  =  1-\frac{i}{N}.
\]
Also note $\pr{D_1}=1$. The probability of no collision at the end of the
game can now be computed via
\begin{eqnarray*}
 1 - \text{Col}(N,q) & = & \pr{D_q} \\
   & = & \prcond{D_q}{D_{q-1}}\cdot\pr{D_{q-1}} \\
    &  \vdots & \vdots \\
 & = & \prod_{i=1}^{q-1} \prcond{D_{i+1}}{D_{i}} \\
 & = & \prod_{i=1}^{q-1} \left(1-\frac{i}{N}\right) \;.
\end{eqnarray*}

% \begin{math}
%  \pr{D_{i+1}} \: = \: \frac{N-i}{N} \: = \: 1-\frac{i}{N} \;.
% \end{math}%
% Also note $\pr{D_1}=1$. The probability of no collision at the end of the
% game can now be computed via
% \begin{eqnarray*}
%  1 - \text{Col}(N,q) & = & \pr{D_q}\dots\pr{D_1} \\
%  & = & \prod_{i=1}^{q-1} \pr{D_{i+1}} \\
%  & = & \prod_{i=1}^{q-1} \left(1-\frac{i}{N}\right) \;.
% \end{eqnarray*}

Note that $i/N\leq 1$. So we can use the inequality $1-x\leq e^{-x}$ for each
term of the above expression. This means the above is not more than
\[
 \prod_{i=1}^{q-1} e^{-i/N} \: = \:
 e^{-1/N-2/N-\cdots-(q-1)/N} \: = \:
 e^{-q(q-1)/2N} \;.
\]
Putting all this together we get 
\[
 \text{Col}(N,q) \:\geq \: 1- e^{-q(q-1)/2N} \;, \protect\vspace{3pt}
\]
which is the second inequality in \ref{fc-bday}.
}

\problempart
Now show that actually
\[
\text{Col}(N,q)  \geq  0.3 \cdot \frac{q(q-1)}{N}
\]
and argue that
\[
\text{Col}(N,q)=\Theta\left(\frac{q^2}{N}\right).
\]

You will find the following inequality useful:
\begin{eqnarray*}
    \left(1-\frac{1}{e}\right)\cdot x \:\leq\:
     1 - e^{-x} \;. \nonumber
\end{eqnarray*}
is true for any real number $x$ with $0\leq x\leq 1$.

\solution{
We know $q(q-1)/2N\leq 1$ because $q\leq
\sqrt{2N}$, so we can use the inequality $1-e^{-x}\geq (1-e^{-1})x$ to get
\[
\text{Col}(N,q) \geq \left(1-\frac{1}{e}\right)\cdot \frac{q(q-1)}{2N}.
\]
A computation of the constant here completes the proof. Therefore
\[
\text{Col}(N,q)=c\cdot\frac{q^2}{N}
\]
for $1 \geq c \geq 0.3$ and 
\[
\text{Col}(N,q)=\Theta\left(\frac{q^2}{N}\right).
\]
}

\end{problemparts}

\end{problem}
\fi

\iffalse
\begin{problem}
A number $m$ between 0 and 100 is chosen, with all numbers equally likely.
Then $m$ white balls and $100-m$ black balls are placed in an urn.
We draw 20 successive balls from the 100 in the urn, leaving 80
behind.  We're blindfolded and the urn is shaken between draws, so we
assume that all draws of 20 of the 100 balls are equally likely.

Now it turns out that all the balls we draw are white.  What is the
probability that if we draw a 21st ball out of the urn, it will be white
as well?

Bayes' rule tells us that
\[
\prcond{21 \mbox{ white}}{ 20 \mbox{ white}}
  = \frac{\pr{21 \mbox{ white}}}{\pr{20 \mbox{ white}}}.
\]
Therefore the problem reduces finding the probability that if we draw
20 balls out of the bin, we get all white balls; similarly for 21.

In general, suppose we have $n$ balls in the box, and that for any
$m=0,\ldots,n$, the probability that exactly $m$ of these $n$ are white
balls is $1/(n+1)$.  We draw $k$ balls out of the box, what is the
probability that they are all white?  Somewhat surprisingly, we will see
that the answer does not depend on $n$.

To make the computation, we first use the rule for conditional
probability, conditioned on how many white balls there are.  If there are
fewer than $k$ white balls, then the probability of drawing $k$ is 0.
Otherwise,
\[
\pr{k \mbox{ white}}
  = \sum_{m=k}^n \prcond{k \mbox{ white}}
  {m \mbox{ white in the box}}\pr{m \mbox{ white in the box}}.
\]

\bparts

\ppart  Use the previous equation to prove that
\begin {equation}\label{eq:binom}
\pr{k \mbox{ white}} = \sum_{m=k}^n \frac{\dbinom{m}{k}}{\dbinom{n}{k}} 
\cdot \frac{1}{n+1} 
\end {equation}

\solution{

To evaluate the conditional probability, we have to define the sample
space and identify the events we are interested in.  The sample space is
given by the $\binom{n}{k}$ ways of drawing $k$ balls out of the box.  The
events whose probability we want to measure are the $\binom{m}{k}$ choices
of $k$ balls out of the $m$ white ones.

}


\ppart The summation of the binomial coefficients can be evaluated
with the following result.
\begin{lemma*} For any $k$ and $n$ such that $n \geq k \geq 0$,
\[
\sum_{m=k}^n  \binom{m}{k} = \binom{n+1}{k+1}.
\]
\end {lemma*}

Give a combinatorial argument that proves the Lemma.  \hint Classify
subsets of $k+1$ elements from $\set{1,\dots, n+1}$ by their maximum
element.

\solution{

Combinatorial argument:

\begin{proof}

We know the righthand side of the equation is the number of ways to choose $k+1$
elements from $\set{1,\dots, n+1}$.

For any such subset, the maximum element $m+1$ must satisfy $k+1 \leq m+ 1
\leq n+1$.  For each $m \in \set{k,\dots,n}$, there are $\binom{m}{k}$
subsets of $k+1$ elements from $\set{1,\dots, m+1}$ whose
maximum element is $m+1$.  So the lefthand side of the equation also counts the
number of such subsets.

\end{proof}

For the record, here's an algebraic proof:

\begin {proof}
We prove the lemma by induction on $n$.

{\em Base Case:} $n=0$. Then also $k=0$ and the statement
of the lemma simplifies to
\[ \binom{0}{0} = \binom{1}{1} \]
which is true.

{\em Inductive Step:}  We distinguish two cases.
If $n=k$ then the statement of the lemma simplifies to
\[ \binom{n}{n} = \binom{n+1}{n+1} \]
which is true. Otherwise, we proceed as follows:
\begin{align*}
\binom{n+1}{k+1}  = & \binom{n}{k} + \binom{n}{k+1} & \mbox{(Pascal's equality)}\\
 = & \binom{n}{k} +  \sum_{m=k}^{n-1}  \binom{m}{k} & 
\mbox{(induction hypothesis)}\\
 = & \sum_{m=k}^{n}  \binom{m}{k}
\end{align*}
\end {proof}

}

\ppart Conclude that
\[
\pr{\mbox{first 21 all white} \mid \mbox{first 20 all white}}
 = \frac{21}{22},
\]
and more generally, 
\[
\pr{\mbox{first $k+1$ all white} \mid \mbox{first $k$ all white}}
 = \frac{k+1}{k+2},
\]
regardless of the value of $n \geq k+1$.


\solution{
We can now simplify Equation~(\ref{eq:binom}).
\[
\pr{k \mbox{ white}} = \sum_{m=k}^n \frac {\dbinom{m}{k}}{\dbinom{n}{k}} 
\cdot \frac 1 {n+1}  = \frac{\dbinom{n+1}{k+1}}{\dbinom{n}{k}}
 \frac{1}{n+1} = \frac{1}{k+1}.
\]
Notice that the result is independent of $n$ as claimed.

\textbf{Comment}: The answer $(k+1)/(k+2)$ is so simple that it begs for a
simpler argument than we developed above.  However, we haven't been able
to invent one or find one in the literature.

}

\ppart Taking the T to lecture, Ben Bitdiddle has noticed the same person
20 days in a row, and he decides to offer odds of 21 to 1 that he will see
that person again tomorrow.  Is this a fair bet?  Explain?

\solution{

If the person Ben saw for 20 days also got off at Kendall station, carries
an MIT folder, and tomorrow is not a holiday, then we can expect the
chances of Ben seeing the person tomorrow to be higher than 21/22, and we
should reject Ben's bet.  But if it is the last day of lectures, then we
can expect chances to be lower, and we would confidently bet against Ben.
In general such a real-world situation hardly fits the model where all
possible numbers of consecutive successes are \emph{a priori} equally
likely.

Ben's bet is similar to the following argument originally made by LaPlace,
one of the founders of probability theory, who is alleged to have offered
odds of a million to one that the Sun would rise tomorrow based on the
following reasoning:
\begin{quotation}\noindent
The sun has certainly been rising every morning in the last 27 centuries
or so, since otherwise such a remarkable event as the sun not rising would
have been recorded in several places and we would know about that.  This
sums up to about a million days, therefore the chance that the sun is not
going to rise tomorrow is at most $10^{-6}$.
\end{quotation}

Anyone who finds this argument persuasive has a very shaky understanding
of probability, history, and astronomy.  LaPlace's argument supposes that
whether the sun will rise for exactly $k$ days occurs with equal
probability for all known $k$, an unjustified, and implausible assumption.
It also assumes that we know with certainty that the sun has risen for the
past million days, which given the nature of historical records, is no
more likely than the probability of tomorrow's sunrise that we are trying
to estimate in the first place.

}

\eparts

\end{problem}
\fi

\iffalse

\begin{problem}
\begin{theorem*}[Relative Probability]
Let $\sspace$ be a sample space and $\pr{}$ a probability function on
$\sspace$.  Let $C \subseteq \sspace$ be an event such that $\pr{C} \neq
0$.  Define a new probability measure $\prsub{}{C}$ on $\sspace$ by the
rule
\begin{equation}\label{defprc}
\prsub{A}{C} \eqdef \prcond{A}{C}
\end{equation}
for any event $A$.  Then $\prsub{}{C}$ is also a probability function on $\sspace$.
\end{theorem*}
We call $\prsub{}{C}$ the \emph{probability relative to $C$}.

\bparts 

\ppart\label{prsuba} Prove the Relative Probability Theorem. \hint Review
the definition of a probability space in
\hyperref{http://theory.lcs.mit.edu/classes/6.042/fall02/handouts/lectures/ln10.pdf}{ln10}{probsp}
{Notes 10, \S5.1}.

\solution{A probability space is defined to be a sample space $\sspace$
and a probability function $\pr{}$ which satisfies two properties:
\begin{enumerate}
\item $\pr{\sspace} =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\naturals} \pr{A_i}$
converges and
\begin{equation}\tag{Sum Rule}
\pr{A} = \pr{\lgunion_{i\in\naturals}A_i} = \sum_{i\in\naturals} \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{\sspace}{C} &= \prcond{\sspace}{C} & \text{definition~(\ref{defprc}) of $\prsub{}{C}$}\\
             &= \frac{\pr{\sspace \cap C}}{\pr{C}} & \text{definition of $\prcond{\sspace}{C}$}\\
             &= \frac{\pr{C}}{\pr{C}} & \text{since $C \subseteq \sspace$}\\
             &= 1 & \text{since $\pr{C} \neq 0$.}
\end{align*}

\item
The Sum Rule can be verified as follows:

\begin{align*}
\prsub{\lgunion_{i\in\naturals}A_i}{C}
    &= \pr{\lgunion_{i\in\naturals}A_i \biggm| C} &
          \text{definition~(\ref{defprc}) of $\prsub{}{C}$}\\\\
    &= \frac{\pr{(\lgunion_{i\in\naturals}A_i) \cap C}}{\pr{C}} &
           \text{definition of $\prcond{\cdot}{C}$}\\
    &= \frac{\pr{\lgunion_{i\in\naturals}(A_i \cap C)}}{\pr{C}}&
             \text{distributive law}\\
    &= \sum_{i \in \naturals} \frac{\pr{A_i \cap C}}{\pr{C}} & \text{Sum Rule}\\
    &=  \sum_{i \in \naturals} {\prcond{A_i}{C}} &
           \text{definition of $\prcond{\cdot}{C}$}\\\\
    &= \sum_{i \in \naturals} {\prsub{A_i}{C}}&
          \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).

\solution{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~(\ref{prsuba}), 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

\end{problem}
\fi

\iffalse

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

\solution{
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.

\solution{ $\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.

\solution{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
\end{problem}
\fi


\end{document}
