
\instatements{\newpage}

\begin{examproblem}{15}  %Eric F03

There are 300 different episodes of the television program {\em Law
and Order}, of which 50 are {\em really great} and 250 are {\em pretty
good}.  One episode is rerun each night.  Assume that this episode is
selected uniformly at random, independent of all preceding episodes.

\bparts

\ppart[3] What is the expected number of episodes you will watch until you
see one really-great episode?

\solution[\vspace{3.5in}]{The probability of seeing a really-great
episode is $50/300 = 1/6$.  By the mean-time-to-success formula, the
expected number of episodes I must watch is 6.}

\ppart[6] Suppose that I've seen $k$ of the really-great episodes where $0
\leq k < 50$.  What is the expected number of additional episodes I must
watch in order to see a really-great episode I have not seen yet?

\solution{The probability of seeing a new really-great episode is $(50
- k)/300$.  Therefore, the expected number is $300 / (50 - k)$.}

\instatements{\newpage}


\ppart[6] What is the expected number of episodes that I must watch in
order to see {\em all} of the really-great episodes?  Your answer should
be a closed-form expression involving the $n$th Harmonic number,
\[
H_n \eqdef \frac{1}{1} + \frac{1}{2} + \ldots + \frac{1}{n}.
\]

\solution{By linearity of expectation, the answer is the expected time
to see the first really-great episode, plus the expected time to see
the second, and so forth:

\begin{eqnarray*}
\frac{300}{50} + \frac{300}{49} + \frac{300}{48} + \ldots + \frac{300}{1}
    & = & 300 H_{50}
\end{eqnarray*}
}

\eparts

\end{examproblem}

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

\iffalse

\instatements{\newpage}

\begin{examproblem}{15}   %Eric F03

There are twelve students in Nancy Plimpton's third-grade class,
including the terrifying Snivelson triplets.  There are twelve desks
in the classroom, arranged like this:

\[
\begin{array}{cccc}
\fbox{A} & \fbox{B} & \fbox{B} & \fbox{A} \\ \\
\fbox{B} & \fbox{C} & \fbox{C} & \fbox{B} \\ \\
\fbox{A} & \fbox{B} & \fbox{B} & \fbox{A}
\end{array}
\]

The teacher will select an assignment of students to desks uniformly
at random.  Two students are considered {\em next to} each other if
one is immediately left, right, behind, or in front of the other.  For
example, each student in a desk marked B is next to exactly three
other students.

Let the random variable $S$ be the number of Snivelsons that sit next
to Nancy.  Let $A$ be the event that Nancy is assigned to an $A$ desk,
$B$ be the event that she is assigned to a $B$ desk, and $C$ be the
event that she is assigned to a C desk.

\bparts

\ppart[5] What are $\pr{A}$, $\pr{B}$, and $\pr{C}$?

\solution{
}

\instatements{\newpage}

\ppart[5] What are $\expect{S \mid A}$, $\expect{S \mid B}$, and
$\expect{S \mid C}$?

\solution[\vspace{3.5in}]{
}

\ppart[5] What is the expected number of Snivelsons that will sit next
to Nancy?

\solution{
}

\eparts

\end{examproblem}
\fi


\iffalse

\instatements{\newpage}


\begin{examproblem}{15}   %Eric F03

Stinky Peterson is taking 7.393 ({\em The Evolution of Nasty, Crawly
Things}).  The final exam is structured as follows:

\begin{itemize}

\item The professor distributes a list of 12 questions two weeks
before the exam, so that students can prepare answers in advance.

\item The professor selects 4 of these questions uniformly at random
and puts them on the final exam.

\item Each student must answer 2 of the questions on the exam.

\end{itemize}

Stinky notes that each possible outcome of the exam-creation process
corresponds to a 12-bit sequence $(b_1, b_2, \ldots, b_{12})$ that has
exactly 4 ones.  In particular, $b_i = 1$ if the $i$th question is on
the exam and $b_i = 0$ if the $i$th question is not on the exam.

\bparts

\ppart[3] How many different final exams are possible?

\solution[\vspace{3in}]{This is the number of 12-bit sequences with
exactly 4 ones, which is $\binom{12}{4}$.}

\instatements{\newpage}

\ppart[3] Stinky has time to prepare answers to only the first 5
questions in advance.  Let $E$ be the event that the final contains
{\em exactly} 2 of the questions Stinky prepared.  Describe all
outcomes in the event $E$ in terms of bit sequences.

