Given an arbitrary graph, a random walk of a chip is a path, which begins at a given starting point and chooses the next node with equal probability out of the set of its current neighbors. Random walks have been used to model a wide variety of processes in economics, physics, medicine, and mathematics.

Five years ago, James Propp invented a quasirandom analogue of random walk. He called this the "Rotor router model", while Joel Spencer coined the term "Propp machine". Instead of distributing chips to randomly chosen neighbors, it deterministically serves the neighbors in a fixed order by associating to each vertex a "rotor" pointing to one of its neighbors. The first chip reaching a vertex moves on in the direction the rotor is pointing, then the rotor direction is updated to the next direction in some cyclic ordering. The second chip is then send in this new direction, the rotor is updated, and so on. This ensures that the chips are distributed highly evenly among the neighbors, similar to (and in fact better than) what a random walk would have done.

The central question of all research on the Propp machine is how well the Propp machine simulates a random walk. A number of aspects have been regarded to far.


Discrepancy

Suppose we put some number of chips on each vertex. What difference does it make if they all do a random walk or a rotor router walk? More precisely, in the Propp model one time step consists of each chip (order irrelevant) doing one rotor guided jump to a neighbor (including the update of the rotor direction). After a certain number of time steps, we compare the actual number of chips on some vertex in the Propp model with the expected number of chips in the random walk model ("discrepancy" on this vertex at this time).

This problem has been studied by different researchers. It is easy to see that on finite graphs, the discrepancy on a single vertex is bounded by a constant (independent of the number of chips we used in total). This is not true for all infinite graphs, but (some technicalities aside) for the infinite grid Z^d. This has been proven by Cooper and Spencer.

For the infinite line Z¹, Cooper, Doerr, Spencer and Tardos among other results, showed that this constant is 2.29. For Z², Doerr and Friedrich discovered that this constant is approximately 7.8, if all vertices serve their neighbors in clockwise or counterclockwise order and 7.3 otherwise. This result in particular shows that the order in which the neighbors are served makes a difference. Note that this is not an issue in the one-dimensional case, where there is only one permutation (alternating left and right). This result raises the question if all graphs do have this property. Cooper, Doerr, Friedrich and Spencer were able to answer this question negatively. For the graph being an infinite regular tree, they show that the deviation can be unbounded.


Aggregating Model

Jim Propp has compared the rotor router model and the random walk in terms of the internal diffusion-limited aggregation model. Here, each chip (one after the other) starts at the origin, runs until it reaches an unoccupied vertex and occupies it. The question is how the set of occupied vertices looks like. It is natural to expect it to be some circular shape for both random walk and Propp walk.

Lawler et al. showed in 1992 that the limiting shape is indeed a Euclidean ball for the random model. Let us denote by r_n the largest radius of a ball containing no unoccupied vertex, and by R_n the smallest radius of a ball containing all occupied vertices. Then Lawler proved that with high probability the difference between these two radii is bounded by O(n^1/6). However, Moore and Machta experimentally observed that these error terms were much smaller, namely of logarithmic size. Again, for the aggregating Propp model much less is known. Levine and Peres proved that the shape of this model converges to a Euclidean ball (in the sense that the symmetric difference of the actual shape of n occupied vertices and the ball of appropriate radius has cardinality O(n^5/6). Levine shows that after n chips, the "Propp circle" contains a disk whose radius grows as n^1/4. In other words, r_n is at least of the order of n^1/4. A nice Java-applet demonstrating this can be found here and here. Propp circles with one million chips are shown in the following figures (click on the picture to zoom). The color indicates in which direction the rotor is pointing.

←↓↑→ (best):

←↓→↑ (clockwise):

←→↓↑ (worst):

Kleber discovered experimentally that after three million chips, R_n and r_n differ by less than two. Surprisingly, the precise difference again depends on the chosen rotor sequence. The following chart shows R_n-r_n for varying n. The different colors represent different rotor sequences and the black lines are the moving averages. Till n=3Mio, the maximum of R_n-r_n is 1.21, 1.74, and 1.96 for the three different rotor sequences.