En matemáticas , la caminata aleatoria borrada en bucle es un modelo para una ruta simple aleatoria con aplicaciones importantes en combinatoria y, en física , teoría cuántica de campos . Está íntimamente conectado al árbol de expansión uniforme , un modelo para un árbol aleatorio . Consulte también caminata aleatoria para un tratamiento más general de este tema.
Definición
Suponga que G es una gráfica yes algún camino de longitud n en G . En otras palabras,son vértices de G tales que y están conectados por un borde. Luego, el borrado de bucle de es un nuevo camino simple creado borrando todos los bucles de en orden cronológico. Formalmente, definimos índices usando inductivamente
donde "max" aquí significa hasta la longitud de la ruta . La inducción se detiene cuando para algunos tenemos . Suponga que esto sucede en J ie es lo ultimo . Luego, el borrado de bucle de, denotado por es un camino simple de longitud J definido por
Ahora sea G una gráfica, sea v un vértice de G y sea R un paseo aleatorio sobre G a partir de v . Deje que T sea un poco de tiempo de parada para R . Luego, la caminata aleatoria borrada en bucle hasta que el tiempo T sea LE ( R ([1, T ])). En otras palabras, tome R desde el principio hasta T , que 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, uno puede 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 a partir del punto (0,0). Sea T el momento en que R golpea por primera vez el círculo de radio 100 (aquí nos referimos, por supuesto, a un círculo discretizado ). LE ( R ) se denomina caminata aleatoria borrada en bucle que comienza en (0,0) y se detiene en el círculo.
Árbol de expansión uniforme
Para cualquier gráfico G , un árbol de expansión de G es un subgráfico de G que contiene todos los vértices y algunos de los bordes, que es un árbol , es decir, conectado y sin ciclos . Un árbol de expansión elegido al azar entre todos los árboles de expansión posibles con la misma probabilidad se denomina árbol de expansión uniforme. Por lo general, hay exponencialmente muchos árboles de expansión (demasiados para generarlos todos y luego elegir uno al azar); en cambio, se pueden generar árboles de expansión uniformes de manera más eficiente mediante un algoritmo llamado algoritmo de Wilson, que utiliza recorridos 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. Entonces, mientras que el árbol T construido hasta ahora no incluye todos los vértices del gráfico, sea v un vértice arbitrario que no está en T , realice una caminata aleatoria borrada de bucle desde v hasta alcanzar un vértice en T , y agregar la ruta resultante de T . Repetir este proceso hasta que se incluyan todos los vértices produce un árbol distribuido uniformemente, independientemente de las elecciones arbitrarias de los vértices en cada paso.
Una conexión en la otra dirección también es cierta. Si v y w son dos vértices en G , entonces, en cualquier árbol de expansión, están conectados por una ruta única. Al tomar esta ruta en el árbol de expansión uniforme , se obtiene una ruta simple aleatoria. Resulta que la distribución de esta ruta es idéntica a la distribución de la caminata aleatoria borrada 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 la caminata aleatoria borrada en bucle es simétrica en sus puntos de inicio y final. Más precisamente, la distribución de la caminata aleatoria borrada en bucle que comienza en v y se detiene en w es idéntica a la distribución de la inversión de la caminata aleatoria borrada en bucle que comienza en w y se detiene en v . El borrado de bucle de un paseo aleatorio y el paseo inverso no dan, en general, el mismo resultado, pero de acuerdo con este resultado las distribuciones de los dos paseos borrados de bucle son idénticas.
El paseo aleatorio laplaciano
Otra representación del paseo aleatorio borrado en bucle se deriva de las soluciones de la ecuación de Laplace discreta . Deje G de nuevo un grafo y dejar que v y w sea dos vértices en G . Construya una ruta aleatoria desde v hasta w de manera inductiva mediante el siguiente procedimiento. Supongamos que ya hemos definido. Sea f una función de G a R que satisfaga
- para todos y
- f es discretamente armónico en todas partes
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 elegirusando f en los vecinos decomo pesos. En otras palabras, si son estos vecinos, elige 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 esta ruta es idéntica a la de una caminata aleatoria borrada en bucle de v a w .
Una visión alternativa es que la distribución de una caminata aleatoria borrada en bucle condicionada para comenzar en algún camino β es idéntica al borrado en bucle de una caminata aleatoria condicionada para no golpear β. Esta propiedad a menudo se conoce como la propiedad de Markov del paseo aleatorio borrado en bucle (aunque la relación con la propiedad de Markov habitual es algo vaga).
Es importante notar que si bien la prueba de equivalencia es bastante fácil, los modelos que involucran funciones o medidas armónicas que cambian dinámicamente son típicamente extremadamente difíciles de analizar. Prácticamente no se sabe nada sobre el paseo p-laplaciano o la agregación limitada por difusión . Otro modelo algo relacionado es el explorador armónico .
Finalmente, hay otro vínculo que debe mencionarse: el teorema de Kirchhoff relaciona el número de árboles de expansión de un gráfico G con los valores propios del laplaciano discreto . Consulte el árbol de expansión para obtener más detalles.
Cuadrículas
Sea d la dimensión, que asumiremos que es al menos 2. Examine Z d es decir, todos los puntos con entero . Esta es una gráfica infinita con grado 2 d cuando conecta cada punto a sus vecinos más cercanos. De ahora en adelante, consideraremos la caminata aleatoria borrada en bucle en este gráfico o en sus subgráficos.
Altas dimensiones
El caso más fácil de analizar es el de la dimensión 5 y superior. En este caso resulta que allí las intersecciones son solo locales. Un cálculo muestra que si uno realiza una caminata aleatoria de longitud n , su borrado de bucle tiene una longitud del mismo orden de magnitud, es decir, n . Escalando en consecuencia, resulta que la caminata aleatoria borrada en bucle converge (en un sentido apropiado) al movimiento browniano cuando n va al infinito. La dimensión 4 es más complicada, pero el panorama general sigue siendo cierto. Resulta que el borrado de bucle de una caminata aleatoria de longitud n tiene aproximadamente vértices, pero nuevamente, después de escalar (que tiene en cuenta el factor logarítmico), la caminata borrada de bucles converge al movimiento browniano.
Dos dimensiones
En dos dimensiones, los argumentos de la teoría de campo conforme y los resultados de la simulación llevaron a una serie de conjeturas interesantes. Supongamos D es algunos simplemente conectado dominio en el plano y x es un punto en D . Tome la gráfica G como
es decir, una cuadrícula de longitud de lado varepsilon restringido a D . Sea v el vértice de G más cercano a x . Examinar ahora un paseo aleatorio loop-borrado a partir de v y se detuvo cuando golpear el "límite" de G , es decir, los vértices de G que corresponden a los límites de D . Entonces las conjeturas son
- A medida que ε va a cero, la distribución de la ruta converge a alguna distribución en rutas simples desde x hasta el límite de D (diferente del movimiento browniano, por supuesto; en 2 dimensiones, las rutas del movimiento browniano no son simples). Esta distribución (denotarla por) se denomina límite de escala del paseo aleatorio borrado en bucle.
- Estas distribuciones son conformemente invariantes . Es decir, si φ es un mapa de Riemann entre D y un segundo dominio E, entonces
- La dimensión de Hausdorff de estos caminos es casi seguro de 5/4 .
El primer ataque a estas conjeturas provino de la dirección de las fichas de dominó . Al tomar un árbol de expansión de G y agregarle su doble 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, borde o cara de G , y los bordes de H muestran qué vértice se encuentra en qué borde y qué borde en qué cara. Resulta que la toma de un árbol de expansión uniforme de G conduce a un domino aleatorio distribuido uniformemente suelo de baldosas de H . El número de teselaciones 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 conforme invariante. Estos argumentos permitieron mostrar que ciertas variables mensurables de caminata aleatoria borrada en bucle son (en el límite) conformemente invariantes, y que el número esperado de vértices en una caminata aleatoria borrada en bucle se detuvo 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 . De manera muy aproximada, es una ecuación diferencial ordinaria estocástica conforme invariante que permite captar la propiedad de Markov de la caminata aleatoria borrada en bucle (y muchos otros procesos probabilísticos).
Tres dimensiones
El límite de escala existe y es invariante bajo rotaciones y dilataciones. [2] Sidenota el número esperado de vértices en la caminata aleatoria borrada en bucle hasta que llega a una distancia de r , entonces
donde ε, c y C son algunos números positivos [3] (los números pueden, en principio, ser calculadas a partir de las pruebas, pero el autor no lo hicieron). Esto sugiere que el límite de escala debería tener una dimensión de Hausdorff entrey 5/3 casi seguro. Los experimentos numéricos muestran que debería ser. [4]
Notas
- ^ Kenyon, R. (2000). El determinante asintótico del laplaciano discreto. Acta Mathematica, 185 (2), 239-286.
- ^ Kozma, Gady (2007) "El límite de escala de la caminata aleatoria borrada en bucle en tres dimensiones", Acta Mathematica , 199 (1), 29-152 doi : 10.1007 / s11511-007-0018-8 preprint
- ^ Lawler, Gregory F. (1999) "Paseo aleatorio borrado en bucle", en Problemas desconcertantes en probabilidad: Festschrift en honor de Harry Kesten (M. Bramson y RT Durrett, eds.), Progr. Probab., Vol. 44, Birkhäuser Boston, Boston, MA, 1999, págs. 197–217.
- ^ Wilson, David B. (2010) "La dimensión del paseo aleatorio borrado en bucle en 3D", Physical Review E , 82 (6): 062102.
Referencias
- Richard Kenyon, El determinante asintótico del laplaciano discreto , Acta Math. 185: 2 (2000), 239-286, versión en línea .
- Richard Kenyon, invariancia conforme del mosaico de dominó , Ann. Probab. 28: 2 (2000), 759-795, versión en línea .
- Richard Kenyon, propiedades de largo alcance de los árboles de expansión , técnicas probabilísticas en equilibrio y física estadística de no equilibrio, J. Math. Phys. 41: 3 (2000), 1338-1363, versión en línea .
- Gady Kozma, El límite de escala de la caminata aleatoria borrada en bucle en tres dimensiones , Acta Math. 199: 1 (2007), 29-152, versión en línea .
- Lawler, Gregory F. (septiembre de 1980). "Una caminata aleatoria para evitar uno mismo". Diario de matemáticas de Duke . 47 (3): 655–693. doi : 10.1215 / S0012-7094-80-04741-9 .
- Gregory F. Lawler, La corrección logarítmica para la caminata aleatoria borrada de bucles en cuatro dimensiones , Actas de la Conferencia en honor de Jean-Pierre Kahane ( Orsay , 1993). Número especial de J. Fourier Anal. Appl., 347-362.
- Gregory F. Lawler, Oded Schramm, Wendelin Werner , Invarianza conforme de caminatas aleatorias planas borradas en bucles y árboles de expansión uniforme , Ann. Probab. 32: 1B (2004), 939-995, versión en línea .
- Robin Pemantle, Elegir un árbol de expansión para el enrejado de enteros de manera uniforme , Ann. Probab. 19: 4 (1991), 1559-1574.
- Oded Schramm , Límites de escala de caminatas aleatorias borradas en bucle y árboles de expansión uniforme , Israel J. Math. 118 (2000), 221-288, versión en línea .
- David Bruce Wilson, Generación de árboles de expansión aleatorios más rápidamente que el tiempo de cobertura , Actas del 28º Simposio Anual de ACM sobre Teoría de la Computación (Filadelfia, PA, 1996), 296-303, ACM, Nueva York, 1996.