Random Recipe

Introduction to the PSK PSK Search Recent Additions CA Archive CA Links Feedback Appreciated !
Take me higher...

About the Particle Postcards

Main Kitchen postcard: Bootstrap percolation

Start with a random density p of occupied sites (1's on a background of 0's). At each update an empty site becomes occupied if it sees at least two previously occupied sites among its four nearest neighbors (N,S,E,W). Under these dynamics an isolated rectangle of occupied sites cannot grow, but any occupied region that is not convex must continue to grow. By superimposing the resulting dynamics for varying values of p, and color coding stable regions for small p with oranges and yellows and larger nucleating regions for large p with blues and greens, we obtain a striking image of nucleation. For more on the mathematics of this rule, see Aizenman, M. and Lebowitz, J. (1988) "Metastability effects in bootstrap percolation." J. Phys. A: Math. Gen. 21, 3801-3813.

Come On In postcard: A Cyclic Smoothing Process

Choose a cyclic palette in which neighboring colors differ imperceptibly. Our wheel consists of a smooth spectrum of greens and blues suggestive of primordial soup. The asynchronous interaction rule is to replace the colors of two neighboring sites by their "average," following the shorter route around the color wheel. Starting from a random configuration we see a simultaneous process of clustering and self-organization. The averaging causes nearby colors to cluster. But since there is no bias toward any region of the spectrum, the result is a homogeneous continuous flow with a "water color" feel, marked by vortices known as 'defects.' This simple rule is related to the Heisenberg model of statistical physics.

Recent Additions postcard: A Directed Random Interface from Consensus

This postcard depicts the same experiment as the previous one, except that time progresses downward and the initial configuration at the top is totally synchronized (note the flat red stripe). Thus the randomness rapidly disorganizes the wave front in this case, after which the dynamics settle into the same equilibrium as before. A multicolor palette facilitates visualization of the interface level sets.

Search postcard: The Stepping Stone Model in One Dimension

Here we see a space-time picture of the one-dimensional counterpart to the system of the previous postcard. Each horizontal slice represents the configuration at a certain time; the initial state is at the top, and the subsequent evolution proceeds down the card. The dynamics are analogous to those above, except that (i) there are only two neighbors on the line (left, right), and (ii) the rule is synchronous, meaning that each site chooses one of two neighbors at random, and then all repainting occurs simultaneously. The spreading which occurs as we move down the image is one-dimensional clustering. Actually all the cells at the top were colored with random intensities of either red or blue but, due to the parallel updating, colors interweave to produce a nice collage effect. (Fine checkerboards such as these are called dithers or dibbles in the graphics world.)

Shelf postcard: The Stepping Stone Model in Two Dimensions

This process goes back to population geneticist Sewall Wright in the early 1940's. To make the soup we start from a random configuration, using a palette of more than 32,000 colors. Then we impose a supremely simple iterative rule: choose a site at random from the whole array, choose one of its four nearest neighbors, and give the former cell the color of the latter. In other words, a random site "eats" a random neighbor. Over time increasingly large regions of solid color are formed until one species takes over any finite region. For a nice treatment of this class of processes, also known as voter models, see Durrett, R. Lecture Notes on Particle Systems and Percolation. Wadsworth & Brooks/Cole, Pacific Grove CA, 1988

Sink postcard: A Directed Random Interface from Disorder

Imagine a row of soldiers marching across a field, or alternatively a linear array of processors performing some computation in parallel. Each individual or machine proceeds at the same rate, subject to random fluctuations, except that anyone ahead of a neighbor must wait until that neighbor catches up. This simple prescription defines a cellular automaton directed interface model that exhibits "hydrodynamic" effects leading to an interesting self-organized equilibrium profile. When the initial distribution of positions is highly disordered, so that alignment occurs over time (moving up), we obtain an interesting pseudo-3d effect. For a theoretical discussion see my paper, "Self-Organization of Random Cellular Automata: four snapshots." In Probability and Phase Transition, ed. G. Grimmett. Kluwer, Dordrecht, 1994, 49-67.

Take me higher...
Introduction to the PSK PSK Search Recent Additions CA Archive CA Links Feedback Appreciated !