The Rotor-router model and Diaconis-Fulton Addition

  • Date: 11/27/2006
Lecturer(s):

Yuval Peres (Microsoft Research)

Location: 

University of British Columbia

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.)

Other Information: 

Probability Seminar 2006

Sponsor: 

pims