statistical mechanics In physics, statistical mechanics is a mathematical framework that applies statistical methods and probability theory to large assemblies of microscopic entities. It does not assume or postulate any natural laws, but explains the macroscopic be ...

, bootstrap percolation is a

percolation Percolation (from Latin ''percolare'', "to filter" or "trickle through"), in physics, chemistry and materials science, refers to the movement and filtering of fluids through porous materials. It is described by Darcy's law. Broader applicatio ...

process in which a random initial configuration of active cells is selected from a

lattice Lattice may refer to: Arts and design * Latticework, an ornamental criss-crossed framework, an arrangement of crossing laths or other thin strips of material * Lattice (music), an organized grid model of pitch ratios * Lattice (pastry), an orna ...

or other space, and then cells with few active neighbors are successively removed from the active set until the system stabilizes. The order in which this removal occurs makes no difference to the final stable state.. When the threshold of active neighbors needed for an active cell to survive is high enough (depending on the lattice), the only stable states are states with no active cells, or states in which every cluster of active cells is infinitely large. For instance, on the

square lattice In mathematics, the square lattice is a type of lattice in a two-dimensional Euclidean space. It is the two-dimensional version of the integer lattice, denoted as . It is one of the five types of two-dimensional lattices as classified by their ...

with the

von Neumann neighborhood In cellular automata, the von Neumann neighborhood (or 4-neighborhood) is classically defined on a two-dimensional square lattice and is composed of a central cell and its four adjacent cells. The neighborhood is named after John von Neumann, ...

, there are finite clusters with at least two active neighbors per cluster cell, but when three or four active neighbors are required, any stable cluster must be infinite. With three active neighbors needed to stay active, an infinite cluster must stretch infinitely in three or four of the possible cardinal directions, and any finite holes it contains will necessarily be rectangular. In this case, the critical probability is 1, meaning that when the probability of each cell being active in the initial state is anything less than 1, then

almost surely In probability theory, an event is said to happen almost surely (sometimes abbreviated as a.s.) if it happens with probability 1 (or Lebesgue measure 1). In other words, the set of possible exceptions may be non-empty, but it has probability 0. ...

there is no infinite cluster. If the initial state is active everywhere except for an square, within which one cell in each row and column is inactive, then these single-cell voids will merge to form a void that covers the whole square if and only if the inactive cells have the pattern of a

separable permutation In combinatorial mathematics, a separable permutation is a permutation that can be obtained from the trivial permutation 1 by direct sums and skew sums. Separable permutations may be characterized by the forbidden permutation patterns 2413 and 3 ...

. In any higher dimension, for any threshold, there is an analogous critical probability below which all cells almost surely become inactive and above which some clusters almost surely survive.. Bootstrap percolation can be interpreted as a

cellular automaton A cellular automaton (pl. cellular automata, abbrev. CA) is a discrete model of computation studied in automata theory. Cellular automata are also called cellular spaces, tessellation automata, homogeneous structures, cellular structures, tessel ...

, resembling

Conway's Game of Life The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970. It is a zero-player game, meaning that its evolution is determined by its initial state, requiring no further ...

, in which live cells die when they have too few live neighbors. However, unlike Conway's Life, cells that have become dead never become alive again. It can also be viewed as an

epidemic model Compartmental models are a very general modelling technique. They are often applied to the mathematical modelling of infectious diseases. The population is assigned to compartments with labels – for example, S, I, or R, (Susceptible, Infectious, ...

in which inactive cells are considered as infected and active cells with too many infected neighbors become infected themselves. The smallest threshold that allows some cells of an initial cluster to survive is called the

degeneracy Degeneracy, degenerate, or degeneration may refer to: Arts and entertainment * ''Degenerate'' (album), a 2010 album by the British band Trigger the Bloodshed * Degenerate art, a term adopted in the 1920s by the Nazi Party in Germany to descri ...

of its adjacency graph, and the remnant of a cluster that survives with threshold ''k'' is called the ''k''-core of this graph. One application of bootstrap percolation arises in the study of

fault tolerance Fault tolerance is the property that enables a system to continue operating properly in the event of the failure of one or more faults within some of its components. If its operating quality decreases at all, the decrease is proportional to the ...

for

distributed computing A distributed system is a system whose components are located on different computer network, networked computers, which communicate and coordinate their actions by message passing, passing messages to one another from any system. Distributed com ...

. If some processors in a large grid of processors fail (become inactive), then it may also be necessary to inactivate other processors with too few active neighbors, in order to preserve the high connectivity of the remaining network. The analysis of bootstrap percolation can be used to determine the failure probability that can be tolerated by the system..

References

{{reflist Percolation theory Cellular automata