Proppian random walks in ZZ

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−1 each with probability p=12 is Proppian, with constant approximately 2.29. The equivalent simple walks on ZdZd are also Proppian. Here, we show the same result for a larger class of walks on ZZ, allowing an arbitrary number of possible steps with some constraint on their probabilities.