IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

The P-Machine, A Random-Like Deterministic Process

  • Jan. 25, 2019
  • 2:30 p.m.
  • LeConte 312


The P-machine, also known as the 'rotor router model', is a simple deterministic process that simulates a random walk on a graph. Instead of distributing chips to randomly chosen neighbors, it serves the neighbors in a fixed order. It turns out that this process simulates a random walk surprisingly well. For example, on the infinite path, independent of the starting configuration, at each time and on each vertex, the number of chips on this vertex deviates from the expected number of chips in the random walk model by at most a constant C, which is approximately 2.29. We discuss this and several related results, and more recent developments.

© Interdisciplinary Mathematics Institute | The University of South Carolina Board of Trustees | Webmaster