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 IntegersConference paper

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: [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], [en] random walks, chip firing games.

Funding:

Source : OpenAIRE Graph

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

Bibliographic References

25 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, http://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, http://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, 106, pp. 80-93, 10.1016/j.jcss.2019.07.001, https://inria.hal.science/hal-00950743.

Takeharu Shiraga;Yukiko Yamauchi;Shuji Kijima;Masafumi Yamashita, 2018, Deterministic Random Walks for Rapidly Mixing Chains, SIAM Journal on Discrete Mathematics, 32, 3, pp. 2180-2193, 10.1137/16m1087667.

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, 2016, 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.

Tobias Friedrich;Maximilian Katzmann;Anton Krohmer, 2015, Unbounded Discrepancy of Deterministic Random Walks on Grids, Lecture notes in computer science, pp. 212-222, 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, arXiv (Cornell University), 70, pp. 45-53, 10.1016/j.aam.2015.06.006, http://arxiv.org/abs/1403.5875.

Adrian Kosowski;Dominik Pająk, 2014, Does Adding More Agents Make a Difference? A Case Study of Cover Time for the Rotor-Router, Lecture notes in computer science, pp. 544-555, 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.

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

Takeharu Shiraga;Yukiko Yamauchi;Shuji Kijima;Masafumi Yamashita, 2014, L ∞ -Discrepancy Analysis of Polynomial-Time Deterministic Samplers Emulating Rapidly Mixing Chains, Lecture notes in computer science, pp. 25-36, 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, 2013, Parallel rotor walks on finite graphs and applications in discrete load balancing, Proceedings of the twenty-fifth annual ACM symposium on Parallelism in algorithms and architectures, pp. 186-195, 10.1145/2486159.2486178.

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

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, Random Structures and Algorithms, 42, 2, pp. 185-213, 10.1002/rsa.20412.

Omer Angel;Alexander E. Holroyd, 2011, Rotor Walks on General Trees, SIAM Journal on Discrete Mathematics, 25, 1, pp. 423-446, 10.1137/100814299.

Tobias Friedrich;Lionel Levine, 2011, Fast Simulation of Large-Scale Growth Models, Lecture notes in computer science, pp. 555-566, 10.1007/978-3-642-22935-0_47.

Alexander E. Holroyd;James Propp, 2010, Rotor walks and Markov chains, Contemporary mathematics - American Mathematical Society, pp. 105-126, 10.1090/conm/520/10256.

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

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

Tobias Friedrich;Thomas Sauerwald, 2010, The Cover Time of Deterministic Random Walks, Lecture notes in computer science, pp. 130-139, 10.1007/978-3-642-14031-0_16.

Leszek Gąsieniec;Tomasz Radzik, 2008, Memory Efficient Anonymous Graph Exploration, Lecture notes in computer science, pp. 14-29, 10.1007/978-3-540-92248-3_2.

Joshua Cooper;Benjamin Doerr;Tobias Friedrich;Joel Spencer, 2007, Deterministic Random Walks on Regular Trees, arXiv (Cornell University), 29, 3, pp. 509-513, 10.1002/rsa.20314, http://arxiv.org/abs/1006.1441.

Sources : OpenCitations, OpenAlex & Crossref

Share and export

Consultation statistics

This page has been seen 317 times.

This article's PDF has been downloaded 278 times.