Results 1 to 14 of 14

Math Help - Random Walk in 1-D (Q2)

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

    Random Walk in 1-D (Q2)

    Let at t=0 a drunkard be at x = 0
    At each time interval he jumps +/- 1. So at t=1 he is at x = -1 OR at x = 1.

    Given that at t = 2n , dunkard is back at x = 0.

    So number of possible paths are 2nC_n

    Question
    1. Of the above possible paths, how many paths are there such that the drunkard is always within 'a' units from the origin. i.e. |x|<=a for all t = 0,1,2,....2n.


    Note: I was able to solve the case where instead of |x|<=a, we just had x<=a. (Using the reflection principle). But with |x| I don't seem to be getting anywhere

    Any help here please?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Oct 2009
    Posts
    95
    Quote Originally Posted by aman_cc View Post
    Let at t=0 a drunkard be at x = 0
    At each time interval he jumps +/- 1. So at t=1 he is at x = -1 OR at x = 1.

    Given that at t = 2n , dunkard is back at x = 0.

    So number of possible paths are 2nC_n

    Question
    1. Of the above possible paths, how many paths are there such that the drunkard is always within 'a' units from the origin. i.e. |x|<=a for all t = 0,1,2,....2n.


    Note: I was able to solve the case where instead of |x|<=a, we just had x<=a. (Using the reflection principle). But with |x| I don't seem to be getting anywhere

    Any help here please?
    Wouldn't the number of walks with x=0 at t=2n be exactly \binom{2n}{n}. Here is my reasoning: you need exactly n +1 steps and exactly n -1 steps. In total there are 2n steps. If you choose n of these 2n steps to be +1 then the remaining steps must be -1. There are \binom{2n}{n} ways of choosing those steps.

    I'm not sure about the second part will think about it.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by gmatt View Post
    Wouldn't the number of walks with x=0 at t=2n be exactly \binom{2n}{n}.
    This is the same as what the OP had. It's just that the 2n wasn't subscripted or superscripted so it looked like the expression might refer to something else.

    I'm also interested in solving the OP's main problem and am finding it difficult, don't know how much time I can put into it and whether I'd find the answer.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Oct 2009
    Posts
    95
    Quote Originally Posted by undefined View Post
    This is the same as what the OP had. It's just that the 2n wasn't subscripted or superscripted so it looked like the expression might refer to something else.

    I'm also interested in solving the OP's main problem and am finding it difficult, don't know how much time I can put into it and whether I'd find the answer.
    Wow, thanks for clearing that up, I thought the OP meant C_n as a catalan number!
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Apr 2009
    Posts
    678
    Thanks
    1
    Quote Originally Posted by gmatt View Post
    Wow, thanks for clearing that up, I thought the OP meant C_n as a catalan number!
    Sorry for the confusion. I meant \binom{2n}{n}And indeed, I have been thinking on my original problem for couple of days but not going anywhere. Let's see.
    Thanks
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Oct 2009
    Posts
    95
    Here is what I got so far.

    The idea is to look for a (very complicated) recursion.

    I'm going to consider vectors of the form

    <br />
\left[ \binom{a}{b}, c, d  \right]<br />

    where

    c - the current distance
    d - the maximum distance observed so far.

    The idea is then to use an extended version of pascals identity:

    <br />
\left[ \binom{2n}{n}, 0, 0  \right] =  \left[ \binom{2n-1}{n}, -1, 1  \right] + \left[ \binom{2n-1}{n-1}, 1, 1  \right]<br />

    <br />
