Results 1 to 6 of 6

Math Help - A random walk problem

  1. #1
    Newbie
    Joined
    Oct 2012
    From
    kolkata
    Posts
    4

    A random walk problem

    Hi , I'm Drishan.. 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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Sep 2012
    From
    Australia
    Posts
    3,649
    Thanks
    601

    Re: A random walk problem

    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2012
    From
    kolkata
    Posts
    4

    Re: A random walk problem

    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)
    Last edited by drishan; October 2nd 2012 at 03:17 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Sep 2012
    From
    Washington DC USA
    Posts
    525
    Thanks
    146

    Re: A random walk problem

    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).
    Last edited by johnsomeone; October 2nd 2012 at 09:37 AM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Oct 2012
    From
    kolkata
    Posts
    4

    Re: A random walk problem

    @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
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member
    Joined
    Sep 2012
    From
    Washington DC USA
    Posts
    525
    Thanks
    146

    Re: A random walk problem

    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.
    Last edited by johnsomeone; October 2nd 2012 at 10:05 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. A random walk problem
    Posted in the New Users Forum
    Replies: 0
    Last Post: October 1st 2012, 09:49 AM
  2. random walk
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: November 16th 2009, 01:50 PM
  3. Another problem related to random walk...
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: September 19th 2009, 02:24 PM
  4. random walk probability problem
    Posted in the Advanced Statistics Forum
    Replies: 4
    Last Post: April 26th 2008, 12:08 PM
  5. Random walk problem
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: November 17th 2007, 08:08 AM

Search Tags


/mathhelpforum @mathhelpforum