Printable View
Hi , I'm Drishan(Hi).. new to this forum.. I need a solution to the following problem..
a simple random walk stops when any of the states is visited 3 times.What is the end state probability distribution?
prob(X(n+1)=k+1|X(n)=k)=p and prob(X(n+1)=k-1|X(n)=k)=1-p
Hey Drishan.
What have you tried already?
This model is a simple random walk and can be represented with a transition matrix. However be aware that if you don't place bounds on X(n), then you will be dealing with a model where you can potentially have inifinitely many states (there is a really small possibility that this will indeed happen, but it needs to be taken into account).
Anyway this looks like a homework question, so can you please show us what you have tried and what kinds of things were covered in class please.
Well, this was a problem from an aptitude test taken by Morgan Stanley. I think to end in state k , there are only 3 possibilities after reaching k for the first time, which are
1)k-->k+1-->k-->k+1-->k
2)k-->k+1-->k-->k-1-->k
3)k-->k-1-->k-->k+1-->k, if the state k-1 is visited only once before
and if k-1 is visited before twice the only possible path is
k-->k+1-->k-->k+1-->k
But I can not think any further than this
and yeah, there is no bound on X(n)
Sorry - I see this post is duplicating your post.
Here's what I've reasoned out so far - no guarantees it's frutiful, but perhaps it will help.
Suppose it starts at 0 and terminates at a>=1.
Thus it's reached a 3 times total, and the first coming up from 0 and so including 0 (at least once).
It reached a a first time, then departed, then reached a and departed a 2nd time, and finally reached a a 3rd time, prior to reaching any other point 3 times.
Could it have departed to the left twice? No, because it would've then reached (a-1) 3 times before reaching a. Also, if a>=2, it couldn't have departed to the left by more than 1 step, otherwise (a-1) would've been reached twice first.
Thus it departed to the left at most once, and if a >=2, then only with an immediate return to a (... a-1, a, a-1, a, a+1, ..., a)
Could it have departed to the right twice? Yes, *but*, only if both departures immediately returned to a. If one of its departures to the right had it at some point reaching a+2, then it would've hit (a+1) 3 times before hitting a.
Summary:
Either one departure to left and one departure to the right - and that one left departure is 1 step only if a>=2,
OR two departures to the right, but only if it was exactly this: ... a-1, a, a+1, a, a+1, a (END).
@johnsomeone.. thanks for your response.. that is exactly what I've figured out so far.. but can't think of how to get the probability distribution
Yeah - I'm not sure.
Thinking out loud: I've a suspicion that it might help to think of it in terms of random variables R and L, where
R = number of steps to the right before turn around, given that you're departing to the right.
L = number of steps to the left before turn around, given that you're departing to the left.
Those are both calcuable, and it feels as if the problem could be stated in terms of them.
Some analysis like this maybe?
Let X(n) = the point you're at at step n.
Case: Departs 0 to right. {R = n1} then {L = 1}.
Then terminates if X(m) = n1 in the future (if "coming back").
Effectively creates a lower bound termination condition.
Case: Departs 0 to right. {R = n1} then {L = n2}. 2<= n2 <= n1.
It terminates on the 1st rightward step after the left moving.
Case: Departs 0 to right. {R = n1} then {L = n2}. n1< n2.
Now negative, and been at 0 twice (started at 0).
Effectively creates an upper bound termination condition, since finished if ever reaches 0 again.