=  \left[ \binom{2n-2}{n}, -2, 2   \right] + \left[ \binom{2n-2}{n-1}, 0, 1  \right] + \left[ \binom{2n-2}{n-1}, 0, 1  \right] + \left[ \binom{2n-2}{n-2}, 2, 2   \right]<br />

    but clearly
    \left[ \binom{2(n-1)}{n-1}, 0, 1  \right] is a recursion on n-1!

    In fact you only need to recurse on  \left[ \binom{2n-2}{n}, -2, 2   \right], because the other side of the recursion tree is symmetric.

    As you expand out the tree for  \left[ \binom{2n-2}{n}, -2, 2   \right] a miracle happens, all the terms you have computed before start reappearing all over the place, for the exact same values of c (thats important) but possibly different values of d (not important to the recursion, but still important in tallying up the number of paths of maximum length d.) So the entire thing starts to recurse, I haven't yet figured out the exact recursion but only the binomial and c are the important values when determining the recursion.

    Well, this isn't complete by any stretch of the imagination but it may give some fuel for some better thoughts. Here is a picture of what the (basic) recursion tree looks like, obviously you would need to expand it out to get a better idea:


    edit --- it may be unclear why I'm doing such a recursion, so I'll give an example

    if you consider the case n=3 then compute the entire recursion tree using that identity until all leaf nodes in the recursion tree you construct are of the form \left[ \binom{k}{k}, c, d  \right] or \left[ \binom{k}{0}, c, d  \right] then that means to get the number of paths of maximum length d you sum up all the leaf nodes (they will all be equal to 1) where d is the desired value. For n = 3 this gives for d=1, 8, d=2, 10 and d = 3, 2.
    Last edited by gmatt; May 5th 2010 at 11:52 PM.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Oct 2009
    Posts
    95
    Forgot to include picture of recursion tree:

    Follow Math Help Forum on Facebook and Google+

  8. #8
    Super Member
    Joined
    Apr 2009
    Posts
    678
    Thanks
    1
    Quote Originally Posted by gmatt View Post
    Here is what I got so far.

    The idea is to look for a (very complicated) recursion.

    I'm going to consider vectors of the form

    <br />
\left[ \binom{a}{b}, c, d \right]<br />

    where

    c - the current distance
    d - the maximum distance observed so far.

    The idea is then to use an extended version of pascals identity:

    <br />
\left[ \binom{2n}{n}, 0, 0 \right] = \left[ \binom{2n-1}{n}, -1, 1 \right] + \left[ \binom{2n-1}{n-1}, 1, 1 \right]<br />

    <br />
= \left[ \binom{2n-2}{n}, -2, 2 \right] + \left[ \binom{2n-2}{n-1}, 0, 1 \right] + \left[ \binom{2n-2}{n-1}, 0, 1 \right] + \left[ \binom{2n-2}{n-2}, 2, 2 \right]<br />

    but clearly
    \left[ \binom{2(n-1)}{n-1}, 0, 1 \right] is a recursion on n-1!

    In fact you only need to recurse on  \left[ \binom{2n-2}{n}, -2, 2 \right], because the other side of the recursion tree is symmetric.

    As you expand out the tree for  \left[ \binom{2n-2}{n}, -2, 2 \right] a miracle happens, all the terms you have computed before start reappearing all over the place, for the exact same values of c (thats important) but possibly different values of d (not important to the recursion, but still important in tallying up the number of paths of maximum length d.) So the entire thing starts to recurse, I haven't yet figured out the exact recursion but only the binomial and c are the important values when determining the recursion.

    Well, this isn't complete by any stretch of the imagination but it may give some fuel for some better thoughts. Here is a picture of what the (basic) recursion tree looks like, obviously you would need to expand it out to get a better idea:


    edit --- it may be unclear why I'm doing such a recursion, so I'll give an example

    if you consider the case n=3 then compute the entire recursion tree using that identity until all leaf nodes in the recursion tree you construct are of the form \left[ \binom{k}{k}, c, d \right] or \left[ \binom{k}{0}, c, d \right] then that means to get the number of paths of maximum length d you sum up all the leaf nodes (they will all be equal to 1) where d is the desired value. For n = 3 this gives for d=1, 8, d=2, 10 and d = 3, 2.
    Well thanks for so much effort. I will have to read your approach carefully. I seem to have heard that this can be solved using the principle of reflection (refer to ballot problem). So I'm working on those lines. Let's see - will post my approach as well once I'm little convinced about it.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member
    Joined
    Oct 2009
    Posts
    95
    So after much deliberation, I think I have arrived at the answer.

    I do not have the time to explain it in the amount of detail that it deserves so I will not attempt to explain it tonight, I will just present the answer and say that I arrived at it using inclusion-exclusion along with the reflection principle you mentioned.

    Before I present the answer, I need to make clear that I use the convention

    <br />
