Deterministic Random Walks on Regular Trees

Joshua Cooper, Benjamin Doerr, Tobias Friedrich, Joel Spencer

Research output: Contribution to journalArticlepeer-review

Abstract

Jim Propp's rotor router model is a deterministic analogue of a random walk on a graph. Instead of distributing chips randomly, each vertex serves its neighbors in a fixed order. The difference between the Propp machine and a random walk has been analyzed on infinite d-dimensional grids. There, apart from a technicality, independent of the starting configuration, at each time, the number of chips on each vertex in the Propp model deviates from the expected number of chips in the random walk model by at most a constant. We show that this is not the case for the k-regular tree (k ≥ 3), i.e., there is a starting configurations on which both models deviate by an arbitrarily large number of chips.

Original languageEnglish (US)
Pages (from-to)509-513
Number of pages5
JournalElectronic Notes in Discrete Mathematics
Volume29
Issue numberSPEC. ISS.
DOIs
StatePublished - Aug 15 2007

Keywords

  • chip firing games
  • discrepancy
  • random walk
  • rotor-router model

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Deterministic Random Walks on Regular Trees'. Together they form a unique fingerprint.

Cite this