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 el que se produce esta eliminación no afecta al estado estable final. [1] [2]
Cuando el umbral de vecinos activos necesario para que una célula activa sobreviva es lo suficientemente alto (dependiendo de la red), los únicos estados estables son estados sin células activas, o estados en los que cada grupo de células activas es infinitamente grande. Por ejemplo, en la red cuadrada con el vecindario de von Neumann , hay grupos finitos con al menos dos vecinos activos por célula 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 necesariamente será rectangular. En este caso, la probabilidad crítica es 1, lo que significa que cuando la probabilidad de que cada célula esté activa en el estado inicial es menor que 1, entonces casi seguramente 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 celdas 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 todas las celdas casi seguramente se vuelven inactivas y por encima de la cual algunos grupos casi seguramente sobreviven. [5]
La percolación bootstrap puede interpretarse como un autómata celular , similar 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 la Vida de Conway, las células que han muerto nunca vuelven a estar vivas. [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 a su vez. [5] El umbral más pequeño que permite que sobrevivan algunas células de un grupo inicial se denomina degeneración de su gráfico de adyacencia, y el remanente de un grupo que sobrevive con el umbral k se denomina k -núcleo de este gráfico. [8]
Una aplicación de la percolación de arranque surge en el estudio de la tolerancia a fallos para la computación distribuida . Si algunos procesadores en una gran red de procesadores fallan (se vuelven inactivos), entonces también puede ser necesario inactivar otros procesadores con muy pocos vecinos activos, con el fin de preservar la alta conectividad de la red restante. El análisis de la percolación de arranque se puede utilizar para determinar la probabilidad de fallo que puede tolerar el sistema. [9]