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.
- Propp machine
- Random walk
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics