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:
- 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 Zd. (L. Levine and Y. Peres). Preprint.