Deterministic random walks on regular trees
- 4 February 2010
- journal article
- research article
- Published by Wiley in Random Structures & Algorithms
- Vol. 37 (3) , 353-366
Abstract
Jim Propp's rotor–router model is a deterministic analog 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 15 (2006) 815–822) show a remarkable similarity of both models. If an (almost) arbitrary population of chips is placed on the vertices of a grid ℤd and does a simultaneous walk in the Propp model, then at all times and on each vertex, the number of chips on this vertex 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 k‐ary 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 exp(Ω(D2)) vertices contribute by being occupied by a number of chips not divisible by k at a certain time. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 2010Keywords
All Related Versions
This publication has 8 references indexed in Scilit:
- Deterministic Random Walks on the Two-Dimensional GridCombinatorics, Probability and Computing, 2009
- The rotor–router model on regular treesJournal of Combinatorial Theory, Series A, 2009
- Deterministic random walks on the integersEuropean Journal of Combinatorics, 2007
- Simulating a Random Walk with Constant ErrorCombinatorics, Probability and Computing, 2006
- The rotor-router shape is sphericalThe Mathematical Intelligencer, 2005
- Inequalities for Beta and Gamma functions via some classical and new integral inequalitiesJournal of Inequalities and Applications, 2000
- Eulerian Walkers as a Model of Self-Organized CriticalityPhysical Review Letters, 1996
- Catalan Numbers, Their Generalization, and Their UsesThe Mathematical Intelligencer, 1991