The Rotor-router model and Diaconis-Fulton Addition
Topic
Given two sets A and B in the lattice, the Diaconis-Fulton sum is a
random set obtained by putting one particle in every point of the
symmetric difference, and two particles in every point of the
intersection, of A and B. Each 'extra particle' performs random walk
until it reach an unoccupied site, where it settles. The law of the
resulting random occupied set A+B does not depend on the order of the
walks. We find the (deterministic) scaling limit of the sums A+B when A
and B consist of the lattice points in some overlapping planar domains.
The limit is described by focusing on the 'odometer' of the process,
which solves a free boundary obstacle problem for the Laplacian.
The same scaling limit is obtained when the random walks are replaced by deterministic rotor walks, as proposed by Jim Propp. In particular, when a singleton at the origin is added to itself n times Internal Diffusion-limited aggregation (IDLA) arises; Lawler, Bramson and Griffeath (1992) proved the limit shape for IDLA is a disk and we prove the analogous result for rotor-router aggregation. (Joint work with Lionel Levine.)
The same scaling limit is obtained when the random walks are replaced by deterministic rotor walks, as proposed by Jim Propp. In particular, when a singleton at the origin is added to itself n times Internal Diffusion-limited aggregation (IDLA) arises; Lawler, Bramson and Griffeath (1992) proved the limit shape for IDLA is a disk and we prove the analogous result for rotor-router aggregation. (Joint work with Lionel Levine.)
Speakers
Additional Information
Probability Seminar 2006
Yuval Peres (Microsoft Research)
Yuval Peres (Microsoft Research)