Bootstrap perkolering
Inom statistisk mekanik är bootstrap-perkolering en perkolationsprocess där en slumpmässig initial konfiguration av aktiva celler väljs från ett gitter eller annat utrymme, och sedan tas celler med få aktiva grannar successivt bort från den aktiva uppsättningen tills systemet stabiliseras. Ordningen i vilken detta avlägsnande sker gör ingen skillnad för det slutliga stabila tillståndet.
När tröskeln för aktiva grannar som behövs för att en aktiv cell ska överleva är tillräckligt hög (beroende på gittret), är de enda stabila tillstånden tillstånd utan aktiva celler, eller tillstånd där varje kluster av aktiva celler är oändligt stort. Till exempel, på det kvadratiska gittret med von Neumann-kvarteret , finns det ändliga kluster med minst två aktiva grannar per klustercell, men när tre eller fyra aktiva grannar krävs måste alla stabila kluster vara oändliga. Med tre aktiva grannar som behövs för att förbli aktiva måste ett oändligt kluster sträcka sig oändligt i tre eller fyra av de möjliga kardinalriktningarna, och alla ändliga hål som det innehåller kommer nödvändigtvis att vara rektangulära. I det här fallet är den kritiska sannolikheten 1, vilket betyder att när sannolikheten för att varje cell är aktiv i det initiala tillståndet är något mindre än 1, så finns det nästan säkert inget oändligt kluster. Om det initiala tillståndet är aktivt överallt förutom för en n × n kvadrat, inom vilken en cell i varje rad och kolumn är inaktiv, kommer dessa encelliga tomrum att smälta samman för att bilda ett tomrum som täcker hela kvadraten om och bara om det inaktiva celler har mönstret av en separerbar permutation . I vilken högre dimension som helst, för vilken tröskel som helst, finns det en analog kritisk sannolikhet under vilken alla celler nästan säkert blir inaktiva och över vilken några kluster nästan säkert överlever.
Bootstrap percolation kan tolkas som en cellulär automat , som liknar Conways Game of Life, där levande celler dör när de har för få levande grannar. Men till skillnad från Conway's Life blir celler som har blivit döda aldrig levande igen. Det kan också ses som en epidemimodell där inaktiva celler betraktas som infekterade och aktiva celler med för många infekterade grannar blir själva infekterade. Den minsta tröskeln som tillåter vissa celler i ett initialt kluster att överleva kallas degenerationen av dess närliggande graf, och resten av ett kluster som överlever med tröskeln k kallas k -kärnan i denna graf.
En tillämpning av bootstrap-perkolering uppstår i studien av feltolerans för distribuerad datoranvändning . Om vissa processorer i ett stort rutnät av processorer misslyckas (blir inaktiva), kan det också vara nödvändigt att inaktivera andra processorer med för få aktiva grannar, för att bevara den höga anslutningsmöjligheten för det återstående nätverket. Analysen av bootstrap-perkolering kan användas för att bestämma felsannolikheten som kan tolereras av systemet.