TY - GEN

T1 - Deterministic random walks on regular trees

AU - Cooper, Joshua

AU - Doerr, Benjamin

AU - Friedrich, Tobias

AU - Spencer, Joel

N1 - Copyright:
Copyright 2009 Elsevier B.V., All rights reserved.

PY - 2008

Y1 - 2008

N2 - Jim Propp's rotor router model is a deterministic analogue of a random walk on a graph. Instead of distributing chips randomly, each vertex serves its neighbors in a fixed order. Cooper and Spencer (Comb. Probab. Comput. (2006)] show a remarkable similarity of both models. If an (almost) arbitrary population of chips is placed on the vertices of a grid ℤdand does a simultaneous walk in the Propp model, then at all times and on each vertex, the number of chips deviates from the expected number the random walk would have gotten there, by at most a constant. This constant is independent of the starting configuration and the order in which each vertex serves its neighbors. This result raises the question if all graphs do have this property. With quite some effort, we are now able to answer this question negatively. For the graph being an infinite kary tree (k ≥ 3), we show that for any deviation D there is an initial configuration of chips such that after running the Propp model for a certain time there is a vertex with at least D more chips than expected in the random walk model. However, to achieve a deviation of D it is necessary that at least KΘ(D) vertices contribute by being occupied by a number of chips not divisible by k in a certain time interval.

AB - Jim Propp's rotor router model is a deterministic analogue of a random walk on a graph. Instead of distributing chips randomly, each vertex serves its neighbors in a fixed order. Cooper and Spencer (Comb. Probab. Comput. (2006)] show a remarkable similarity of both models. If an (almost) arbitrary population of chips is placed on the vertices of a grid ℤdand does a simultaneous walk in the Propp model, then at all times and on each vertex, the number of chips deviates from the expected number the random walk would have gotten there, by at most a constant. This constant is independent of the starting configuration and the order in which each vertex serves its neighbors. This result raises the question if all graphs do have this property. With quite some effort, we are now able to answer this question negatively. For the graph being an infinite kary tree (k ≥ 3), we show that for any deviation D there is an initial configuration of chips such that after running the Propp model for a certain time there is a vertex with at least D more chips than expected in the random walk model. However, to achieve a deviation of D it is necessary that at least KΘ(D) vertices contribute by being occupied by a number of chips not divisible by k in a certain time interval.

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

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

M3 - Conference contribution

AN - SCOPUS:58449110604

SN - 9780898716474

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 766

EP - 772

BT - Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms

T2 - 19th Annual ACM-SIAM Symposium on Discrete Algorithms

Y2 - 20 January 2008 through 22 January 2008

ER -