En matemáticas , el paseo aleatorio con bucle borrado es un modelo para un camino aleatorio simple con importantes aplicaciones en combinatoria , física y teoría cuántica de campos . Está íntimamente relacionado con el árbol de expansión uniforme , un modelo para un árbol aleatorio . Véase también paseo aleatorio para un tratamiento más general de este tema.
Supongamos que G es un gráfico y un camino de longitud n en G. En otras palabras, los vértices de G son tales que y están conectados por una arista. Luego, el borrado del bucle es una nueva ruta simple creada borrando todos los bucles en orden cronológico. Formalmente, definimos índices inductivamente usando
donde "max" aquí significa hasta la longitud del camino . La inducción se detiene cuando para algunos tenemos .
En palabras, para encontrar , sostenemos en una mano, y con la otra mano, rastreamos hacia atrás desde el final: , hasta que llegamos a algo , en cuyo caso establecemos , o terminamos en , en cuyo caso establecemos .
Supongamos que esto sucede en J , es decir, es el último . Entonces el borrado del bucle de , denotado por es un camino simple de longitud J definido por
Ahora sea G un gráfico, sea v un vértice de G y sea R un paseo aleatorio sobre G a partir de v . Sea T un tiempo de parada para R. Luego, el recorrido aleatorio borrado en bucle hasta que el tiempo T sea LE ( R ([1, T ])). En otras palabras, tome R desde su inicio hasta T (esa es una ruta (aleatoria)), borre todos los bucles en orden cronológico como se indicó anteriormente y obtendrá una ruta simple aleatoria.
El tiempo de parada T puede ser fijo, es decir, se pueden realizar n pasos y luego borrar el bucle. Sin embargo, suele ser más natural tomar T como el tiempo de golpe en algún set. Por ejemplo, sea G el gráfico Z 2 y sea R un paseo aleatorio que comienza en el punto (0,0). Sea T el momento en que R llega por primera vez al círculo de radio 100 (aquí nos referimos, por supuesto, a un círculo discretizado ). LE( R ) se denomina paseo aleatorio borrado en bucle que comienza en (0,0) y se detiene en el círculo.
Para cualquier gráfico G , un árbol de expansión de G es un subgrafo de G que contiene todos los vértices y algunas de las aristas, que es un árbol , es decir, conectado y sin ciclos . Un árbol de expansión elegido aleatoriamente entre todos los árboles de expansión posibles con igual probabilidad se llama árbol de expansión uniforme. Por lo general, hay muchos árboles de expansión exponencialmente (demasiados para generarlos todos y luego elegir uno al azar); en cambio, los árboles de expansión uniformes se pueden generar de manera más eficiente mediante un algoritmo llamado algoritmo de Wilson que utiliza paseos aleatorios borrados en bucle.
El algoritmo procede de acuerdo con los siguientes pasos. Primero, construya un árbol T de un solo vértice eligiendo (arbitrariamente) un vértice. Luego, si bien el árbol T construido hasta ahora aún no incluye todos los vértices del gráfico, sea v un vértice arbitrario que no está en T , realice un recorrido aleatorio borrado en bucle desde v hasta llegar a un vértice en T , y agregue la ruta resultante a T . Repetir este proceso hasta que se incluyan todos los vértices produce un árbol distribuido uniformemente, independientemente de las elecciones arbitrarias de vértices en cada paso.
También es cierta una conexión en la otra dirección. Si v y w son dos vértices en G , entonces, en cualquier árbol de expansión, están conectados por una ruta única. Tomar este camino en el árbol de expansión uniforme da un camino simple aleatorio. Resulta que la distribución de este camino es idéntica a la distribución del paseo aleatorio borrado en bucle que comienza en v y se detiene en w . Este hecho puede utilizarse para justificar la exactitud del algoritmo de Wilson. Otro corolario es que el paseo aleatorio con bucle borrado es simétrico en sus puntos inicial y final. Más precisamente, la distribución del recorrido aleatorio borrado en bucle que comienza en v y se detiene en w es idéntica a la distribución de la inversión del recorrido aleatorio borrado en bucle que comienza en w y se detiene en v . El borrado en bucle de un recorrido aleatorio y el recorrido inverso no dan, en general, el mismo resultado, pero según este resultado las distribuciones de los dos recorridos borrados en bucle son idénticas.
Otra representación del paseo aleatorio con bucle borrado surge de las soluciones de la ecuación discreta de Laplace . Sea G nuevamente una gráfica y sean v y w dos vértices en G. Construya una ruta aleatoria de v a w inductivamente usando el siguiente procedimiento. Supongamos que ya lo hemos definido . Sea f una función de G a R que satisfaga
Donde una función f en una gráfica es discretamente armónica en un punto x si f ( x ) es igual al promedio de f en los vecinos de x .
Con f definida, elija usar f en los vecinos de como pesos. En otras palabras, si estos son vecinos, elija con probabilidad
Continuando con este proceso, recalculando f en cada paso, el resultado es una ruta simple aleatoria de v a w ; la distribución de este camino es idéntica a la de un paseo aleatorio borrado en bucle de v a w . [ cita necesaria ]
Una visión alternativa es que la distribución de un paseo aleatorio con borrado en bucle condicionado a comenzar en algún camino β es idéntico al borrado en bucle de un paseo aleatorio condicionado a no llegar a β. Esta propiedad a menudo se denomina propiedad de Markov del paseo aleatorio borrado en bucle (aunque la relación con la propiedad de Markov habitual es algo vaga).
Es importante señalar que, si bien la prueba de la equivalencia es bastante sencilla, los modelos que implican funciones o medidas armónicas que cambian dinámicamente suelen ser extremadamente difíciles de analizar. Prácticamente no se sabe nada sobre el paseo p-Laplaciano o la agregación de difusión limitada . Otro modelo algo relacionado es el explorador armónico.
Finalmente hay otro vínculo que cabe mencionar: el teorema de Kirchhoff relaciona el número de árboles generadores de un grafo G con los valores propios del laplaciano discreto . Consulte el árbol de expansión para obtener más detalles.
Sea d la dimensión, que supondremos que es al menos 2. Examine Z d , es decir, todos los puntos con un número entero . Esta es una gráfica infinita con grado 2 d cuando conectas cada punto con sus vecinos más cercanos. De ahora en adelante consideraremos el paseo aleatorio borrado en bucle en este gráfico o sus subgrafos.
El caso más fácil de analizar es el de dimensión 5 y superiores. En este caso resulta que allí las intersecciones son sólo locales. Un cálculo muestra que si uno realiza un paseo aleatorio de longitud n , su borrado de bucle tiene una longitud del mismo orden de magnitud, es decir, n . Escalando en consecuencia, resulta que el paseo aleatorio borrado por bucle converge (en un sentido apropiado) al movimiento browniano cuando n tiende a infinito. La dimensión 4 es más complicada, pero el panorama general sigue siendo cierto. Resulta que el borrado del bucle de un paseo aleatorio de longitud n tiene aproximadamente vértices, pero nuevamente, después del escalado (que tiene en cuenta el factor logarítmico), el paseo borrado del bucle converge al movimiento browniano.
En dos dimensiones, los argumentos de la teoría de campos conforme y los resultados de la simulación llevaron a una serie de conjeturas interesantes. Supongamos que D es algún dominio simplemente conexo en el plano y x es un punto en D. Tome la gráfica G como
es decir, una cuadrícula de longitud lateral ε restringida a D. Sea v el vértice de G más cercano a x . Examine ahora un recorrido aleatorio borrado en bucle que comienza en v y se detiene al llegar al "límite" de G , es decir, los vértices de G que corresponden al límite de D. Entonces las conjeturas son
El primer ataque a estas conjeturas provino de la dirección de los mosaicos de dominó . Tomando un árbol de expansión de G y agregándole su dual plano se obtiene un mosaico de dominó de un gráfico derivado especial (llámelo H ). Cada vértice de H corresponde a un vértice, arista o cara de G , y las aristas de H muestran qué vértice se encuentra en qué arista y qué arista en qué cara. Resulta que tomar un árbol de expansión uniforme de G conduce a un mosaico de dominó aleatorio uniformemente distribuido de H. El número de mosaicos de dominó de un gráfico se puede calcular utilizando el determinante de matrices especiales, que permiten conectarlo a la función de Green discreta que es aproximadamente conformemente invariante. Estos argumentos permitieron demostrar que ciertos mensurables del paseo aleatorio borrado en bucle son (en el límite) conformemente invariantes, y que el número esperado de vértices en un paseo aleatorio borrado en bucle detenido en un círculo de radio r es del orden de . [1]
En 2002 estas conjeturas se resolvieron (positivamente) utilizando la Evolución Estocástica de Löwner . En términos generales, es una ecuación diferencial ordinaria estocástica conformemente invariante que permite captar la propiedad de Markov del paseo aleatorio borrado en bucle (y muchos otros procesos probabilísticos).
El límite de escala existe y es invariante bajo rotaciones y dilataciones. [2] Si denota el número esperado de vértices en el recorrido aleatorio borrado en bucle hasta llegar a una distancia de r , entonces
donde ε, cy C son algunos números positivos [3] ( los números pueden, en principio, calcularse a partir de las pruebas, pero el autor no lo hizo). Esto sugiere que el límite de escala debería tener una dimensión de Hausdorff entre y 5/3 casi con seguridad. Los experimentos numéricos muestran que así debería ser . [4]
