We analyze Jim Propp's P -machine, a simple deterministic process that simulates a random walk on Z d to within a constant. The proof of the error bound relies on several estimates in the theory of simple random walks and some careful summing. We mention three intriguing conjectures concerning signchanges and unimodality of functions in the linear span of {p(·, x) : x ∈ Z d }, where p(n, x) is the probability that a walk beginning from the origin arrives at x at time n. Consider the following machine, which we call the P -machine after its progenitor, Jim Propp. We begin with a set of chips on "even" vertices of Z d , i.e., those an even L 1 -distance from the origin. We label by Z 2d = {0, 1, . . . , 2d − 1} the 2d directions of Z d . (For example: North, South, East and West for d = 2.) On each vertex v there will be a "rotor" which will have a state j ∈ Z 2d . The initial states of the rotors can be set arbitrarily. The rotors work as follows: when one feeds it a chip, a rotor changes to state j + 1 (addition in Z 2d ) and sends the chip to the vertex in direction j. Each time unit we feed all of the chips currently on each vertex to the rotor on that vertex. The result is a new distribution of chips. We imagine doing this operation for total time n. Now, consider the following process. We again begin with a set of chips on "even" vertices of Z d . Each chip takes an n-step simple random walk from its starting point. At time n, we expect that the P -machine and the random process should give rise to similar distributions if they begin with the same configuration of chips. For the random walk process we may consider the expected number of chips that will be at v at time n. Our main result is that the difference between this expected number and the actual number at v at time n in the deterministic P -machine is bounded uniformly -irrespective of how much time has passed, what the original chip distribution was, the starting states of the rotors, or even the choice of v! *
Cooper and Spencer REF studied d-dimensional grid graphs, showing a constant bound on the difference between the number of tokens at a given node v in the rotorrouter model and the expected number of tokens at v in the random-walk model.
Simulating a Random Walk with Constant Error
Combinatorics, Probability & Computing
Computer Science Mathematics