Deterministic Random Walks on the Two-Dimensional Grid

DOI10.1017/S0963548308009589zbMath1185.05130arXivmath/0703453OpenAlexW2117204986MaRDI QIDQ3557507

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

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

Related Items (23)

Bounds on the cover time of parallel rotor walks ⋮ The multi-agent rotor-router on the ring: a deterministic alternative to parallel random walks ⋮ Robustness of the rotor-router mechanism ⋮ Total variation discrepancy of deterministic random walks for ergodic Markov chains ⋮ Deterministic Random Walks for Rapidly Mixing Chains ⋮ Unnamed Item ⋮ Proppian random walks in \(\mathbb Z\) ⋮ A simple approach for adapting continuous load balancing processes to discrete settings ⋮ Derandomizing random walks in undirected graphs using locally fair exploration strategies ⋮ Reachability Switching Games ⋮ Orbits of rotor-router operation and stationary distribution of random walks on directed graphs ⋮ Unbounded Discrepancy of Deterministic Random Walks on Grids ⋮ Consistency of Markov chain quasi-Monte Carlo on continuous state spaces ⋮ Deterministic random walks on regular trees ⋮ Deterministic walks with choice ⋮ Randomized diffusion for indivisible loads ⋮ Fast Simulation of Large-Scale Growth Models ⋮ The cover time of deterministic random walks for general transition probabilities ⋮ Infinite-step stationarity of rotor walk and the wired spanning forest ⋮ Does adding more agents make a difference? A case study of cover time for the rotor-router ⋮ Minimalist art from cellular automata ⋮ Discrete analog computing with rotor-routers ⋮ Deterministic random walks on finite graphs

Cites Work

• Unnamed Item
• Internal diffusion limited aggregation
• Internal diffusion-limited aggregation: parallel algorithms and complexity
• Goldbug variations
• Subdiffusive fluctuations for internal diffusion limited aggregation
• Deterministic random walks on the integers
• The rotor-router shape is spherical
• Simulating a Random Walk with Constant Error

This page was built for publication: Deterministic Random Walks on the Two-Dimensional Grid