## Abstract

Jim Propp's rotor router model is a deterministic analogue of a random walk on a graph. Instead of distributing chips randomly, each vertex serves its neighbors in a fixed order. The difference between the Propp machine and a random walk has been analyzed on infinite d-dimensional grids. There, apart from a technicality, independent of the starting configuration, at each time, the number of chips on each vertex in the Propp model deviates from the expected number of chips in the random walk model by at most a constant. We show that this is not the case for the k-regular tree (k ≥ 3), i.e., there is a starting configurations on which both models deviate by an arbitrarily large number of chips.

Original language | English (US) |
---|---|

Pages (from-to) | 509-513 |

Number of pages | 5 |

Journal | Electronic Notes in Discrete Mathematics |

Volume | 29 |

Issue number | SPEC. ISS. |

DOIs | |

State | Published - Aug 15 2007 |

## Keywords

- chip firing games
- discrepancy
- random walk
- rotor-router model

## ASJC Scopus subject areas

- Discrete Mathematics and Combinatorics
- Applied Mathematics