Results 1 to 5 of 5

Math Help - Random walk problem

  1. #1
    Newbie
    Joined
    Nov 2007
    From
    Sault Ste. Marie, Ontario
    Posts
    15

    Random walk problem

    Hi there,

    I'm currently studying diffusion theory and I'm hung up on a basic principle. Imagine a line that extends infinitely in either direction and in the middle is the origin. Where I'm hung up is here: say you had n moves and you wanted to know the number of paths to get to a point m units to the right of the origin and you could go left a times and right b times in one unit steps. My text gives this formula:

    n!/(a!b!)
    My problem is not that I don't know how to use this formula; instead, I don't understand how they arrived at this formula. Why do they use n! and why do they divide it by a!b!? Any insight into this would be appreciated.

    jjmclell
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Oct 2007
    Posts
    145
    Let's cast your problem into a 8x8 chessboard.
    How many shortest paths can you take from one diagonal corner to the next?

    We know the length of the shortest path is 16. (no of moves is 16)
    Let the path of going up 1 square be a, and the path of going right one square be b.
    So to get to the other corner, we can take a path of:
    aaaaaaaabbbbbbbb
    or
    abababababababab
    ...

    The number of ways you can order this is:
    {16!\over {8!8!}}

    Maybe this helps.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2007
    From
    Sault Ste. Marie, Ontario
    Posts
    15
    So basically we're talking permutations?...it's been so long since my highschool finite math class but I think I understand what you're getting at. However I still don't understand the WHY part of the formula. From your example, I can understand n!...it's like having having 16 moves in a hat and the order in which you can draw them is 16x15x14....or 16!. I also see that because we only have two different moves, there would be paths that are replicates of each other and we want to take them out of the total number of paths. I assume that is why we divide n! by a!b! but I cannot understand why that does the trick of eliminating replicated paths. Does this make sense?...I'm probably talking like a crazy person right now but it's hard to describe my mental frustration with this problem.

    jjmclell
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Oct 2007
    Posts
    145
    Let's create another simplier analogy.
    There are 3 boys and 2 girls. How many ways can you order them in a row?

    BBBGG
    BBGGB
    BGGBB
    GGBBB
    GBBBG
    GBBGB
    GBGBB
    BGBGB
    BBGBG
    BGBBG

    There are 10 ways. Instead of listing them out, you can use the formula:
    {5!}\over{3!2!}

    And the reason for dividing by 3! is to remove all instances of the case when:
    B1 B2 B3 GG = B2 B1 B3 GG = B3 B1 B2 GG = ....(there are 6 such arrangements. We are interested in only 1).
    Same goes for the girls.


    Is this what you want? Forgive me if I am out of point.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Nov 2007
    From
    Sault Ste. Marie, Ontario
    Posts
    15
    Thanks a lot. I think I now understand why the formula is the way it is. Much appreciated.
    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, 09:43 PM
  2. Random Walk in 2D
    Posted in the Advanced Statistics Forum
    Replies: 3
    Last Post: November 17th 2010, 03:04 AM
  3. Random walk
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: February 16th 2010, 09:34 AM
  4. Another problem related to random walk...
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: September 19th 2009, 02:24 PM
  5. random walk probability problem
    Posted in the Advanced Statistics Forum
    Replies: 4
    Last Post: April 26th 2008, 12:08 PM

Search Tags


/mathhelpforum @mathhelpforum