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

Time before visit number one, random walk

  1. Oct 13, 2012 #1
    Hi there!

    I'm working on a random walk-problem my professor gave me.

    Given a MC with the following properties:
    P0,0 = 1 - p
    P0,1 = p
    Pi,i-1 = 1 - pi
    Pi,i+1 = pi
    i [itex]\in[/itex][1,∞)
    Xn: state at step number n

    The chain is irreducible and ergodic and 0 < p ≤ 1

    introducing N:
    N = {min n > 0 : Xn = 15 | X0 = n0}

    The problem to be calculated is:

    P(N [itex]\geq[/itex] 1000).
    for n0 = 0
    and n0 = 10

    My thoughts:

    P(N [itex]\geq[/itex] 1000) = 1 - P(N < 1000) = 1 - [P(N = 999) + P(N = 998) + ...]

    Now here's where it gets tricky (I think). It is very hard to determine an exact solution sice the markov property causes the chain to 'forget' if it has been to a state before. That is, we don't know if it's the first time we visit a state when we visit a state (correct me if i'm wrong here, but there is no 'easy' way to solve this problem).

    By 'calculate' I wonder if he really means 'approximate'. Since Pi,i+1 gets so small for large i the answer can be approximated to:
    P(N [itex]\geq[/itex] 1000) ≈ 1 - Ʃk=1998 Pi,14kP14,15
    = 1 - P14,15Ʃk=1998Pi,14k
    (don't worry about my summation shenanigans. matlab can solve this for me)
    Obviously this approximation can only be good for realtively small p, and n0

    I really want your thoughts on this problem. Are there any solutions that are more 'correct' than mine? Thank you
    Last edited: Oct 13, 2012
  2. jcsd
  3. Oct 14, 2012 #2
    If you make X=15 an absorbing state, you could write the solution in terms of powers of a 16 by 16 matrix.
  4. Oct 14, 2012 #3
    Of course! Thank you very much :smile:
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook