Deterministic Random Walks on the Integers

Joshua Cooper; Benjamin Doerr; Joel Spencer; Gábor Tardos

doi:10.46298/dmtcs.3436

Joshua Cooper ; Benjamin Doerr ; Joel Spencer ; Gábor Tardos - Deterministic Random Walks on the Integers

dmtcs:3436 - Discrete Mathematics & Theoretical Computer Science, January 1, 2005, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05) - https://doi.org/10.46298/dmtcs.3436

Deterministic Random Walks on the IntegersArticle

Authors: Joshua Cooper ¹; Benjamin Doerr ²; Joel Spencer ¹; Gábor Tardos ³

1 Courant Institute of Mathematical Sciences [New York]
2 Max-Planck-Institut für Informatik
3 Alfréd Rényi Institute of Mathematics

We analyze the one-dimensional version of Jim Propp's $P$-machine, a simple deterministic process that simulates a random walk on $\mathbb{Z}$. The "output'' of the machine is astonishingly close to the expected behavior of a random walk, even on long intervals of space and time.

https://doi.org/10.46298/dmtcs.3436

Source: HAL:hal-01184393v1

Volume: DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)

Section: Proceedings

Published on: January 1, 2005

Imported on: May 10, 2017

Keywords: random walks,chip firing games.,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO]

Funding:

Source : OpenAIRE Graph

PostDoctoral Research Fellowship; Funder: National Science Foundation; Code: 0303272

Bibliographic References

27 Documents citing this article

Swee Hong Chan;Lionel Levine, 2022, Abelian networks IV. Dynamics of nonhalting networks, arXiv (Cornell University), 276, 1358, 10.1090/memo/1358, https://arxiv.org/abs/1804.03322.

Takeharu Shiraga, 2020, The cover time of deterministic random walks for general transition probabilities, arXiv (Cornell University), 815, pp. 153-162, 10.1016/j.tcs.2020.02.009, https://arxiv.org/abs/1602.07729.

Adrian Kosowski;Dominik Pająk, 2019, Does adding more agents make a difference? A case study of cover time for the rotor-router, Journal of Computer and System Sciences, 106, pp. 80-93, 10.1016/j.jcss.2019.07.001, https://doi.org/10.1016/j.jcss.2019.07.001.

Takeharu Shiraga;Yukiko Yamauchi;Shuji Kijima;Masafumi Yamashita, 2018, Deterministic Random Walks for Rapidly Mixing Chains, arXiv (Cornell University), 32, 3, pp. 2180-2193, 10.1137/16m1087667, https://arxiv.org/abs/1311.3749.

Tobias Friedrich;Maximilian Katzmann;Anton Krohmer, 2018, Unbounded Discrepancy of Deterministic Random Walks on Grids, SIAM Journal on Discrete Mathematics, 32, 4, pp. 2441-2452, 10.1137/17m1131088.

Takeharu Shiraga;Yukiko Yamauchi;Shuji Kijima;Masafumi Yamashita, 2017, Total variation discrepancy of deterministic random walks for ergodic Markov chains, Theoretical Computer Science, 699, pp. 63-74, 10.1016/j.tcs.2016.11.017, https://doi.org/10.1016/j.tcs.2016.11.017.

Hoda Akbari;Petra Berenbrink;Thomas Sauerwald, 2016, A simple approach for adapting continuous load balancing processes to discrete settings, Apollo (University of Cambridge), 29, 2, pp. 143-161, 10.1007/s00446-016-0266-y, https://www.repository.cam.ac.uk/handle/1810/292829.

Tobias Friedrich;Maximilian Katzmann;Anton Krohmer, Lecture Notes in Computer Science, Unbounded Discrepancy of Deterministic Random Walks on Grids, pp. 212-222, 2015, 10.1007/978-3-662-48971-0_19.

Trung Van Pham, 2015, Orbits of rotor-router operation and stationary distribution of random walks on directed graphs, Advances in Applied Mathematics, 70, pp. 45-53, 10.1016/j.aam.2015.06.006, https://doi.org/10.1016/j.aam.2015.06.006.

Adrian Kosowski;Dominik Pajak, Lecture Notes in Computer Science, Does Adding More Agents Make a Difference? A Case Study of Cover Time for the Rotor-Router, pp. 544-555, 2014, 10.1007/978-3-662-43951-7_46.

