Random Walk Problem

Date: 04/10/2006 at 14:37:06
From: Julia
Subject: logic

Dorothy stands on the edge of a cliff: an infinite expanse of land is 
behind her.  Taking one step forward would send her to her doom, 
whereas one step back would be a step toward safety.  All of Dorothy's 
steps are precisely one foot long.  Dorothy has agreed to let her fate 
be determined by the flip of a coin.  She will take one step forward 
if the result of a toss is heads, one step back if it is tails.  If 
she survives the first toss, she is willing to do it again, and again, 
and again, stepping forward and back one foot according to the toss of 
the coin.  After an infinite number of tosses she hopes to be 
wandering off into the infinite expanse behind her.  What are 
Dorothy's chances of survival?

Date: 04/11/2006 at 17:57:23
From: Doctor Vogler
Subject: Re: logic

Hi Julia,

Thanks for writing to Dr. Math.  This kind of problem is called a
"random walk."  There has been a lot of study on the subject, and you
could learn about it by searching for that phrase.  In any case, I
would recommend setting

  f(n) = probability that Dorothy will not fall off the cliff if she
is standing n steps away from falling.

For example, you want to calculate f(1), the probability that she
won't fall when she is standing only one step away from falling.  Then
you can write a recurrence relation for f(n).  Particularly, since she
has a 50% chance of moving closer to the cliff, and a 50% chance of
moving farther away, then for n > 1, you should get

  f(n) = (1/2)*f(n-1) + (1/2)*f(n+1).

So the next step is to solve this recurrence relation.  Well, if you write

  g(n) = f(n) - f(n-1),

then you'll find that the other equation is equivalent to

  g(n+1) = g(n),

which means that

  g(n) = f(n) - f(n-1)

is a constant, say k.  Then

  f(n) = f(n-1) + k

implies that f(n) is an arithmetic sequence, so it has the form

  f(n) = n*k + constant.

Now if you consider f(0), or consider how f(1) should relate to f(2),
you will find that the second constant is zero, so that

  f(n) = n*k.

So what could the constant k possibly be?

Well, if k < 0, then you get negative probabilities, which is
impossible.  So certainly k >= 0.  But if k > 0, then

  f(n) = n*k

will grow to be very large (bigger than 1, in particular) when n gets
very large, which is also impossible, since probabilities must always
be between 0 and 1.  That leaves only one possible choice for k,
namely k = 0.  What does that tell you about poor Dorothy?

If you have any questions about this or need more help, please write
back and show me what you have been able to do, and I will try to
offer further suggestions.

- Doctor Vogler, The Math Forum
  http://mathforum.org/dr.math/