- #1
Paalfaal
- 13
- 0
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
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: