Deterministic random walks on regular trees

DOI10.1002/RSA.20314MaRDI QIDQ3055897zbMATH OpenOpenAlexFDO

Authors Benjamin Doerr, Tobias Friedrich, Joshua Cooper, Joel Spencer

Publication date 10 November 2010

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1006.1441

zbMATH Keywords

discrepancyrotor-router modelquasirandomness

Mathematics Subject Classification ID

Trees (05C05) Random walks on graphs (05C81)

Abstract: 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 $$ 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 ($kge3$), 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(Omega(D^2))$ vertices contribute by being occupied by a number of chips not divisible by $k$ at a certain time.

Recommendations

• Deterministic Random Walks on Regular Trees
• Deterministic random walks on the two-dimensional grid
• Deterministic random walks
• Quasirandomness in Graphs
• Deterministic random walks on the integers

Cites work

• scientific article; zbMATH DE number 5713958 (Why is no real title available?)
• Catalan numbers, their generalization, and their uses
• Deterministic random walks on the integers
• Deterministic random walks on the two-dimensional grid
• Inequalities for Beta and Gamma functions via some classical and new integral inequalities
• Simulating a Random Walk with Constant Error
• The rotor-router model on regular trees
• The rotor-router shape is spherical

Cited in

(15)

• Reachability Switching Games
• Deterministic random walks
• Toward derandomizing Markov chain Monte Carlo
• Derandomizing random walks in undirected graphs using locally fair exploration strategies
• Quasirandomness in Graphs
• Deterministic Random Walks on Regular Trees
• Deterministic random walks for rapidly mixing chains
• Deterministic random walks on finite graphs
• The rotor-router model on regular trees
• A simple approach for adapting continuous load balancing processes to discrete settings
• Deterministic random walks on the two-dimensional grid
• Deterministic walks with choice
• Unbounded discrepancy of deterministic random walks on grids
• Reachability switching games
• Total variation discrepancy of deterministic random walks for ergodic Markov chains

This page was built for publication: Deterministic random walks on regular trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3055897)