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 0101

0 0 1 0 0

At the nex step, thebold1 can move up, left and right, but not down (since there's a 1 in that spot). Theitalics1 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).