2006/02/14 by Joshua Cooper, Cooper, Joshua, Benjamin Doerr +6
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #11K45 #60C05 #Algorithms and Data Compression #Cellular Automata and Applications #Combinatorics (math.CO) #DNA and Biological Computing #FOS: Mathematics #Probability (math.PR) #math.CO #math.PR #msc:11K45 #msc:60C05
paper · pdf · doi:10.48550/arxiv.math/0602300
27 pages, 0 figured
arxiv created 2006/02/14 · openalex publication_date 2006/02/14 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Jim Propp's P-machine, also known as the "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), for the L2 average of a contiguous set of intervals even to O(sqrtlog L). All these bounds are tight.