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 Integers

Authors: Joshua Cooper ORCID-iD1; Benjamin Doerr ORCID-iD2; Joel Spencer 1; Gábor Tardos ORCID-iD3

  • 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

Linked publications - datasets - softwares

Source : ScholeXplorer IsRelatedTo ARXIV 0910.1077
Source : ScholeXplorer IsRelatedTo DOI 10.48550/arxiv.0910.1077
  • 10.48550/arxiv.0910.1077
  • 0910.1077
Discrete low-discrepancy sequences

Share and export

Consultation statistics

This page has been seen 141 times.
This article's PDF has been downloaded 146 times.