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
  1. Chalupa, J.; Leath, P. L.; Reich, G. R. (1979), "Bootstrap percolation on a Bethe lattice", Journal of Physics C: Solid State Physics, 12 (1): L31–L35, Bibcode:1979JPhC...12L..31C, doi:10.1088/0022-3719/12/1/008.
  2. Adler, Joan (1991), "Bootstrap percolation", Physica A: Statistical Mechanics and its Applications, 171 (3): 453–470, Bibcode:1991PhyA..171..453A, doi:10.1016/0378-4371(91)90295-n.
  3. van Enter, Aernout C. D. (1987), "Proof of Straley's argument for bootstrap percolation", Journal of Statistical Physics, 48 (3–4): 943–945, Bibcode:1987JSP....48..943V, doi:10.1007/BF01019705, MR 0914911.
  4. Shapiro, Louis; Stephens, Arthur B. (1991), "Bootstrap percolation, the Schröder numbers, and the N-kings problem", SIAM Journal on Discrete Mathematics, 4 (2): 275–280, doi:10.1137/0404025, MR 1093199.
  5. Balogh, József; Bollobás, Béla; Duminil-Copin, Hugo; Morris, Robert (2012), "The sharp threshold for bootstrap percolation in all dimensions", Transactions of the American Mathematical Society, 364 (5): 2667–2701, arXiv:1010.3326, doi:10.1090/S0002-9947-2011-05552-2, MR 2888224.
  6. Aizenman, M.; Lebowitz, J. L. (1988), "Metastability effects in bootstrap percolation", Journal of Physics A: Mathematical and General, 21 (19): 3801–3813, Bibcode:1988JPhA...21.3801A, doi:10.1088/0305-4470/21/19/017.
  7. Schonmann, Roberto H. (1992), "On the behavior of some cellular automata related to bootstrap percolation", Annals of Probability, 20 (1): 174–193, doi:10.1214/aop/1176989923, JSTOR 2244552, MR 1143417.
  8. Gottschau, Marinus (2016), Bootstrap percolation on degenerate graphs, arXiv:1605.07002, Bibcode:2016arXiv160507002G.
  9. Kirkpatrick, Scott; Wilcke, Winfried W.; Garner, Robert B.; Huels, Harald (2002), "Percolation in dense storage arrays", Physica A: Statistical Mechanics and its Applications, 314 (1–4): 220–229, Bibcode:2002PhyA..314..220K, doi:10.1016/S0378-4371(02)01153-6, MR 1961703.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.