\solution[\vspace{3.5in}]{The event $E$ contains all 12-bit sequences
with exactly 2 ones in the first 5 positions.}

\ppart[3] What is $\pr{E}$?

\solution{The number of outcomes in $E$ is $\binom{5}{2} \cdot
\binom{7}{2}$ since we must put 2 ones in the first 5 positions and 2
ones in the last 7 positions.  Since all outcomes are equally likely,
we have:

\begin{eqnarray*}
\pr{E} & = & \frac{\binom{5}{2} \cdot \binom{7}{2}}{\binom{12}{4}}
\end{eqnarray*}
}

\instatements{\newpage}

\ppart[3] Let $F$ be the event that the final contains {\em at least}
2 of the questions Stinky prepared.  Describe all outcomes in event
$F$.

\solution[\vspace{3.5in}]{The event $F$ contains all sequences with 2,
3, or 4 ones in the first 7 positions.}

\ppart[3] What is $\pr{F}$?

\solution{
Reasoning as before, we get:

\begin{eqnarray*}
\pr{F} & = &
\frac{
\binom{5}{2} \cdot \binom{7}{2} +
\binom{5}{3} \cdot \binom{7}{1} +
\binom{5}{4} \cdot \binom{7}{0}}{\binom{12}{4}}
\end{eqnarray*}
}

\eparts

\end{examproblem}
\fi

\instatements{\newpage}

\begin{examproblem}{10}  %S02 Final & spring99 final problem 7

We consider a hypothetical Institute with only two departments: EECS
and Math, and consider the experiment where we pick a random applicant
for admission to one of these departments.  Define the following
events:
\begin{eqnarray*}
A & \eqdef & \text{applicant is accepted,}\\
F & \eqdef & \text{applicant is female,}\\
M & \eqdef &  \text{applicant is male,}\\
\mathit{MATH} & \eqdef & \text{applicant applied to Math,}\\
\mathit{EECS} & \eqdef & \text{applicant applied to EECS.}
\end{eqnarray*}
Assume that all applicants are either male or female, and that no
applicant applied to both departments.
\iffalse
That is, the events $F_{EECS}$,
$F_{CS}$, $\mbox{M-EECS}$, and $\mbox{M-CS}$ are all disjoint.
\fi

\begin{problemparts}

\problempart[5] The Institute is sued for gender discrimination, with
the plaintiff observing that in both EECS and Math, the probability that a
woman is accepted is less than the probability that a man is accepted.
This observation can be precisely expressed with two inequalities
between conditional probabilities involving the events above.  State these
inequalities.

\solution[\vspace*{5cm}]{
\begin{eqnarray*}
\pr{A \mid F \intersect \mathit{EECS}} & < & \pr{A \mid M \intersect \mathit{EECS}}, \\
\pr{A \mid F \intersect \mathit{MATH}} & < & \pr{A \mid M \intersect \mathit{MATH}}.
\end{eqnarray*}
}

\problempart[5] The Institute's defense attorneys retort that overall among
all applicants, a woman is {\em more} likely to be accepted than a man.
Express this observation as an inequality between conditional probabilities
involving the events above.

\solution[\vspace*{4cm}]{
\begin{eqnarray*}
\pr{A \mid F} & > & \pr{A \mid M}
\end{eqnarray*}
}

\iffalse
\problempart Although the assertions above may appear to be logically
inconsistent, both the plaintiff's and the defense's claims about the
conditional probabilities can be correct. (Never mind whose interpretation
of the data we find more persuasive.)  Fill in the missing table entries
below with possible applicant statistics for which both the plaintiff and
the University attorneys' assertions are true.

\begin{center}
\renewcommand{\arraystretch}{.3}
\begin{tabular}{|c|c|c|c|}
\hline
& &\hspace*{1in}&\\
     & Applied & Accepted & percent accepted\\
 & & & \\ \hline \hline & & &\\
Dept & Females & Females &  Females\\
& & & \\ \hline & & &\\
Math & & & \\ & & & \\ \hline & & &\\
EECS & 100 & 70 & 70\% \\ & & & \\ \hline & & &\\
Total & &  & \\ & & &\\ \hline \hline & & &\\
Dept & Males & Males & Males\\
& & & \\ \hline & & &\\
Math & 100 & 50 & 50\% \\ & & & \\ \hline & & &\\
EECS & & & \\ & & & \\ \hline & & &\\
Total & &  & \\
& & &\\
\hline
\end{tabular}
\end{center}

