## Abstract

The rotor-router model, also known as the Propp machine, is a deterministic process analogous to a random walk on a graph. Instead of distributing tokens to randomly chosen neighbors, the Propp machine deterministically serves the neighbors in a fixed order by associating to each vertex a "rotor-router" pointing to one of its neighbors. This paper investigates the discrepancy at a single vertex between the number of tokens in the rotor-router model and the expected number of tokens in a random walk, for finite graphs in general. We show that the discrepancy is bounded by O (mn) at any time for any initial configuration if the corresponding random walk is lazy and reversible, where n and m denote the numbers of nodes and edges, respectively. For a lower bound, we show examples of graphs and initial configurations for which the discrepancy at a single vertex is Ω(m) at any time (> 0). For some special graphs, namely hypercube skeletons and Johnson graphs, we give a polylogarithmic upper bound, in terms of the number of nodes, for the discrepancy.

Original language | English |
---|---|

Pages (from-to) | 739-761 |

Number of pages | 23 |

Journal | Random Structures and Algorithms |

Volume | 46 |

Issue number | 4 |

DOIs | |

Publication status | Published - Jul 1 2015 |

## All Science Journal Classification (ASJC) codes

- Software
- General Mathematics
- Computer Graphics and Computer-Aided Design
- Applied Mathematics