TOPICS
Search

Bootstrap Percolation


A two-dimensional binary (k=2) totalistic cellular automaton with a von Neumann neighborhood of range r=1. It has a birth rule that at least 2 of its 4 neighbors are alive, and a survival rule that all cells survive. n steps of bootstrap percolation on an s×s grid with random initial condition of density p can be implemented in the Wolfram Language as

With[{n = 10, p = 0.1, s = 20},
  CellularAutomaton[
    {1018, {2, {{0, 2, 0}, {2, 1, 2}, {0, 2, 0}}},
      {1, 1}},
    Table[If[Random[Real] < p, 1, 0],  {s},  {s}],
    n
  ]
]
Bootstrap percolation for three different starting densities

If the initial condition consists of a random sparse arrangement of cells with density p, then the system seems to quickly converge to a steady state of rectangular islands of live cells surrounded by a sea of dead cells. However, as p crosses some threshold on finite-sized grids, the behavior appears to change so that every cell becomes live. Several examples are shown above on three 25×25 grids with random initial conditions and different starting densities.

However, this conclusion proves to be incorrect, since the apparent change in behavior actually is a spurious edge effect introduced by use of a finite-sized grid. Amazingly, Holroyd (2003) showed that the asymptotic threshold occurs such that

 lim_(p->0; s->infty)plns=1/(18)pi^2.

See also

Totalistic Cellular Automaton, Voter Model

Explore with Wolfram|Alpha

References

Aizenman, M. and Lebowitz, J. "Metastability Effects in Bootstrap Percolation." J. Phys. A 21, 3801-3813, 1988.Gray, L. "A Mathematician Looks at Wolfram's New Kind of Science." Not. Amer. Math. Soc. 50, 200-211, 2003.Holroyd, A. "Sharp Metastability Threshold for Two-Dimensional Bootstrap Percolation." Prob. Th. and Related Fields 125, 195-224, 2003.Wolfram, S. A New Kind of Science. Champaign, IL: Wolfram Media, pp. 337-342, 2002.

Referenced on Wolfram|Alpha

Bootstrap Percolation

Cite this as:

Weisstein, Eric W. "Bootstrap Percolation." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/BootstrapPercolation.html

Subject classifications