Bootstrap percolation

In statistical mechanics, bootstrap percolation is a percolation process in which a random initial configuration of active cells is selected from a lattice 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.^[1][2]

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 with the von Neumann neighborhood, 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.^[1] 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 there is no infinite cluster.^[3] If the initial state is active everywhere except for an n × n 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.^[4] 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.^[5]

Bootstrap percolation can be interpreted as a cellular automaton, resembling Conway's Game of Life, 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.^[6][7] It can also be viewed as an epidemic model in which inactive cells are considered as infected and active cells with too many infected neighbors become infected themselves.^[5] The smallest threshold that allows some cells of an initial cluster to survive is the degeneracy of its adjacency graph, and the remnant of a cluster that survives with threshold k is the k-core of this graph.^[8]

One application of bootstrap percolation arises in the study of fault tolerance for distributed computing. 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.^[9]

References