Random walk and random aggregation, derandomized
This talk will describe a general recipe for replacing discrete stochastic processes by deterministic analogues that satisfy the same first-order limit laws but have smaller fluctuations. The recipe will be applied to several illustrative problems in the study of random walk and random aggregation. In particular, a derandomized version of the internal diffusion-limited aggregation model in two dimensions gives rise to a growing blob that is remarkably close to circular and also displays intriguing internal structures (see http://www.math.wisc.edu/~propp/million.gif). This is joint work with Ander Holroyd and Lionel Levine.
An early write-up of derandomized aggregation:
Email-log of some messages I sent out about derandomized walk:
Lionel Levine’s undergraduate thesis:
Slides from a talk given by Lionel Levine:
Lionel Levine and Adam Kampff’s picture of the rotor-router aggregation blob after 270,000 particles have aggregated:
Two close-ups of that same picture:
Ed Pegg’s picture of the rotor-router blob after 750,000 particles have aggregated:
Ander Holroyd’s picture of the rotor-router blob after 1,000,000 particles have aggregated:
Vishal Sanwalani’s picture of the state achieved by the abelian sandpile model when sixty thousand grains have been added:
Hal Canary’s applets for demonstrating derandomized walk and aggregation:
James Propp is an Associate Professor in the Department of Mathematics at the University of Wisconsin at Madison. His research interests are in combinatorics, probability, and dynamical systems.
- James Propp
- University of Wisconsin