Rotor-Router Model

 

 

Rotor-router aggregate of 270,000 particles. 

Description:

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.
 

References:

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