# Time before visit number one, random walk

1. Oct 13, 2012

### Paalfaal

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 $\in$[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 $\geq$ 1000).
for n0 = 0
and n0 = 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 Pi,i+1 gets so small for large i the answer can be approximated to:
P(N $\geq$ 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. Oct 14, 2012

### bpet

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

3. Oct 14, 2012

### Paalfaal

Of course! Thank you very much