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

\usepackage{amsmath}
\usepackage{latexsym}
\usepackage{graphics}
\usepackage{amsfonts}
\usepackage{amssymb}

\addtolength{\textheight}{.05in}

\begin{document}

\pset{10}{May 6, 2003}{To your tutor on Friday, May 9}

%\newcommand{\solution}[1]{}                          % hide solutions
\newcommand{\solution}[1]{\textbf{Solution.} #1}    % show solution

\newcommand{\beqn}{\begin{eqnarray*}}
\newcommand{\eeqn}{\end{eqnarray*}}
\newcommand{\ex}[1]{\text{Ex} \left[ #1 \right] }
\newcommand{\pr}[1]{\text{Pr} \left\{ #1 \right\} }

\begin{problems}

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

\problem Suppose that we roll $n$ six-sided dice that are fair and
independent.  Compute the expected value of the highest roll.  You
might find the following fact from lecture helpful: for a random
variable $X$ that takes on values in $\mathbb{N}$:

\beqn
\ex{X} & = & \sum_{k=0}^{\infty} \pr{X > k}
\eeqn

\solution{Let $X_1, \ldots, X_n$ be the individual die rolls, and
define:

\beqn
X & = & \max(X_1, \ldots, X_n)
\eeqn

Our goal is to evaluate:

\beqn
\ex{X}	& = &	\sum_{k=0}^{\infty} \pr{X > k} \\
	& = &	\sum_{k=0}^{5} \pr{X > k}
\eeqn

The infinite sum is equal to the finite sum, because the highest roll
can not possibly be greater than 6; thus, all later terms are zero.
All that remains is to compute $\pr{X > k}$, which we can do as
follows:

\beqn
\pr{X > k}
	& = &	1 - \pr{X \leq k} \\
	& = &	1 - \pr{X_1 \leq k \cap \ldots \cap X_n \leq k} \\
	& = &	1 - \pr{X_1 \leq k} \cdot \ldots \cdot \pr{X_n \leq k} \\
	& = &	1 - \pr{X_1 \leq k}^n \\
	& = &	1 - \left(\frac{k}{6}\right)^n
\eeqn

In the first step, we switch to analyzing the complementary event.
Next, we observe the highest roll is less than or equal to $k$ if and
only if every individual roll is less than or equal to $k$.  The third
step uses independence, and the final step uses the fact that each
roll has an equal probability of being less than or equal to $k$.  The
final step is valid for integral $k$ between 0 and 6.

Substituting this result into the expectation formula gives:

\beqn
\ex{X}	& = &	\sum_{k=0}^{5} \pr{X > k} \\
	& = &	\sum_{k=0}^{5} \left(1 - \left(\frac{k}{6}\right)^n\right) \\
	& = &	6 - \frac{1^n + 2^n + 3^n + 4^n + 5^n}{6^n}
\eeqn
}

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

\problem The starship {\em Almost Invincible} is cruising across the
galaxy.  Each day, there is a 1 in 80 chance that the ship is blown up
by Arcturian raiders, a 1 in 300 chance that it is eaten by a giant
spaceworm, and 1 in 2000 chance that it is sucked into a black hole.
Assume that these events are independent.  What is the expected
duration of the {\em Almost Invincible}'s cruise?

\solution{
Each day, the ship is destroyed with probability:

\beqn
1 -
\left(1 - \frac{1}{80}\right) \cdot
\left(1 - \frac{1}{300}\right) \cdot
\left(1 - \frac{1}{2000}\right)
    & = & \frac{781621}{48000000} \\
\eeqn

Therefore, the expected time until the ship is destroyed is:

\beqn
\frac{48000000}{781621} & \approx & 61.41 \text{ days}
\eeqn
}

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

\problem For some MIT students, undergraduate life is a continuing
struggle against a creature in the closet known as the {\em Dirty
Clothes Monster}.  Each term, the monster either is {\em under
control} or else is {\em out of control}.  When a student first
arrives at MIT, the monster is under control.  Thereafter, the
struggle proceeds as follows:

If the monster is under control in a given term, then:

\begin{itemize}

\item With probability $\frac{6}{10}$, the monster is under control
the next term.

\item With probability $\frac{3}{10}$, the monster is out of control
the next term.

\item With probability $\frac{1}{10}$, the student wins the struggle
by graduating.

\end{itemize}

If the monster is out of control in a given term, then:

\begin{itemize}

\item With probability $\frac{7}{10}$, the monster is out of control
the next term.

\item With probability $\frac{2}{10}$, the monster is under control
the next term.

\item With probability $\frac{1}{10}$, the student is never heard from
again.

\end{itemize}

Let's analyze the prospects of such a student.

\begin{problemparts}

\problempart Draw a tree diagram deep enough so that you understand
the overall structure of the tree.  Mark each vertex either $X$ or $Y$
according to whether the monster is under control ($X$) or out of
control ($Y$).

\solution{

\bigskip
\centerline{\resizebox{5.5in}{!}{\includegraphics{pset10-tree.eps}}}
\bigskip

All the $X$ nodes are roots of identical subtrees, and all the $Y$
nodes are roots of identical subtrees.}

\problempart Let $X$ be the probability that the student eventually
wins, given that the monster is currently under control.  Let $Y$ be
the probability that the student eventually wins, given that the
monster is currently out of control.  Obtain two equations from your
tree diagram, one expressing $X$ in terms of $X$ and $Y$ and one
expressing $Y$ in terms of $X$ and $Y$.

\solution{
\beqn
X & = & \frac{1}{10} + \frac{6}{10} X + \frac{3}{10} Y \\
Y & = & \frac{2}{10} X + \frac{7}{10} Y 
\eeqn
}

\problempart Solve the two equations you obtained.  What is the
probability that a newly-arrived MIT student ultimately triumphs over
the Dirty Clothes Monster?

\solution{The solution to the equations is $X = \frac{1}{2}$ and $Y =
\frac{1}{3}$.  Therefore, the student survives with probability
$\frac{1}{2}$.}

\end{problemparts}

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

\end{problems} \end{document}
