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 ORCID1; Benjamin Doerr ORCID2; Joel Spencer 1; Gábor Tardos ORCID3

  • 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.


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

27 Documents citing this article

Consultation statistics

This page has been seen 165 times.
This article's PDF has been downloaded 174 times.