Deterministic random walks on the two-dimensional grid

DOI10.1017/S0963548308009589MaRDI QIDQ3557507zbMATH OpenOpenAlexFDO

Authors Benjamin Doerr, Tobias Friedrich

Publication date 23 April 2010

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

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

zbMATH Keywords

Propp machinerandom walk on a graphrotor router model

Mathematics Subject Classification ID

Random walks on graphs (05C81) Sums of independent random variables; random walks (60G50)

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. We analyze the difference between Propp machine and random walk on the infinite two-dimensional grid. It is known that, apart from a technicality, independent of the starting configuration, at each time, the number of chips on each vertex in the Propp model deviates from the expected number of chips in the random walk model by at most a constant. We show that this constant is approximately 7.8, if all vertices serve their neighbors in clockwise or counterclockwise order and 7.3 otherwise. This result in particular shows that the order in which the neighbors are served makes a difference. Our analysis also reveals a number of further unexpected properties of the two-dimensional Propp machine.

Recommendations

• Deterministic Random Walks on Regular Trees
• Deterministic random walks
• Quasirandomness in Graphs
• Deterministic random walks on regular trees
• Deterministic random walks on the integers

Cites work

• Deterministic random walks on the integers
• Goldbug variations
• scientific article; zbMATH DE number 1446863 (Why is no real title available?)
• Internal diffusion limited aggregation
• Internal diffusion-limited aggregation: parallel algorithms and complexity
• Simulating a Random Walk with Constant Error
• Subdiffusive fluctuations for internal diffusion limited aggregation
• The rotor-router shape is spherical

Cited in

(29)

• Total variation discrepancy of deterministic random walks for ergodic Markov chains
• Goldbug variations
• A deterministic walk on the randomly oriented Manhattan lattice
• Does adding more agents make a difference? A case study of cover time for the rotor-router
• The multi-agent rotor-router on the ring: a deterministic alternative to parallel random walks
• Robustness of the rotor-router mechanism
• Bounds on the cover time of parallel rotor walks
• Deterministic random walks on regular trees
• Simulating a Random Walk with Constant Error
• Quasirandomness in Graphs
• Understanding chicken walks on n × n grid: Hamiltonian paths, discrete dynamics, and rectifiable paths
• Deterministic Random Walks on Regular Trees
• Deterministic random walks for rapidly mixing chains
• Unbounded discrepancy of deterministic random walks on grids
• Orbits of rotor-router operation and stationary distribution of random walks on directed graphs
• Infinite-step stationarity of rotor walk and the wired spanning forest
• Reachability switching games
• Minimalist art from cellular automata
• Reachability Switching Games
• Deterministic random walks
• Discrete analog computing with rotor-routers
• Deterministic random walks on finite graphs
• Deterministic Random Walks on the Two-Dimensional Grid
• Consistency of Markov chain quasi-Monte Carlo on continuous state spaces
• A simple approach for adapting continuous load balancing processes to discrete settings
• Proppian random walks in Z
• Derandomizing random walks in undirected graphs using locally fair exploration strategies
• Deterministic walks with choice
• Randomized diffusion for indivisible loads

This page was built for publication: Deterministic random walks on the two-dimensional grid

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