Results 1 to 5 of 5

Math Help - Need help with random walk algorithm

  1. #1
    Newbie
    Joined
    Aug 2009
    Posts
    17

    Post Need help with random walk algorithm

    I have a problem considering a two-dimensional grid.
    The grid size is (L*D) where L and D are known. Each grid site has either 1 or 0 as its value. The total amount of 1's is known and equal to N. The rest of the (L*D - N) sites are 0's.
    At the beggining the N 1's are spread randomly over the grid.

    I wish to create an algorithm which in every steps randomly selects one of the (1) spots, and moves it (randomly) to one of its four nearest neighbours. This move is only allowed if the neighbour isn't occupied (0) and the site is inside the grid, as to preserve the total number of 1's.

    Descriptive example:

    0 0 0 0 0
    0 0 1 0 1
    0 0 1 0 0

    At the nex step, the bold 1 can move up, left and right, but not down (since there's a 1 in that spot). The italics 1 can move up, down and left, but not right (since it is the end of the grid).

    Currently I use this type of algorithm:
    1. Randomly choose a 1 in the grid.
    2. Randomly choose a direction (out of 4 allowed).
    3. If possible, move the 1 to the new spot and replace the old spot by 0. If not possible, go to step 1.

    As it appears, this algorithm has a severe flaw: The 1's start out nearly evenly distributed. As I perform increasingly many iterations of the above algorithms, the 1's seem to clump up near the edges of the grid, and the middle stays pretty much empty.

    This is a very bad behavior, since I require an algorithm where the 1's stay evenly distributed no matter how many moves are performed. This is to simulate sort of a simple classical gas in a 2D container.

    I suspect that this phenomenon arises from the following cause: 1's at the perimeters of the grid have on average a lower probability to move than those in the middle, since they have less spots open for them to move to.

    How can I change this algorithm as to still move only one (1) every step, and maintain the even distribution of 1's in the grid?

    If it helps simplify the matter, you can consider a 1 dimesional case of this question, because the other dimension in my problem has quasi-periodic boundary conditions (so 1's don't clump up at the top or bottom of the grid).
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Nov 2009
    Posts
    23
    Quote Originally Posted by Marril View Post

    Descriptive example:

    0 0 0 0 0
    0 0 1 0 1
    0 0 1 0 0


    Currently I use this type of algorithm:
    1. Randomly choose a 1 in the grid.
    2. Randomly choose a direction (out of 4 allowed).
    3. If possible, move the 1 to the new spot and replace the old spot by 0. If not possible, go to step 1.
    One idea:
    chance this If not possible, go to step 1.
    by changing these

    • the bold 1 can move up, left and right, but not down (since there's a 1 in that spot).


    • The italics 1 can move up, down and left, but not right (since it is the end of the grid)

    for example let the italic 1 go left like the "wall" forces it to do it.

    Because This is to simulate sort of a simple classical gas in a 2D container.
    one idea is that the move of the bold 1, recursively cause many moves, if you choose "down" where there exists allready one 1.
    Last edited by liberty; November 19th 2009 at 02:20 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Aug 2009
    Posts
    17
    for example let the italic 1 go left like the "wall" forces it to do it.
    Tell me if I understand this correctly:
    Your suggestion is that if a 1 tries to move into a prohibited spot, it gets "reflected" to the other side. This may be a useful approach and makes some physical sense. Unfortunately I tried this and it doesn't seem to work. The 1's still seem to clump up near the extremities, at a somewhat slower rate.

    one idea is that the move of the bold 1, recursively cause many moves, if you choose "down" where there exists allready one 1.
    Here I suppose you suggest that I try to move a 1 to all 4 directions before giving up on it and trying a different 1. Also a reasonable suggestion, I will try it later today.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2008
    From
    Paris, France
    Posts
    1,174
    Quote Originally Posted by Marril View Post
    I suspect that this phenomenon arises from the following cause: 1's at the perimeters of the grid have on average a lower probability to move than those in the middle, since they have less spots open for them to move to.
    In fact, the reason can only come from the interactions between the 1's (or a programming error). Indeed, if your particles move without interacting with each other (so with possibly many particles at one site), then the distribution of the particles converges to the uniform distribution, whatever the starting positions are. (If you know Markov chains, you can check that the uniform distribution is a stationnary measure for the process defined by the motion of 1 particle) So this part of your algorithm is correct.

    You should run your algorithm after disabling the interaction and see if indeed your phenomenon disappears. If not, you should re-check your code.

    I can't pronounce rigorously however on the effect of interactions. It is not unlikely that they perturb the distribution.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Aug 2009
    Posts
    17
    Thanks for your input Laurent!
    However, the only interaction between the particles in my model is the fact that only one particle may occupy each cell (fermion like particles). This changes the probability of moving a particular particle according to it's neighborhood.

    It seems the suggestions above by liberty didn't do the trick. I guess the next step is to try to formulate master equations and find a method where movement probabilities are conserved.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Random Walk in 2D
    Posted in the Advanced Statistics Forum
    Replies: 3
    Last Post: November 17th 2010, 03:04 AM
  2. an almost random walk SP
    Posted in the Advanced Statistics Forum
    Replies: 3
    Last Post: July 15th 2010, 10:58 AM
  3. Random Walk in 1-D
    Posted in the Advanced Statistics Forum
    Replies: 2
    Last Post: May 3rd 2010, 09:14 AM
  4. Random Walk
    Posted in the Advanced Statistics Forum
    Replies: 5
    Last Post: November 16th 2009, 01:31 PM
  5. Algorithm Theta-walk (p,q) - Need help!
    Posted in the Geometry Forum
    Replies: 3
    Last Post: August 17th 2009, 09:45 PM

Search Tags


/mathhelpforum @mathhelpforum