0

I have a random walk at position i that goes to i+2 with probability 1/2 and goes to i-1 with probability 1/2. We start at position 0 and are absorbed by position -1. What is the probability of being absorbed in an infinite random walk?

I am trying to solve this by thinking about recurrence relationships where

$$f(x) = \frac{1}{2} f(x-1) + \frac{1}{2} f(x+2)$$ and $$f(-1) = 1$$

But I haven't gotten anywhere. Can anyone provide insight?

Jason
  • 149

1 Answers1

1

Are you familiar with the standard method of solving linear recurrences with constant coefficients? You can write your equation as $$f(n+2)-2f(n)+f(n-1)=0\ ,$$ and the usual method applies. In this case you will have a cubic characteristic equation, but one of the roots will be clear if you look closely.

You will need conditions in order to determine the unknown constants in your solution. The value of $f(-1)$ should be obvious, also consider what happens when $n\to\infty$.

If you have not studied this topic just ask Google, there will be many explanations online.

David
  • 82,662
  • Hi - not sure what you mean by one of the roots should be clear? It's unclear to me how I can intuit roots in a recursive equation without knowing the generating function. Can you offer some guidelines while I follow up on your other suggestions? – Jason Sep 01 '22 at 05:41
  • 1
    Look up the characteristic equation if you don't already know about it. That is where one of the roots should be clear. – David Sep 01 '22 at 05:50