Proppian random walks in ℤ

Juliana Freire, Joel Spencer

Research output: Contribution to journalArticlepeer-review


The Propp Machine is a deterministic process that simulates a random walk. Instead of distributing chips randomly, each position makes the chips move according to the walk's possible steps in a fixed order. A random walk is called Proppian if at each time at each position the number of chips differs from the expected value by at most a constant, independent of time or the initial configuration of chips. The simple walk where the possible steps are 1 or -1 each with probability p=12 is Proppian, with constant approximately 2.29. The equivalent simple walks on Zd are also Proppian. Here, we show the same result for a larger class of walks on Z, allowing an arbitrary number of possible steps with some constraint on their probabilities.

Original languageEnglish (US)
Pages (from-to)349-361
Number of pages13
JournalDiscrete Mathematics
Issue number5
StatePublished - Mar 6 2011


  • Derandomization
  • Propp machine
  • Random walk

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Proppian random walks in ℤ'. Together they form a unique fingerprint.

Cite this