Första passagen perkolation

First passage percolation är en matematisk metod som används för att beskriva de vägar som kan nås i ett slumpmässigt medium inom en given tidsperiod.

Introduktion

Första passagen perkolation är ett av de mest klassiska områdena inom sannolikhetsteorin . Det introducerades först av John Hammersley och Dominic Welsh 1965 som en modell av vätskeflöde i ett poröst medium. Det är en del av perkolationsteorin, och klassisk Bernoulli- perkolation kan ses som en delmängd av första passage-perkolation.

Det mesta av modellens skönhet ligger i dess enkla definition (som ett slumpmässigt metriskt utrymme ) och egenskapen att flera av dess fascinerande gissningar inte kräver mycket ansträngning för att kunna anges. Oftast är målet med första passagen perkolering att förstå ett slumpmässigt avstånd på en graf, där vikter tilldelas kanter. De flesta frågor är knutna till att antingen hitta vägen med minst vikt mellan två punkter, känd som en geodetisk , eller för att förstå hur den slumpmässiga geometrin beter sig i stora skalor.

Matematik

Som är fallet inom perkolationsteori i allmänhet, involverar många av problemen relaterade till första passage-perkolering att hitta optimala vägar eller optimala tider. Modellen definieras enligt följande. Låt $G$ vara en graf . Vi placerar en icke-negativ slumpvariabel $t(e)$ , kallad passagetiden för kanten $e$ , vid varje närmaste grannkant av grafen $G$ . Samlingen $t(e)$ antas vanligtvis vara oberoende, identiskt fördelad men det finns varianter av modellen. Den slumpmässiga variabeln $t(e)$ tolkas som tiden eller kostnaden som krävs för att korsa kanten e { $displaystyle e}$ .

Eftersom varje kant i första passage-perkolation har sin egen individuella vikt (eller tid) kan vi skriva den totala tiden för en bana som summan av vikterna för varje kant i banan.

$T(\gamma )=\summa _{i\in \gamma }t(e_{i}).$

Givet två hörn $x,y$ av $G$ sätter en sedan

$T(x,y)=\inf _{\gamma }T(\gamma ),$

där infimum är över alla finita banor som börjar vid $x$ och slutar vid $y$ . Funktionen $T$ inducerar en slumpmässig pseudometrik på $G$ .

Den mest kända modellen av första passage-perkolation är på gallret $\mathbb {Z} ^{d}$ . En av dess mest ökända frågor är "Hur ser en boll med stor radie ut?". Denna fråga togs upp i den ursprungliga uppsatsen av Hammersley och Welsh 1969 och gav upphov till Cox-Durretts gränsformsats 1981. Även om Cox-Durretts sats ger förekomsten av gränsformen, är inte många egenskaper hos denna uppsättning kända. Till exempel förväntas det att under milda antaganden bör denna uppsättning vara strikt konvex. Från och med 2016 är det bästa resultatet förekomsten av Auffinger-Damron-differentieringspunkten i Cox-Liggett-fodralet med platt kant.

Det finns också några specifika exempel på första passage-perkolering som kan modelleras med Markov-kedjor . Till exempel: en komplett graf kan beskrivas med Markov-kedjor och rekursiva träd och 2-breddsremsor kan beskrivas med en Markov-kedja och lösas med en Harris-kedja .

Ansökningar

First passage percolation är välkänd för att ge upphov till andra matematiska verktyg, inklusive Subadditive Ergodic Theorem, ett grundläggande resultat i ergodisk teori .

Utanför matematiken används Eden-tillväxtmodellen för att modellera bakterietillväxt och avsättning av material. Ett annat exempel är att jämföra en minimerad kostnad från Vickrey-Clarke-Groves-auktionen (VCG-auktion) med en minimerad väg från första passage-perkolering för att bedöma hur pessimistisk VCG-auktionen är vid sin nedre gräns. Båda problemen löses på samma sätt och man kan hitta distributioner att använda i auktionsteori.