Benjamin Doerr;Tobias Friedrich;Thomas Sauerwald, 2014, Quasirandom Rumor Spreading, ACM transactions on algorithms, 11, 2, pp. 1-35, 10.1145/2650185, https://doi.org/10.1145/2650185.

Katy E. Beeler;Kenneth S. Berenhaut;Joshua N. Cooper;Meagan N. Hunter;Peter S. Barr, 2014, Deterministic walks with choice, Discrete Applied Mathematics, 162, pp. 100-107, 10.1016/j.dam.2013.08.031, https://doi.org/10.1016/j.dam.2013.08.031.

Shuji Kijima;Kentaro Koga;Kazuhisa Makino, 2014, Deterministic random walks on finite graphs, Random Structures & Algorithms, 46, 4, pp. 739-761, 10.1002/rsa.20533.

Takeharu Shiraga;Yukiko Yamauchi;Shuji Kijima;Masafumi Yamashita, Lecture Notes in Computer Science, L ∞ -Discrepancy Analysis of Polynomial-Time Deterministic Samplers Emulating Rapidly Mixing Chains, pp. 25-36, 2014, 10.1007/978-3-319-08783-2_3.

Yusuke Ide;Norio Konno;Masato Takei, 2014, Some basic properties of a rotor-router model with i.i.d. initial rotor-routers on the line, Proceedings of the ISCIE International Symposium on Stochastic Systems Theory and its Applications, 2014, 0, pp. 303-306, 10.5687/sss.2014.303, https://doi.org/10.5687/sss.2014.303.

Hoda Akbari;Petra Berenbrink, Proceedings of the twenty-fifth annual ACM symposium on Parallelism in algorithms and architectures, Parallel rotor walks on finite graphs and applications in discrete load balancing, 2013, Montréal Québec Canada, 10.1145/2486159.2486178.

Shuji Kijima, 2013, Randomness in algorithm design, Journal of Physics: Conference Series, 473, pp. 012014, 10.1088/1742-6596/473/1/012014, https://doi.org/10.1088/1742-6596/473/1/012014.

Tobias Friedrich;Lionel Levine, 2012, Fast simulation of large‐scale growth models, arXiv (Cornell University), 42, 2, pp. 185-213, 10.1002/rsa.20412, https://arxiv.org/abs/1006.1003.

Juliana Freire;Joel Spencer, 2011, Proppian random walks in Z, Discrete mathematics, 311, 5, pp. 349-361, 10.1016/j.disc.2010.11.001.

Omer Angel;Alexander E. Holroyd, 2011, Rotor Walks on General Trees, arXiv (Cornell University), 25, 1, pp. 423-446, 10.1137/100814299.

Tobias Friedrich;Lionel Levine, arXiv (Cornell University), Fast Simulation of Large-Scale Growth Models, pp. 555-566, 2011, 10.1007/978-3-642-22935-0_47, http://arxiv.org/abs/1006.1003.

Alexander E. Holroyd;James Propp, 2010, Rotor walks and Markov chains, Contemporary mathematics, pp. 105-126, 10.1090/conm/520/10256, https://doi.org/10.1090/conm/520/10256.

James Propp, 2010, Discrete analog computing with rotor-routers, arXiv (Cornell University), 20, 3, 10.1063/1.3489886, https://arxiv.org/abs/1007.2389.

Joshua Cooper;Benjamin Doerr;Tobias Friedrich;Joel Spencer, 2010, Deterministic random walks on regular trees, arXiv (Cornell University), 37, 3, pp. 353-366, 10.1002/rsa.20314, https://arxiv.org/abs/1006.1441.

Tobias Friedrich;Thomas Sauerwald, arXiv (Cornell University), The Cover Time of Deterministic Random Walks, pp. 130-139, 2010, 10.1007/978-3-642-14031-0_16, https://arxiv.org/abs/1006.3430.

Benjamin Doerr;Tobias Friedrich, 2009, Deterministic Random Walks on the Two-Dimensional Grid, Combinatorics, Probability & Computing, 18, 1-2, pp. 123-144, 10.1017/s0963548308009589.

Leszek Gąsieniec;Tomasz Radzik, CiteSeer X (The Pennsylvania State University), Memory Efficient Anonymous Graph Exploration, pp. 14-29, 2008, 10.1007/978-3-540-92248-3_2, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.392.6737.

Sources : OpenCitations, OpenAlex & Crossref

Share and export

Consultation statistics

This page has been seen 165 times.

This article's PDF has been downloaded 173 times.