Random Walk ProblemDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/