La percolación de primer paso es un método matemático utilizado para describir los caminos alcanzables en un medio aleatorio dentro de un período de 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 fluido en un medio poroso. [1] Es 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. La mayoría de las veces, el objetivo de la percolación de primer paso es comprender una distancia aleatoria en un gráfico, donde se asignan pesos a las aristas. La mayoría de las preguntas están vinculadas a encontrar el camino con el menor peso entre dos puntos, conocido como geodésica , o a comprender cómo se comporta la geometría aleatoria en grandes escalas.
Como es el caso 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 un grafo . Colocamos una variable aleatoria no negativa , llamada tiempo de paso del borde , en cada borde vecino más cercano del grafo . Por lo general, se supone que la colección es independiente, idénticamente distribuida, pero existen variantes del modelo. La variable aleatoria se interpreta como el tiempo o el costo necesario para atravesar el borde .
Dado que cada borde en la percolación del primer paso tiene su propio peso individual (o tiempo), podemos escribir el tiempo total de una ruta como la suma de los pesos de cada borde en la ruta. [3]
Dados dos vértices de uno entonces conjuntos
donde el ínfimo se encuentra sobre todos los caminos finitos que comienzan en y terminan en . La función induce una pseudométrica aleatoria en .
El modelo más famoso de percolación de primer paso se basa en la red . Una de sus preguntas más notorias es "¿Cómo se ve una bola de gran radio?". Esta pregunta se planteó en el artículo original de Hammersley y Welsh en 1969 y dio lugar al teorema de forma límite de Cox-Durrett en 1981. [4] Aunque el teorema de Cox-Durrett establece la existencia de la forma límite, no se conocen muchas propiedades de este conjunto. Por ejemplo, se espera que bajo supuestos moderados este conjunto sea estrictamente convexo. A partir de 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 se pueden modelar utilizando cadenas de Markov . Por ejemplo: un gráfico completo se puede describir utilizando cadenas de Markov y árboles recursivos [6] y las franjas de 2 anchos se pueden describir utilizando una cadena de Markov y resolver utilizando una cadena de Harris . [7]
La percolación de primer paso es bien conocida por dar lugar a otras herramientas de las matemáticas, incluido el Teorema Ergódico Subaditivo, un resultado fundamental en la teoría ergódica .
Fuera de las matemáticas, el modelo de crecimiento de Edén se utiliza para modelar el crecimiento de bacterias y la deposición de material. Otro ejemplo es comparar un costo minimizado de la subasta Vickrey-Clarke-Groves (subasta VCG) con una trayectoria minimizada de la percolación de primer paso para medir cuán pesimista es la subasta VCG en su límite inferior. Ambos problemas se resuelven de manera similar y se pueden encontrar distribuciones para usar en la teoría de subastas.