\solution{
\[
\begin{array}{ccr}
\mbox{CS} & \mbox{0 females accepted, 1 applied} & 0\% \\
          & \mbox{50 males accepted, 100 applied} & 50\% \\
\mbox{EECS} & \mbox{70 females accepted, 100 applied} & 70\% \\
          & \mbox{1 male accepted, 1 applied} & 100\% \\
\hline
\mbox{Overall} & \mbox{70 females accepted, 101 applied} & \approx 70\% \\
          & \mbox{51 males accepted, 101 applied} & \approx 51\%
\end{array}
\]
}
\fi
\end{problemparts}

\end{examproblem}

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

\iffalse
\begin{examproblem}{20}   %F01 final

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 \emph{stick} with his original choice of door or
\emph{switch} to the other unopened door.  He wins if the prize is behind
the door he finally chooses.

To analyze this setup, we 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[3]  What is $\pr{GP}$? \brule{0.5in}.  $\prcond{OP}{\bar{GP}}$?\brule{0.5in}.
\solution{1/3,1/2}

\ppart[2] What is $\pr{OP}$? \brule{0.5in}
\solution[\vspace{0.7in}]{\[
\prcond{OP}{GP}\pr{GP} + \prcond{OP}{\bar{GP}}\pr{\bar{GP}} = 0\cdot 1/3 +
1/2 \cdot 2/3 = 1/3.
\]
}

\ppart[2] 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[\vspace{0.7in}]{
$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$.}

\ppart[1] What is the probability the game will continue forever?\brule{0.5in}

\solution{0.  In terms of the previous problem part, this is the
probability of \emph{never} failing.}

\ppart[6] When Carol finally picks the goat, the contestant has the choice of
sticking or switching.  Let's say that the contestant adopts the strategy
of sticking.  Let $W$ be the event that the contestant wins with this
strategy, and let $w \eqdef \pr{W}$.  Express the following conditional
probabilities as simple closed forms in terms of $w$.
\begin{enumerate}
\renewcommand{\labelenumi}{\roman{enumi})}

\item $\prcond{W}{GP} = $ \brule{0.5in}
\solution{1}

\item $\prcond{W}{\bar{GP}\intersect OP} = $ \brule{0.5in}
\solution{$w$}

\item $\prcond{W}{\bar{GP}\intersect \bar{OP}} = $ \brule{0.5in}
\solution{0}
\end{enumerate}

\ppart[3] What is $\pr{W}$? \brule{0.5in}

\solution[\vspace{2in}]
{1/2, because
\[\begin{array}{rcll}
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}}\\
  & = & 1 \cdot 1/3 & +\ w \cdot 2/3 \cdot 1/2 + 0 \cdot 2/3 \cdot 1/2\\
  & = & 1/3 + w/3.
\end{array}\]
So $w(1- 1/3) = 1/3$.}

\ppart[3] 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[\vspace{4in}]
{Switching strategies turns wins to losses for \emph{terminated}
games.  So the probability of win with switch is $t-\pr{W}$ where $t$ is
the probability of termination.  In original Monty Hall, the game obviously
terminated 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{examproblem}
\fi

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


\instatements{\newpage}

\begin{examproblem}{15}
Two factories produce the same product.  The number, $R$, of items
produced per day by the first factory fluctuates randomly with mean 80 and
standard deviation 2.  The number, $T$, of items produced per day by the
second factory fluctuates independently of the first factory's output, and
$T$ is observed to have mean 90 and standard deviation 3.  \iffalse Use
the Chebychev Bound to\fi Show that there is at least a 96\% chance that
tomorrow, the excess output of the second factory over the first factory
will differ from what it is expected to be by less than a factor of two.

\solution{
Let $D \eqdef T-R$ be the excess output in a day.  So
\begin{align}
\expect{D} & = \expect{T} - \expect{R} = 90-80=10,\label{E}\\
\variance{D} & = \variance{T} + \variance{R} = 2^2+3^2=13,\label{V}\\
\pr{\abs{D-\expect{D}} \geq 2\expect{D}} & \leq \frac{13}{20^2}
&\text{(by~(\ref{E}), (\ref{V}) \& Chebychev)},\notag\\
\pr{\abs{D-\expect{D}} <  2\expect{D}} & \geq 1 - \frac{13}{20^2} =
   \frac{387}{400} > 0.96. \notag
\end{align}
}

\end{examproblem}
