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 Zd, and use this to prove that the shape of the rotor-router aggregation model in Zd, suitably rescaled, converges to a Euclidean ball in Rd.
Given a finite region A in Zd, 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)},
An = (An-1)'. Lawler et al. [2] showed that the region
An, rescaled by a factor of n1/d, converges with
probability one to a Euclidean ball in Rd 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 An. For example, if all
rotors are initially pointing north, the sequence will be begin A1 =
{(0,0)}, A2 = {(0,0),(1,0)}, A3 = {(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 Zd, we write A* for the union of
closed unit cubes in Rd centered at the points of A. We write
L for d-dimensional Lebesgue measure. We prove the
following:
Theorem: Let (An)n >
1 be rotor-router aggregation in Zd, starting from any
initial configuration of rotors. Then as n tends to infinity L(
n-1/d sym(An*, B) ) converges to zero, where B
is the ball of unit volume centered at the origin in
Rd.