Random walk on integers with two absorbing boundaries

[andrews.mark]

Hi - I am trying to find the probability of hitting one of two boundaries in a simple random walk (I describe the problem precisely below). Actually, my main concern is to find the probability distribution over time to hit either one of two boundaries. I think that this is a very standard problem, i.e. time to ruin in the Gambler's ruin problem, and while I am able to find material describing the probability of hitting one, or other, boundary, I have not been successful in finding any material describing the probability distribution over hitting times. Could anyone help?

many thanks,
Mark

The problem is as follows:
A particle x begins at time t=0, with a value of 0. At each time interval, t=1,2,... it is incremented by 1 with probability p, and decremented by 1 with probability q=1-p. There are two boundaries a>0 and b<0, such that when the particle hits either one it stops. I would like to know 1) the probability that the particle hits a before b and 2) assuming it has hit a (or b), the probability distribution over the time taken to hit it.

 

[mathman]

In a classic text by William Feller "An Introduction to Probability Theory and its Application", this problem is discussed in full detail.

 

[andrews.mark]

Mathman, many thanks! I checked out the book you suggested. It is great. By the way, I also found a book by Cox and Miller on Stochastic processes that is very helpful too.
thank you,
Mark

 

[Focus]

If you want a method for doing these sorts of questions, use the one step method. Define your random walk to be absorbing, i.e. X_n=a implies X_m=a for all m>n. Then define $x_i=\mathbb{P}_i(T_a<\infty)$ where $T_a=\inf\{n:X_n=a\}$. So obvious if it hits b then T_a is infinite. The one step method is
$$x_i=p_{i,i+1}x_{i+1}+p_{i,i-1}x_{i-1}$$
The p s are your transitional probabilities. The equation is intuitive if you think about it.

Now you get a recurrence relation and you need to solve it for x_i, you may find the next identity useful
$$\displaystyle x_i=x_0+\sum_{n=0}^{i-1}(x_{n+1}-x_n)$$

As for the expectation its almost exactly the same, let $y_i=\mathbb{E}_i[T_a]$, then you get the relation
$$y_i=1+p_{i,i+1}y_{i+1}+p_{i,i-1}y_{i-1}$$
You get a 1 there because every time you move to a new state you increase the time by one.

Hope this helps.

 

[andrews.mark]

Hi Focus. Thanks for the advice. Very helpful indeed.
But what exactly does x_i mean? I presume it is the probability of a particle hitting barrier "a" having started at position i. I am inferring that on the basis of the difference equation. I presume that everything messier when we ask of the probability of hitting barrier "a" at time "t", for t> 1.
-mark

 

[Focus]

Yes the definition of them may be confusing but it is the probability that you hit a in a finite time given that you start at i. I should have also mention your boundary conditions are $x_a=1\quad x_b=0$.

If you want to know the $\mathbb{P}_i(T_a=k)$ then you have to condition your way backwards
$$\mathbb{P}_i(T_a=k)=\mathbb{P}_i(X_{k-1}=a-1)p_{a-1,a}=\mathbb{P}_i(X_{k-2}=a-2)p_{a-2,a-1}p_{a-1,a}=p_{a-2,a-1}p_{a-1,a}(\mathbb{P}_i(X_{k-3}=a-1)p_{a-1,a-2}+\mathbb{P}_i(X_{k-3}=a-3)p_{a-3,a-2})=...$$

So you look at where you are and you say, how could I get here? Well I could have moved one up or one down. And do the same again and again, then a pattern emerges.

 

[andrews.mark]

Hi Focus, that is very helpful. thanks again.
-m