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.