Rotor-router aggregate of 270,000 particles.

The rotor-router model is a deterministic analogue of random walk invented by
Jim Propp. It can be used to define a deterministic aggregation model analogous
to internal diffusion limited aggregation. We prove [4] an isoperimetric
inequality for the exit time of simple random walk from a finite region in Z^{d},
and use this to prove that the shape of the rotor-router aggregation model in Z^{d},
suitably rescaled, converges to a Euclidean ball in R^{d}.

Given a finite region A in Z^{d}, let A' be the (random) region
obtained by starting a random walk at the origin, stopping the walk when it
first exits A, and adjoining the endpoint of the walk to A. Internal diffusion
limited aggregation (``internal DLA'') is the growth model obtained by iterating
this procedure starting from the set containing only the origin: A1 = {(0,0)}, A_{n}
= (A_{n-1})'. Lawler et al. [2] showed that the region A_{n},
rescaled by a factor of n^{1/d}, converges with probability one to a
Euclidean ball in R^{d} as n approaches infinity. Lawler [3] estimated
the rate of convergence.

Jim Propp has proposed the following deterministic analogue of internal DLA in
two dimensions. At each site x in A is a ``rotor'' pointing North, East, South
or West. A particle is placed at the origin and performs* rotor-router walk*
until it exits the region A: during each time step, the rotor at the particle's
current location is rotated clockwise by 90 degrees, and the particle takes a
step in the direction of the newly rotated rotor. The intent of this rule is to
simulate the first-order properties of random walk by forcing each site to route
approximately equal numbers of particles to each of the four neighboring sites.
When the particle reaches a point not in A, that point is adjoined to the region
and the procedure is iterated to obtain a sequence of regions A_{n}. For
example, if all rotors are initially pointing north, the sequence will be begin
A_{1} = {(0,0)}, A_{2} = {(0,0),(1,0)}, A_{3} =
{(0,0),(1,0),(0,-1)}, etc.

In [4], we prove a shape theorem for the rotor-router model analogous to that
for internal DLA. Denote by sym(R,S) the symmetric difference of sets R
and S. For a region A in Z^{d}, we write A* for the union of
closed unit cubes in R^{d} centered at the points of A. We write *L*
for d-dimensional Lebesgue measure. We prove the following:

**Theorem:** Let (A_{n})_{n > 1} be rotor-router
aggregation in Z^{d}, starting from any initial configuration of rotors.
Then as n tends to infinity *L*( n^{-1/d }sym^{(}A_{n}*,
B) ) converges to zero, where B is the ball of unit volume centered at the
origin in R^{d}.

- Internal diffusion limited aggregation. (G. F. Lawler, M. Bramson,
and D. Griffeath).
*Ann. Probab.***20**(1992) no.4, 2117--2140. - Subdiffusive fluctuations for internal diffusion limited aggregation.
(G. F. Lawler).
*Ann. Probab.***23**(1995) no. 1, 71--86. -
Spherical Asymptotics for the
Rotor-Router Model in Z
^{d}. (L. Levine and Y. Peres). Preprint.