Percolación de primer paso

La percolación de primer paso es un método matemático que se utiliza para describir las trayectorias alcanzables en un medio aleatorio dentro de un tiempo determinado.

La percolación de primer paso es una de las áreas más clásicas de la teoría de la probabilidad . Fue introducida por primera vez por John Hammersley y Dominic Welsh en 1965 como un modelo de flujo de fluidos en un medio poroso. ^{[ 1 ]} Forma parte de la teoría de la percolación , y la percolación clásica de Bernoulli puede considerarse un subconjunto de la percolación de primer paso.

La mayor parte de la belleza del modelo reside en su definición simple (como un espacio métrico aleatorio ) y en la propiedad de que varias de sus fascinantes conjeturas no requieren mucho esfuerzo para ser enunciadas. En la mayoría de los casos, el objetivo de la percolación de primer paso es comprender una distancia aleatoria en un grafo, donde se asignan pesos a las aristas. La mayoría de las preguntas están relacionadas con encontrar el camino con el menor peso entre dos puntos, conocido como geodésica , o con comprender cómo se comporta la geometría aleatoria a gran escala.

Como ocurre en la teoría de la percolación en general, muchos de los problemas relacionados con la percolación de primer paso implican encontrar rutas óptimas o tiempos óptimos. El modelo se define de la siguiente manera. ^{[ 2 ]} Sea${\displaystyle G}$Sea un gráfico . Colocamos una variable aleatoria no negativa. ${\displaystyle t(e)}$, llamado tiempo de paso del borde${\displaystyle e}$, en cada arista vecina más cercana del grafo${\displaystyle G}$La colección${\displaystyle t(e)}$Generalmente se asume que son independientes e idénticamente distribuidas, pero existen variantes del modelo. La variable aleatoria${\displaystyle t(e)}$se interpreta como el tiempo o el costo necesario para recorrer el borde${\displaystyle e}$.

Dado que cada arista en la percolación de primer paso tiene su propio peso (o tiempo) individual, podemos escribir el tiempo total de un camino como la suma de los pesos de cada arista en el camino. ^{[ 3 ]}

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

Dados dos vértices${\displaystyle x,y}$de${\displaystyle G}$uno entonces establece

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

donde el ínfimo se encuentra sobre todos los caminos finitos que comienzan en${\displaystyle x}$y termina en${\displaystyle y}$. La función${\displaystyle T}$induce una pseudométrica aleatoria en${\displaystyle G}$.

El modelo más famoso de percolación de primer paso se basa en la red cristalina.${\displaystyle \mathbb {Z} ^{d}}$Una de sus preguntas más notorias es "¿Cómo se ve una bola de radio grande?". Esta pregunta se planteó en el artículo original de Hammersley y Welsh en 1969 y dio origen al teorema de la forma límite de Cox-Durrett en 1981. ^{[ 4 ]} Aunque el teorema de Cox-Durrett proporciona la existencia de la forma límite, no se conocen muchas propiedades de este conjunto. Por ejemplo, se espera que bajo supuestos suaves este conjunto sea estrictamente convexo. Hasta 2016, el mejor resultado es la existencia del punto de diferenciabilidad de Auffinger-Damron en el caso de borde plano de Cox-Liggett . ^{[ 5 ]}

También existen algunos ejemplos específicos de percolación de primer paso que pueden modelarse mediante cadenas de Markov . Por ejemplo: un grafo completo puede describirse mediante cadenas de Markov y árboles recursivos ^{[ 6 ]} , y las franjas de ancho 2 pueden describirse mediante una cadena de Markov y resolverse mediante una cadena de Harris ^{[ 7 ]} .

La percolación de primer paso es bien conocida por dar lugar a otras herramientas matemáticas, incluido el Teorema Ergódico Subaditivo, un resultado fundamental en la teoría ergódica .

Fuera del ámbito matemático, el modelo de crecimiento de Eden se utiliza para modelar el crecimiento bacteriano y la deposición de material. Otro ejemplo consiste en comparar un coste minimizado de la subasta de Vickrey-Clarke-Groves (subasta VCG) con una ruta minimizada de la percolación de primer paso para evaluar el pesimismo de la subasta VCG en su límite inferior. Ambos problemas se resuelven de forma similar y se pueden encontrar distribuciones para su uso en la teoría de subastas .