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:

www.math.wisc.edu/~propp/hidden/rotor

Email-log of some messages I sent out about derandomized walk:

www.math.wisc.edu/~propp/hidden/test/rotorwalk.to

Lionel Levine’s undergraduate thesis:

www.math.berkeley.edu/~levine/rotorrouter.pdf

Slides from a talk given by Lionel Levine:

www.math.berkeley.edu/~levine/slides/

Lionel Levine and Adam Kampff’s picture of the rotor-router aggregation blob after 270,000 particles have aggregated:

www.math.berkeley.edu/~levine/private/rotorrouter/bigblob.bmp

Two close-ups of that same picture:

www.math.berkeley.edu/~levine/private/rotorrouter/closeup.bmp

Ed Pegg’s picture of the rotor-router blob after 750,000 particles have aggregated:

www.math.wisc.edu/~propp/proppcircle.gif

Ander Holroyd’s picture of the rotor-router blob after 1,000,000 particles have aggregated:

www.math.wisc.edu/~propp/million.gif

Vishal Sanwalani’s picture of the state achieved by the abelian sandpile model when sixty thousand grains have been added:

www.math.wisc.edu/~propp/hidden/501.gif

Hal Canary’s applets for demonstrating derandomized walk and aggregation:

http://ups.physics.wisc.edu/~hal/SSL/2003/