\problemdata      
        {?} % latex-friendly label for the prob.
        {Probability-Expectation} % The topic(s) of the problem content.
        {?} % Source (if known)
        {F01, PS12; F98, Tu12; F95, Tu10} % Usage (list ones you are aware of).
        {Christos Kapoutsis, S02} % Last revision info (author, date).



\begin{problem}
{\bf Lost in Infinite Corridors}
A distressed Harvard student, lost in the underground corridors of MIT, finds
himself in a room containing three doors.  Door 1 leads him to freedom
(out of MIT) after one hour of travel; door 2 returns him to the same
room after four hours travel, and door 3 returns him to the room after
seven hours travel.  Each time he finds himself in the room, the confused and memory-less
Harvard student picks a door with equal probability.
Let $T$ denote the time until he finds the exit.
\bparts

\ppart Let T be the total number of hours before he finds 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{
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$.
}


\iffalse
\ppart Is $R_k$ independent of the event that $Q\geq k$?
Is $R_k$ independent of $Q$?

\solution{
$R_i$ is \emph{not} independent of $Q$.  For
example, if $Q=i$, then it must be that the student found the escape door
at the $i$th step, and so $\pr{R_i = 1 | Q=i} =1 \neq 1/3 = \pr{R_i = 1}$.

However, suppose we are given that the student has never managed to escape
before the $i$th step, that is, that $Q \ge i$.  Then we can observe that
the experiment starting at the $i$th step has exactly the same structure
as the experiment at the first step---where we were given, implicitly,
that the student had not escaped before the first step.  So we can
conclude that the distribution of $R_i$ given $Q \ge i$ is the same as
that of $R_1$ given that $Q\ge 1$, that is, the same as $R_1$, which we
already observed is the same as $R_i$.  In other words, $R_i$ is
independent of the event that $Q \geq i$, as required.
}
\fi


\ppart 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.\]
}


\ppart Now suppose that an MIT student is also lost and finds herself in a 
similar situation to the Harvard student.  Of course, the MIT student never chooses the 
same door twice.  What is $\expect{T}$ for the MIT student?

\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$.
}
\eparts


\end{problem}