## Abstract

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 language | English (US) |
---|---|

Pages (from-to) | 349-361 |

Number of pages | 13 |

Journal | Discrete Mathematics |

Volume | 311 |

Issue number | 5 |

DOIs | |

State | Published - Mar 6 2011 |

## Keywords

- Derandomization
- Propp machine
- Random walk

## ASJC Scopus subject areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics