Simulating a random walk with constant error

Joshua N. Cooper, Joel Spencer

Research output: Contribution to journalArticlepeer-review


We analyse Jim Propp's P-machine, a simple deterministic process that simulates a random walk on ℤ d to within a constant. The proof of the error bound relies on several estimates in the theory of simple random walks and some careful summing. We mention three intriguing conjectures concerning sign-changes and unimodality of functions in the linear span of {p(.,x): x ∈ ℤ d}where p(n, x) is the probability that a walk beginning from the origin arrives at x at time n.

Original languageEnglish (US)
Pages (from-to)815-822
Number of pages8
JournalCombinatorics Probability and Computing
Issue number6
StatePublished - Nov 2006

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Statistics and Probability
  • Computational Theory and Mathematics
  • Applied Mathematics


Dive into the research topics of 'Simulating a random walk with constant error'. Together they form a unique fingerprint.

Cite this