Time before visit number one, random walk

[Paalfaal]

Hi there!

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ⁱ
P_i,i+1 = pⁱ
i \in[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₀ = n₀}

The problem to be calculated is:

P(N \geq 1000).
for n₀ = 0
and n₀ = 10




My thoughts:

P(N \geq 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 \geq 1000) ≈ 1 - Ʃ_k=1⁹⁹⁸ P_i,14^kP_14,15
= 1 - P_14,15Ʃ_k=1⁹⁹⁸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₀



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

 

[bpet]

If you make X=15 an absorbing state, you could write the solution in terms of powers of a 16 by 16 matrix.

 

[Paalfaal]

If you make X=15 an absorbing state, you could write the solution in terms of powers of a 16 by 16 matrix.

Of course! Thank you very much