Hi there!(adsbygoogle = window.adsbygoogle || []).push({});

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

Given a MC with the following properties:

P_{0,0}= 1 - p

P_{0,1}= p

P_{i,i-1}= 1 - p^{i}

P_{i,i+1}= p^{i}

i [itex]\in[/itex][1,∞)

X_{n}: state at step number n

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

introducing N:

N = {min n > 0 : X_{n}= 15 | X_{0}= n_{0}}

The problem to be calculated is:

P(N [itex]\geq[/itex] 1000).

for n_{0}= 0

and n_{0}= 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 P_{i,i+1}gets so small for large i the answer can be approximated to:

P(N [itex]\geq[/itex] 1000) ≈ 1 - Ʃ_{k=1}^{998}P_{i,14}^{k}P_{14,15}

= 1 - P_{14,15}Ʃ_{k=1}^{998}P_{i,14}^{k}

(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 n_{0}

I really want your thoughts on this problem. Are there any solutions that are more 'correct' than mine? Thank you

**Physics Forums | Science Articles, Homework Help, Discussion**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Time before visit number one, random walk

**Physics Forums | Science Articles, Homework Help, Discussion**