DMTCS Proceedings, 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)

Font Size:  Small  Medium  Large

Deterministic Random Walks on the Integers

Joshua Cooper, Benjamin Doerr, Joel Spencer, Gábor Tardos


We analyze the one-dimensional version of Jim Propp's P-machine, a simple deterministic process that simulates a random walk on ℤ. The ``output'' of the machine is astonishingly close to the expected behavior of a random walk, even on long intervals of space and time.

Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page

Valid XHTML 1.0 Transitional