Richardson's model

This is perhaps the simplest possible model. Each site in the square lattice is either occupied (in state 1) or vacant (in state 0).

(i) A site once occupied stays occupied forever.

(ii) A vacant site becomes occupied at a rate equal to the fraction of the four nearest neighbors that are occupied.

If we start with only the origin occupied at time 0 then each site in lattice will eventually become occupied (and remain occupied forever). Things get interesting when we we let B(t) be the set of lattice points occupied at time t ask

At what rate does the blob B(t) grow?

Eden (1961) was the first to ask this question, but the solution remained elusive until Richardson (1973) showed

Theorem. B(t)/t has a limiting shape, which is roughly but not exactly circular.

s3 Exercise. Check the last theorem by running the model starting from a single occupied site. (Choose the initial condition "rectangle" and set the height and width equal to 1.)

Sketch of Proof. The first step in Richardson's asymptotic shape result is to show that if t(n,0) is the first time the point (n,0) is occupied then t(n,0)/n converges to a constant c(1,0). This is accomplished by using the subadditive ergodic theorem. For details, see e.g., Smythe and Wierman (1977), Cox and Durrett (1981), or Kesten (1986).

Research Problem. Having a law of large numbers for t(n,0) it is natural to ask if there is a central limit theorem. Before you say "of course", we would like to note that simulations (Zabolitsky and Stauffer (1986), Wolf and Kertesz (1987)) suggest the standard deviation of t(n,0) is of order n^{1/3}, i.e., n to the one third power, instead of the usual square root of n. There are some heuristic arguments in support of this result. See e.g., Kardar, Parisi, and Zhang (1986). However, all that is known rigorously is that the fluctuations are no worse than square root of n. See Kesten (1993) and Alexander (1993), and the related work reported on in Newman (1994).

Eden, M. (1961) A two dimensional growth process. Proc. 4th Berkeley Symp., IV, 222-239

Richardson, D. (1973) Random growth in a tesselation. Proc. Camb. Phil. Soc. 74, 515-528

Smythe, R. and Weirman, J.C. (1977) First Passage Percolation On The Square Lattice. Springer Lecture Notes in Math 671

Cox, J.T. and Durrett, R. (1981) Some limit theorems for first passage percolation with necessary and sufficient conditions. Ann. Prob. 9, 583-603

Kesten, H. (1986) Aspects of First Passage Percolation. In Springer Lecture Notes in Math 1180

Kardar, M., Parisi, G., and Zhang, Y.C. (1986) Dynamic scaling fo growing interfaces. Phys. Rev. Letters. 56, 889-892

Zabolitsky, J.G. and Stauffer, D. (1986) Simulation of large Eden clusters. Phys. Rev. A 34, 1523-1530

Wolf, D. and Kertesz, J. (1987) Noise reduction in Eden models. J. Phys. A 20, L257-L261

Kesten, H. (1993) On the speed of convergence in first passage percolation. Ann. Appl. Prob. 3, 296-338

Alexander, K. (1993) A note on some rates of convergence in first-passage percolation. Ann. Appl. Prob. 3, 81-90

Newman, C. (1994) A surface view of first passage percolation. Proc. Int. Congress of Math, Zurich.

On to the next page or back to the survey contents page