Results 1 to 3 of 3

Math Help - Random Walk in 1-D

  1. #1
    Super Member
    Joined
    Apr 2009
    Posts
    678
    Thanks
    1

    Random Walk in 1-D

    Consider a random walk in one dimension.

    Consider a numberline with integers marked on it. A drunkard it at x=0 at t=0. At each time interval he jumps +1 or -1. i.e. at t=1 he can be at x=1 or x = -1

    After t = n, let him be at x_n.

    What is the probability that |x_n| =< a, where a is some +ve integer.

    Any ideas to start on this?

    Also I would later want to generalize it to include conditions like
    1. x_n > a
    2. x_n < b
    and combine them using AND, OR.

    So please advise. Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member Failure's Avatar
    Joined
    Jul 2009
    From
    Zürich
    Posts
    555
    Quote Originally Posted by aman_cc View Post
    Consider a random walk in one dimension.

    Consider a numberline with integers marked on it. A drunkard it at x=0 at t=0. At each time interval he jumps +1 or -1. i.e. at t=1 he can be at x=1 or x = -1

    After t = n, let him be at x_n.

    What is the probability that |x_n| =< a, where a is some +ve integer.

    Any ideas to start on this?
    Let p be the probability that he takes a step to the right, then the probability of his being at position 2k-n after n steps is

    \mathrm{P}(X_n=2k-n)=\binom{n}{k}p^k (1-p)^{n-k}

    If p=1/2 this simplifies to \mathrm{P}(X_n=2k-n)=\binom{n}{k}2^{-n}, of course.

    By setting x := 2k-n it follows from this that if x\in \{-n,-n+1,\ldots, 0, 1, \ldots, n-1, n\}, we have

    \mathrm{P}(X_n=x)=\begin{cases} \binom{n}{\frac{x+n}{2}}p^k(1-p)^{n-k}, & \text{if } x+n\text{ is even} \\<br />
0,&\text{otherwise}<br />
\end{cases}

    Given that, the probability that |X_n|\leq a is

    \mathrm{P}(|X_n|\leq a) = \sum_{x=-a}^a\mathrm{P}(X_n=x)
    (assuming that a\in\{0,1,\ldots,n\}).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Apr 2009
    Posts
    678
    Thanks
    1
    Quote Originally Posted by Failure View Post
    Let p be the probability that he takes a step to the right, then the probability of his being at position 2k-n after n steps is

    \mathrm{P}(X_n=2k-n)=\binom{n}{k}p^k (1-p)^{n-k}

    If p=1/2 this simplifies to \mathrm{P}(X_n=2k-n)=\binom{n}{k}2^{-n}, of course.

    By setting x := 2k-n it follows from this that if x\in \{-n,-n+1,\ldots, 0, 1, \ldots, n-1, n\}, we have

    \mathrm{P}(X_n=x)=\begin{cases} \binom{n}{\frac{x+n}{2}}p^k(1-p)^{n-k}, & \text{if } x+n\text{ is even} \\<br />
0,&\text{otherwise}<br />
\end{cases}

    Given that, the probability that |X_n|\leq a is

    \mathrm{P}(|X_n|\leq a) = \sum_{x=-a}^a\mathrm{P}(X_n=x)
    (assuming that a\in\{0,1,\ldots,n\}).
    Really sorry but there is an errata in my question. The question is -
    How may paths are there which start at
    x = 0 (@ t = 0)
    and end at
    x = x_n (@ t = n)

    so that you are never more than 'a' units away from the origin.

    Sorry once again plz
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Random walk
    Posted in the Advanced Statistics Forum
    Replies: 4
    Last Post: March 26th 2011, 10:43 PM
  2. Random Walk
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: October 18th 2010, 05:29 PM
  3. an almost random walk SP
    Posted in the Advanced Statistics Forum
    Replies: 3
    Last Post: July 15th 2010, 11:58 AM
  4. Random Walk in 1-D (Q2)
    Posted in the Discrete Math Forum
    Replies: 13
    Last Post: May 10th 2010, 01:45 AM
  5. Random walk
    Posted in the Advanced Statistics Forum
    Replies: 2
    Last Post: February 19th 2009, 06:22 AM

Search Tags


/mathhelpforum @mathhelpforum