Bootstrap Percolation
(Scroll down for information about the picture...)
What is this?
We start with a square array of 300 by 300
smaller squares, called "sites". Initially, 5% of the sites are
chosen at random to be "infected" - these sites are coloured red.
The picture then evolves in discrete time steps according to the
following rules. Infected sites remain infected for ever. A
currently uninfected site becomes infected at the next time step if at
least two of its four nearest neighbours are currently infected. In
the particular experiment above, the entire square eventually became
infected. The picture shows the time at which sites became infected:
initially infected sites are red, subsequent
infections are black (earliest),
followed by dark blue, light blue, green, yellow, and finally white (latest).
Mathematics
What determines whether the entire square eventually becomes infected?
Clearly it depends of the size of the square and the proportion of
sites initially infected, but how exactly? In the case of very large
squares, the following answer is proved in [6].
Consider a series of experiments in which the size of the square
becomes larger and larger indefinitely. Fix a number c, and
adjust the initial proportions of infected sites so that when the
square is L by L sites, the proportion is
c / ln(L). (Here "ln" is the natural logarithm). Then,
in the limit as the square become large, the probability that it will
become entirely infected approaches 1 (certainty) if c>&lambda, or 0
(certain not to happen) if c<&lambda, where
&lambda = &pi2 / 18 = 0.548311...
Theory versus Experiment
The model seems ideal for computer simulation.
Surprisingly however, simulation results can lead to misleading
predictions about limiting behaviour (or vice-versa, depending on one's
perspective). Simulations in [2] involving squares up to 28,800 by
28,800 (nearly a billion sites) resulted in the prediction
&lambda = 0.245 ± 0.015,
different from the rigorous value above by more than a factor of two!
The reason for the discrepancy seems to be that the convergence to the
limiting constant 0.548311... is extremely slow, so even very large
simulations do not come very close. In fact, combining the simulation
results of [2] with the rigorous results of [6], one may (tentatively) estimate that
in order to get close to the limiting value, one would need to
simulate a square of about
100,000,000,000,000,000,000 by 100,000,000,000,000,000,000
(1020 by 1020) sites,
certainly well beyond the range of any computer!
Applications
The above model is called bootstrap percolation, and serves as
a mathematically idealised model for phenomena of nucleation and
growth. Such models have been applied in the study of crack
formation, magnetic alloys, hydrogen mixtures, and computer storage arrays.
See the references below
for more information. More generally, bootstrap percolation provides
an important stepping stone towards understanding other cellular
automaton models, which have numerous applications in physics, biology
and information technology.
References
Links:
Primordial Soup Kitchen. David Griffeath's cellular automaton page
Analysis of Local Growth Models. Lecture notes by Janko Gravner
Bootstrap Percolation in Eric Weisstein's Mathworld.
Articles:
[1] J. Adler. Bootstrap percolation. Physica A, 171:453-470, 1991.
[2] J. Adler, D. Stauffer and A. Aharony. Comparison of bootstrap
percolation models. Journal of Physics A, 22:L297-L301, 1989.
[3] M. Aizenman and J. L. Lebowitz. Metastability effects in bootstrap percolation models. Journal of Physics A, 22:L297-L301, 1989.
[4] R. Cerf and F. Manzo. The threshold regime of finite volume bootstrap percolation. To appear.
[5] J. Gravner and D. Griffeath. First passage times for threshold growth dynamics on Zd. Annals of probability, 24(4):1752-1778, 1996.
[6] A. E. Holroyd. Sharp metastability threshold for two-dimensional
bootstrap percolation. Probability Theory and Related Fields,
125(2):195-224, 2003.
[7] R. H. Schonamnn. On the behaviour of some cellular automata related to bootstrap percolation. Annals of probability, 20(1):174-193, 1992.
Alexander E. Holroyd 2005