TY - GEN

T1 - Deterministic random walks

AU - Cooper, Joshua

AU - Doerr, Benjamin

AU - Spencer, Joel

AU - Tardos, Garbor

PY - 2006

Y1 - 2006

N2 - Jim Propp's P-machine, also known as 'rotor router model' is a simple deterministic process that simulates a random walk on a graph. Instead of distributing chips to randomly chosen neighbors, it serves the neighbors in a fixed order. We investigate how well this process simulates a random walk. For the graph being the infinite path, we show that, independent of the starting configuration, at each time and on each vertex, the number of chips on this vertex deviates from the expected number of chips in the random walk model by at most a constant C1, which is approximately 2.29. For intervals of length L, this improves to a difference of O(log L) (instead of 2.29L), for the L2 average of a contiguous set of intervals even to O(√log L). It seems plausible that similar results hold for higher-dimensional grids ℤd instead of the path ℤ.

AB - Jim Propp's P-machine, also known as 'rotor router model' is a simple deterministic process that simulates a random walk on a graph. Instead of distributing chips to randomly chosen neighbors, it serves the neighbors in a fixed order. We investigate how well this process simulates a random walk. For the graph being the infinite path, we show that, independent of the starting configuration, at each time and on each vertex, the number of chips on this vertex deviates from the expected number of chips in the random walk model by at most a constant C1, which is approximately 2.29. For intervals of length L, this improves to a difference of O(log L) (instead of 2.29L), for the L2 average of a contiguous set of intervals even to O(√log L). It seems plausible that similar results hold for higher-dimensional grids ℤd instead of the path ℤ.

UR - http://www.scopus.com/inward/record.url?scp=33646842218&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33646842218&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:33646842218

SN - 0898716101

SN - 9780898716108

T3 - Proceedings of the 8th Workshop on Algorithm Engineering and Experiments and the 3rd Workshop on Analytic Algorithms and Combinatorics

SP - 185

EP - 197

BT - Proceedings of the 8th Workshop on Algorithm Engineering and Experiments and the 3rd Workshop on Analytic Algorithms and Combinatorics

T2 - 8th Workshop on Algorithm Engineering and Experiments and the 3rd Workshop on Analytic Algorithms and Combinatorics

Y2 - 21 January 2006 through 21 January 2006

ER -