В статистической механике бутстрап -перколяция — это процесс перколяции , в котором случайная начальная конфигурация активных ячеек выбирается из решетки или другого пространства, а затем ячейки с небольшим количеством активных соседей последовательно удаляются из активного набора до тех пор, пока система не стабилизируется. Порядок, в котором происходит это удаление, не имеет значения для конечного устойчивого состояния. [1] [2]
Когда порог активных соседей, необходимых для выживания активной клетки, достаточно высок (в зависимости от решетки), единственными стабильными состояниями являются состояния без активных клеток или состояния, в которых каждый кластер активных клеток бесконечно велик. Например, на квадратной решетке с окрестностью фон Неймана существуют конечные кластеры с по крайней мере двумя активными соседями на ячейку кластера, но когда требуются три или четыре активных соседа, любой стабильный кластер должен быть бесконечным. [1] При трех активных соседях, необходимых для того, чтобы оставаться активным, бесконечный кластер должен бесконечно растягиваться в трех или четырех возможных кардинальных направлениях, и любые конечные отверстия, которые он содержит, обязательно будут прямоугольными. В этом случае критическая вероятность равна 1, что означает, что когда вероятность того, что каждая клетка будет активной в исходном состоянии, меньше 1, то почти наверняка бесконечного кластера не существует. [3] Если начальное состояние активно везде, за исключением квадрата n × n , в котором одна ячейка в каждой строке и столбце неактивна, то эти пустоты из одной ячейки сольются, образуя пустоту, которая покрывает весь квадрат, если и только если неактивные ячейки имеют структуру разделимой перестановки . [4] В любом более высоком измерении для любого порога существует аналогичная критическая вероятность, ниже которой все ячейки почти наверняка станут неактивными, а выше которой некоторые кластеры почти наверняка выживут. [5]
Перколяцию Bootstrap можно интерпретировать как клеточный автомат , напоминающий игру Конвея «Жизнь» , в которой живые клетки умирают, когда у них слишком мало живых соседей. Однако, в отличие от игры Конвея «Жизнь», клетки, которые стали мертвыми, никогда больше не оживают. [6] [7] Ее также можно рассматривать как модель эпидемии , в которой неактивные клетки считаются инфицированными, а активные клетки со слишком большим количеством инфицированных соседей сами становятся инфицированными. [5] Наименьший порог, позволяющий некоторым клеткам исходного кластера выжить, называется вырожденностью его графа смежности, а остаток кластера, который выживает с порогом k, называется k -ядром этого графа. [8]
Одно из применений bootstrap percolation возникает при изучении отказоустойчивости для распределенных вычислений . Если некоторые процессоры в большой сетке процессоров выходят из строя (становятся неактивными), то может также потребоваться деактивировать другие процессоры со слишком малым количеством активных соседей, чтобы сохранить высокую связность оставшейся сети. Анализ bootstrap percolation может быть использован для определения вероятности отказа, которую может допустить система. [9]