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.