ausblenden:
Schlagwörter:
-
Zusammenfassung:
Jim Propp�s rotor router model is a simple deterministic analogue of a random
walk.
Instead of distributing chips randomly, it serves the neighbors in a fixed
order. We
analyze the difference between Propp machine and random walk on the infinite
two-
dimensional grid. We show 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 c, which is 7.83 for
clockwise
rotor sequences and 7.28 otherwise. This is the first paper which demonstrates
that
the order in which the neighbors are served makes a difference.