Quasirandomness in Graphs

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.