\problemdata
{expectation}
{wald's theorem}
{S98 pset 11}
{Eric Ho S02}
\begin{problem}

The Fellowship of the Ring is lost in the underground mines of Moira.
They find themselves in a chamber containing three doors.  Door 1
leads them to freedom after one hour of travel; door 2 returns them to
the same room after four hours travel, and door 3 returns them to the
room after seven hours travel. Each time they find themselves in the
room, they pick a door with equal probability.

\begin{problemparts}

\problempart Let $T$ be the total number of hours before they find the
exit.  Define a sequence of independent identically distributed random
variables $R_i$ and a stopping time $Q$ such that

\begin{displaymath}
T = \sum_{i=1}^{Q}{R_i}
\end{displaymath}

\solution{FIX SOLUTION We view this an experiment where at each step
the student makes a choice between three equally likely outcomes.  We
define $R_i$ as the number of hours to return to the same room, or to
escape, starting at the $i$th step.  The experiment does not end.
That is, as soon as the student escapes, he is doomed, like Sisyphus,
to be stuck back in the room and start trying to escape again.  This
ensures that there is an $i$th step for all $i \ge 0$, and that the
$R_i$ are identically distributed (they are also independent, though
this fact is not needed in applying Wald's Theorem).  In particular,
$\pr{R_i=1}=\pr{R_i=4}=\pr{R_i =7}=1/3$, and $\expect{R_i} =
(1+4+7)/3=4$.

Define $Q$ to be the number of steps from the first step until the escape
door is selected \emph{for the first time}.  Now $Q$ is geometrically
distributed with probability $1/3$ and $\expect{Q}=3$.
}


\problempart Use Wald's Theorem to find $\expect{T}$.

\solution{
Since Wald's Theorem is applicable, we conclude
\[\expect{T} = \expect{\sum_{i=1}^Q R_i}  = 3 \times 4 = 12.\]
}


\problempart Gandalf decides to take over, and he never chooses the
same door twice.  What is $\expect{T}$ now?

\solution{ The problem can be solved by complete enumeration; call $A$
the door that leads out, $B$ the door that leads back in four hours,
and $C$ the door that leads back in seven hours. The possible events
are

\begin {itemize}

\item
$A$ with probability $1/3$, in which case $T=1$

\item
$BA$ with probability $\frac 12 \cdot \frac 13 = \frac 16$, in which
case $T=5$;

\item
$BCA$ with probability $\frac 12 \cdot \frac 13 \cdot 1 = \frac 16$,
in which case $T=12$;

\item
$CA$ with probability $\frac 12 \cdot \frac 13  = \frac 16$, in which case $T=8$;

\item
$CBA$ with probability $\frac 12 \cdot \frac 13 \cdot 1 = \frac 16$, in which
case $T=12$.

\end {itemize}

The average of $T$ this time is $\expect{T} = 39/6 = 6.5$.
}
\end{problemparts}
\end{problem}