\binom{n}{k} = 0<br />

    for all k<0.

    Let m=a+1.
    The number of walks with distance \le a at all times is given by

    <br />
\binom{2n}{n}+2 \sum _{k=1} ^\infty (-1)^k \binom{2n}{n- k m}.<br />

    I will explain in much more detail tomorrow why this is true, since it will take several detailed diagrams to describe how the reflections work and where the inclusion-exclusion principle comes into play. Unfortunately I fear explaining this may take several hours.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Member
    Joined
    Oct 2009
    Posts
    95
    Quote Originally Posted by gmatt View Post
    So after much deliberation, I think I have arrived at the answer.

    I do not have the time to explain it in the amount of detail that it deserves so I will not attempt to explain it tonight, I will just present the answer and say that I arrived at it using inclusion-exclusion along with the reflection principle you mentioned.

    Before I present the answer, I need to make clear that I use the convention

    <br />
\binom{n}{k} = 0<br />

    for all k<0.

    Let m=a+1.
    The number of walks with distance \le a at all times is given by

    <br />
\binom{2n}{n}+2 \sum _{k=1} ^\infty (-1)^k \binom{2n}{n- k m}.<br />

    I will explain in much more detail tomorrow why this is true, since it will take several detailed diagrams to describe how the reflections work and where the inclusion-exclusion principle comes into play. Unfortunately I fear explaining this may take several hours.
    As a quick corollary

    let a=0,m=1 then we have that

    <br />
\binom{2n}{n} = 2 \sum _{k=1} ^\infty (-1)^{k+1} \binom{2n}{n- k} = 2 \sum _{k=1} ^n (-1)^{k+1} \binom{2n}{n- k}<br />

    since we know that for any n we must have that the number of walks with distance always \le a = 0 is 0.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Super Member
    Joined
    Apr 2009
    Posts
    678
    Thanks
    1
    Quote Originally Posted by gmatt View Post
    As a quick corollary

    let a=0,m=1 then we have that

    <br />
\binom{2n}{n} = 2 \sum _{k=1} ^\infty (-1)^{k+1} \binom{2n}{n- k} = 2 \sum _{k=1} ^n (-1)^{k+1} \binom{2n}{n- k}<br />

    since we know that for any n we must have that the number of walks with distance always \le a = 0 is 0.

    Thanks a lot !!! I'm in no hurry so you don't need to stretch yourself to write down the whole explanation. Let me go over your answer carefully.
    I also seem to be hitting in some direction. Will post my result today/tomorrow. Thanks yet again
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Member
    Joined
    Oct 2009
    Posts
    95
    Okay,

    I made some figures tonight but unfortunately don't have enough time to explain them, I'll just attach them for now and add an explanation the next day hopefully.






    Follow Math Help Forum on Facebook and Google+

  13. #13
    Member
    Joined
    Oct 2009
    Posts
    95
    Okay, here is a very detailed explanation of what is going on.

    I wrote it up as a document, because I did not want to struggle with any limitations this forum imposes.

    Tell me if you have any questions.

    Can be downloaded at : http://sites.google.com/site/garamatt/dlw.pdf

    Also added as an attachment.

    Ps. I don't know how to delete a post but would like to delete my previous post.
    Attached Files Attached Files
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Super Member
    Joined
    Apr 2009
    Posts
    678
    Thanks
    1
    Quote Originally Posted by gmatt View Post
    Okay, here is a very detailed explanation of what is going on.

    I wrote it up as a document, because I did not want to struggle with any limitations this forum imposes.

    Tell me if you have any questions.

    Can be downloaded at : http://sites.google.com/site/garamatt/dlw.pdf

    Also added as an attachment.

    Ps. I don't know how to delete a post but would like to delete my previous post.

    Thanks a lot - Let me readup your document
    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
    Posted in the Advanced Statistics Forum
    Replies: 2
    Last Post: May 3rd 2010, 10:14 AM
  5. Random walk
    Posted in the Advanced Statistics Forum
    Replies: 2
    Last Post: February 19th 2009, 06:22 AM

Search Tags


/mathhelpforum @mathhelpforum