En mecánica estadística , la percolación bootstrap es un proceso de percolación en el que se selecciona una configuración inicial aleatoria de celdas activas de una red u otro espacio, y luego las celdas con pocos vecinos activos se eliminan sucesivamente del conjunto activo hasta que el sistema se estabiliza. El orden en que se produce esta eliminación no influye en el estado estable final. [1] [2]
Cuando el umbral de vecinos activos necesarios para que una célula activa sobreviva es lo suficientemente alto (dependiendo de la red), los únicos estados estables son los estados sin células activas o los estados en los que cada grupo de células activas es infinitamente grande. Por ejemplo, en la red cuadrada con la vecindad de von Neumann , hay grupos finitos con al menos dos vecinos activos por celda del grupo, pero cuando se requieren tres o cuatro vecinos activos, cualquier grupo estable debe ser infinito. [1] Con tres vecinos activos necesarios para permanecer activo, un grupo infinito debe extenderse infinitamente en tres o cuatro de las posibles direcciones cardinales, y cualquier agujero finito que contenga será necesariamente rectangular. En este caso, la probabilidad crítica es 1, lo que significa que cuando la probabilidad de que cada celda esté activa en el estado inicial es menor que 1, entonces es casi seguro que no hay un grupo infinito. [3] Si el estado inicial está activo en todas partes excepto en un cuadrado n × n , dentro del cual una celda en cada fila y columna está inactiva, entonces estos vacíos de una sola celda se fusionarán para formar un vacío que cubra todo el cuadrado si y solo si las células inactivas tienen el patrón de una permutación separable . [4] En cualquier dimensión superior, para cualquier umbral, existe una probabilidad crítica análoga por debajo de la cual es casi seguro que todas las células se vuelven inactivas y por encima de la cual es casi seguro que algunos grupos sobrevivan. [5]
La percolación Bootstrap se puede interpretar como un autómata celular , parecido al Juego de la vida de Conway , en el que las células vivas mueren cuando tienen muy pocos vecinos vivos. Sin embargo, a diferencia de Life de Conway, las células que han muerto nunca vuelven a vivir. [6] [7] También puede verse como un modelo epidémico en el que las células inactivas se consideran infectadas y las células activas con demasiados vecinos infectados se infectan ellas mismas. [5] El umbral más pequeño que permite que algunas células de un grupo inicial sobrevivan se llama degeneración de su gráfico de adyacencia, y el remanente de un grupo que sobrevive con el umbral k se llama k -núcleo de este gráfico. [8]
Una aplicación de la percolación bootstrap surge en el estudio de la tolerancia a fallas para la computación distribuida . Si algunos procesadores en una gran red de procesadores fallan (se vuelven inactivos), entonces también puede ser necesario desactivar otros procesadores con muy pocos vecinos activos, para preservar la alta conectividad de la red restante. El análisis de percolación bootstrap se puede utilizar para determinar la probabilidad de falla que puede tolerar el sistema. [9]