| Jim Propp's rotor router model is a deterministic analogue of a random walk on a
graph. Instead of distributing chips randomly, each vertex serves its neighbors
in a fixed order. We analyze the difference between Propp machine and random
walk on the infinite two-dimensional grid. It is known that, independent of the
starting configuration, at each time, the number of chips on each vertex
deviates from the expected number of chips in the random walk model by at most a
constant. We show that this constant is approximately 7.8, if all vertices serve
their neighbors in clockwise or counterclockwise order and 7.3 otherwise. This
result in particular shows that the order in which the neighbors are served
makes a difference. Our analysis also reveals a number of unexpected properties
of these Propp machines. |
