La percolación del primer paso es un método matemático que se utiliza para describir los caminos alcanzables en un medio aleatorio dentro de un período de tiempo determinado.
La filtración del primer pasaje es una de las áreas más clásicas de la teoría de la probabilidad . Fue introducido por primera vez por John Hammersley y Dominic Welsh en 1965 como 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 verse como un subconjunto de la percolación del 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 formuladas. La mayoría de las veces, el objetivo de la filtración del primer paso es comprender una distancia aleatoria en un gráfico, donde se asignan pesos a los bordes. La mayoría de las preguntas están ligadas 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 a gran escala.
Como es el caso de la teoría de la percolación en general, muchos de los problemas relacionados con la percolación del primer paso implican encontrar rutas óptimas o tiempos óptimos. El modelo se define de la siguiente manera. [2] Sea una gráfica . Colocamos una variable aleatoria no negativa , llamada tiempo de paso del borde , en cada borde vecino más cercano del gráfico . Generalmente se supone que la colección es independiente y está distribuida de manera idéntica, 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 filtración del 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 borde en el camino. [3]
Dados dos vértices de uno, entonces se establece
donde el mínimo está sobre todos los caminos finitos que comienzan y terminan en . La función induce una pseudométrica aleatoria en .
El modelo más famoso de percolación de primer paso es el de la celosía . Una de sus preguntas más notorias es "¿Cómo es una bola de gran radio?". Esta cuestión se planteó en el artículo original de Hammersley y Welsh en 1969 y dio lugar 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 hay muchas propiedades de este conjunto. son conocidos. Por ejemplo, se espera que bajo supuestos suaves 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 hay 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 usando cadenas de Markov y árboles recursivos [6] y franjas de 2 anchos se pueden describir usando una cadena de Markov y resolver usando una cadena de Harris . [7]
La filtración del primer pasaje 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 Eden 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 ruta minimizada desde la filtración del primer pasaje para evaluar qué tan pesimista es la subasta VCG en su límite inferior. Ambos problemas se resuelven de manera similar y se pueden encontrar distribuciones que se pueden utilizar en la teoría de las subastas.