Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Random walk on integers with two absorbing boundaries

  1. Mar 22, 2009 #1
    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.
     
  2. jcsd
  3. Mar 22, 2009 #2

    mathman

    User Avatar
    Science Advisor
    Gold Member

    In a classic text by William Feller "An Introduction to Probability Theory and its Application", this problem is discussed in full detail.
     
  4. Mar 25, 2009 #3
    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
     
  5. Mar 25, 2009 #4
    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 [itex]x_i=\mathbb{P}_i(T_a<\infty)[/itex] where [itex]T_a=\inf\{n:X_n=a\}[/itex]. So obvious if it hits b then T_a is infinite. The one step method is
    [tex]x_i=p_{i,i+1}x_{i+1}+p_{i,i-1}x_{i-1}[/tex]
    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
    [tex]\displaystyle x_i=x_0+\sum_{n=0}^{i-1}(x_{n+1}-x_n)[/tex]

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

    Hope this helps.
     
  6. Mar 25, 2009 #5
    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
     
  7. Mar 25, 2009 #6
    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 [itex]x_a=1\quad x_b=0[/itex].

    If you want to know the [itex]\mathbb{P}_i(T_a=k)[/itex] then you have to condition your way backwards
    [tex]\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})=...[/tex]

    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.
     
  8. Mar 26, 2009 #7
    Hi Focus, that is very helpful. thanks again.
    -m
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Random walk on integers with two absorbing boundaries
  1. Random Walk (Replies: 2)

  2. Random walk (Replies: 2)

Loading...