Mathematics Colloquium

From Diaconis-Fulton Addition to a Free Boundary Problem

Speaker: Yuval Peres, Microsoft Research

Location: Warren Weaver Hall 1302

Date: Monday, March 2, 2009, 3:45 p.m.


Start with n particles at each of k points in the d‐dimensional lattice, and let each particle perform simple random walk until it reaches an unoccupied site. The law of the resulting random set of occupied sites does not depend on the order in which the walks are performed, as shown by Diaconis and Fulton. We prove that if the distances between the starting points are scaled by the d'th root of n, then the set of occupied sites has a deterministic scaling limit. In two dimensions, the boundary of the limiting shape is an algebraic curve of degree 2k. (For k = 1 it is a circle, as proved in 1992 by Lawler, Bramson and Griffeath.) The limiting shape can also be described in terms of a free‐boundary problem for the Laplacian and quadrature identities for harmonic functions. I will show simulations of the process, that suggest an intriguing conjectured relation with conformal mapping.

(Joint work with Lionel Levine.)