Deterministic random walks

Joshua Cooper, Benjamin Doerr, Joel Spencer, Garbor Tardos

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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 ℤ.

Original languageEnglish (US)
Title of host publicationProceedings of the 8th Workshop on Algorithm Engineering and Experiments and the 3rd Workshop on Analytic Algorithms and Combinatorics
Pages185-197
Number of pages13
StatePublished - 2006
Event8th Workshop on Algorithm Engineering and Experiments and the 3rd Workshop on Analytic Algorithms and Combinatorics - Miami, FL, United States
Duration: Jan 21 2006Jan 21 2006

Publication series

NameProceedings of the 8th Workshop on Algorithm Engineering and Experiments and the 3rd Workshop on Analytic Algorithms and Combinatorics
Volume2006

Other

Other8th Workshop on Algorithm Engineering and Experiments and the 3rd Workshop on Analytic Algorithms and Combinatorics
CountryUnited States
CityMiami, FL
Period1/21/061/21/06

ASJC Scopus subject areas

  • Engineering(all)

Fingerprint Dive into the research topics of 'Deterministic random walks'. Together they form a unique fingerprint.

  • Cite this

    Cooper, J., Doerr, B., Spencer, J., & Tardos, G. (2006). Deterministic random walks. In Proceedings of the 8th Workshop on Algorithm Engineering and Experiments and the 3rd Workshop on Analytic Algorithms and Combinatorics (pp. 185-197). (Proceedings of the 8th Workshop on Algorithm Engineering and Experiments and the 3rd Workshop on Analytic Algorithms and Combinatorics; Vol. 2006).