Deterministic random walks on regular trees

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