\documentclass[12pt]{article}
\usepackage{light}

%\hidesolutions
\showsolutions

\newcommand{\naturals}{\mathbb N}
\newcommand{\eqdef}{:=}

\begin{document}

\newcommand{\prsub}[2]{\mathop{\textup{Pr}_{#1}}\nolimits\left(#2\right)}

\recitation{23}{May 11, 2005}


\section{Stencil the flea}

There is a small flea named Stencil.  To his right, there is an
endless flat plateau.  One inch to his left is the Cliff of Doom,
which drops to a raging sea filled with flea-eating monsters.
\begin{center}
\includegraphics{stencil1}
\end{center}
Each second, Stencil hops 1 inch to the right or 1 inch to the left
with equal probability, independent of the direction of all previous
hops.  If he ever lands on the very edge of the cliff, then he teeters
over and falls into the sea.
\begin{center}
\includegraphics{stencil2}
\end{center}
Our job is to analyze the life of Stencil.  Does he have any chance of
avoiding a fatal plunge?  If not, how long will he hop around before
he takes the plunge?

\newpage
\begin{problem}
Let's begin with a simpler problem. Suppose that Stencil is $n$ inches
from the left side of an island $w$ inches across:
%
\begin{center}
\includegraphics{stencil4}
\end{center}
%
In other words, Stencil starts at position $n$, for some $0\leq n\leq
w$ and there are cliffs at positions 0 and $w$. Let $R_n$ be the
probability he falls to the right off the Cliff of Disaster, given
that he starts at position~$n$. 

\bparts
\ppart
What are the values of $R_0$ and $R_n$? When $0<n<w$, can you express
$R_n$ in terms of $R_{n-1}$ and $R_{n+1}$? (Hint: Total Probability!)

\solution[\vspace{2.5cm}]{
If $n=w$, he starts at position $w$ and immediately falls from the
Cliff of Disaster, so $R_w = 1$.  On the other hand, if he starts at
position $0$, then he falls from the Cliff of Doom immediately, so
$R_0 = 0$. 

Now suppose that he stands somewhere in the middle
of the island, so that $0 < n < w$.  Then we can break the analysis
of his fate into two cases based on the direction of his first hop:
%
\begin{itemize}

\item If his first hop is to the left, then he lands at position $n-1$
and eventually falls off the Cliff of Disaster with probability
$R_{n-1}$.

\item On the other hand, if his first hop is to the right, then he
lands at position $n+1$ and eventually falls off the Cliff of Disaster
with probability $R_{n+1}$.

\end{itemize}
%
Therefore, by the Total Probability Theorem, we have:
%
\[
R_n = \frac{1}{2} R_{n-1} + \frac{1}{2} R_{n+1}
\]
}

\ppart
Solve the linear recurrence (you don't see any linear recurrence? talk
to your TA!) to find $R_n$. (There is our usual guide on the last page.)

\solution[\vspace{4cm}]{
We rearrange the terms in the recurrence equation:
%
\[
R_{n+1} = 2 R_n - R_{n-1}
\]
The characteristic equation is:
%
\[
x^2 - 2 x + 1 = 0
\]
%
This equation has a double root at $x = 1$.  There is no inhomogenous
part, so the general solution has the form:
%
\[
R_n = a \cdot 1^n + b \cdot n 1^n = a + b n
\]
%
Substituting in the boundary conditions $R_0 = 0$ and $R_w = 1$ gives
two linear equations:
%
\begin{align*}
0 & = a \\
1 & = a + b w
\end{align*}
%
The solution to this system is $a = 0$, $b = 1 / w$.  Therefore, the
solution to the recurrence is:
%
\[
R_n = n / w
\]}

\ppart
So you know the probability that Stencil falls off the right
side. Can you quickly deduce the probability that he will \dots falls 
off the \textit{left} side? \dots lives on forever?

\solution[\vspace{1cm}]{
We exploit the symmetry of the problem: the probability that he
falls off the \textit{left} side starting at position $n$ is the same
as the probability that he falls of the \textit{right} side starting
at position $w - n$, which is $(w - n) / n$.

This is bad news.  The probability that Stencil eventually falls off
one cliff or the other is:
%
\[
\frac{n}{w} + \frac{w - n}{w} = 1
\]
%
There's no hope!  The probability that he hops around on the island
forever is zero.  }


\ppart
Now let's go back to the original problem, where Stencil is 1 inch
from the left edge of an infinite plateau. What is the probability
that he lives on forever? 

\solution[\vspace{2.5cm}]{
The probability that he eventually
falls into the sea is:
%
\[
\lim_{w \to \infty} \frac{w - 1}{w} = 1
\]
%
Our little friend is doomed!}

\eparts
\end{problem}


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

\newpage
\begin{problem}
By now you must already know the tragic fate that awaits poor little
Stencil the flea. On the bright side, though, Stencil may get to hop
around for a while before he sinks beneath the waves.  Let's find out
how much he is expected to live. We should begin with the simpler
setup as before:
%
\begin{center}
\includegraphics{stencil4}
\end{center}
%
Let $X_n$ be the expected number of hops he takes before falling
off a cliff. 

\bparts
\ppart
What are the values of $X_0$ and $X_w$? If $0<n<w$, can you express
$X_n$ in terms of $X_{n-1}$ and $X_n$? (Hint: Total Expectation!)

\solution[\vspace{1.5cm}]{
If he starts at either edge of the island, then he dies immediately:
%
\begin{align*}
X_0 & = 0 \\
X_w & = 0
\end{align*}
%
If he starts somewhere in the middle of the island ($0 < n < w$), then
we can again break down the analysis into two cases based on his first
hop:
%
\begin{itemize}

\item If his first hop is to the left, then he lands at position $n-1$
and can expect to live for another $X_{n-1}$ steps.

\item If his first hop is to the right, then he lands at position
$n+1$ and his expected lifespan is $X_{n+1}$.

\end{itemize}
%
Thus, by the Total Expectation Theorem and linearity, his expected
lifespan is:
%
\begin{align*}
X_n & = 1 + \frac{1}{2} X_{n-1} + \frac{1}{2} X_{n+1}
\end{align*}
%
The leading $1$ accounts for his first hop.}

\ppart
Now you should solve the recurrence.

\solution[\vspace{5cm}]{
We can rewrite the last line as:
%
\[
X_{n+1} = 2 X_n - X_{n-1} - 2
\]
%
As before, the characteristic equation is:
%
\[
x^2 - 2 x + 1 = 0
\]
%
There is a double-root at 1, so the homogenous solution has the form:
%
\[
X_n = a + b n
\]
%
There's an inhomogenous term, so we also need to find a particular
solution.  Since this term is a constant, we should try a particular
solution of the form $X_n = c$ and then try $X_n = c + d n$ and then
$X_n = c + d n + e n^2$ and so forth.  As it turns out, the first two
possibilities don't work, but the third does.  Substituting in this
guess gives: 
%
\begin{align*}
X_{n+1} & = 2 X_n - X_{n-1} - 2 \\
c + d(n+1) + e(n+1)^2 & = 2 (c + dn + en^2) - (c + d(n-1) + e(n-1)^2) - 2 \\
e & = -1
\end{align*} 
% 
All the $c$ and $d$ terms cancel, so $X_n = c + d n - n^2$ is a
particular solution for all $c$ and $d$.  For simplicity, let's take
$c = d = 0$.  Thus, our particular solution is $X_n = - n^2$.

Adding the homogenous and particular solutions gives the general form
of the solution:
%
\begin{align*}
X_n & = a + b n - n^2
\end{align*}
%
Substituting in the boundary conditions $X_0 = 0$ and $X_w = 0$ gives
two linear equations:
%
\begin{align*}
0 & = a \\
0 & = a + b w - w^2
\end{align*}
%
The solution to this system is $a = 0$ and $b = w$.  Therefore, the
solution to the recurrence equation is:
%
\[
X_n = w n - n^2 = n (w - n)
\]
}

\ppart
Return to the original problem, where Stencil has the Cliff of
Doom 1 inch to his left and an infinite plateau to this right: What
is his expected lifespan there? 

\solution[\vspace{1cm}]{
In this case, his expected lifespan is:
%
\[
\lim_{w \to \infty} 1 (w - 1) = \infty
\]
%
\textit{Yes, Stencil is expected to live forever!}}

\ppart
Compare your answer to the previous part and your
answer to the last part of the previous problem. Anything troublesome?

\solution[\vspace{1cm}]{
So, Stencil is certain to eventually fall off the cliff into
the sea--- but his expected lifespan is infinite!  This sounds almost 
like a contradiction, but both answers are correct!

Here's an informal explanation.  The probability that Stencil falls
from the Cliff of Doom on the $k$-th step is approximately $1 /
k^{3/2}$.  Thus, the probability that he falls eventually is:
%
\[
\pr{\text{falls off cliff}} \approx \sum_{k=1}^{\infty} \frac{1}{k^{3/2}}
\]
%
You can verify by integration that this sum converges.  The exact sum
actually converges to 1.  On the other hand, the expected time until
he falls is:
%
\[
\ex{\text{hops until fall}} \approx \sum_{k=1}^{\infty} k \cdot
\frac{1}{k^{3/2}} = \sum_{k=1}^{\infty} \frac{1}{\sqrt{k}} 
\]
%
And you can verify by integration that this sum diverges.  So our
answers are compatible!}

\eparts
\end{problem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\instatements{
\newpage
\begin{figure}[p]
\input{short_guide.tex}
\end{figure}}


\end{document}
