Paseo aleatorio con bucle borrado

{\displaystyle 10^{6}} — Un paseo aleatorio en 2D sin bucles para $10^{6}$ pasos.

En matemáticas , el paseo aleatorio sin bucles es un modelo de trayectoria simple aleatoria 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 de árbol aleatorio . Es un caso del tema más general de los paseos aleatorios .

Definición

Supongamos que G es algún grafo y $\gamma$ es algún camino de longitud n en G. En otras palabras, $\gamma (1),\dots,\gamma (n)$ son vértices de G tales que $\gamma (i)$ y $\gamma (i+1)$ están conectados por una arista. Luego, el borrado del bucle de $\gamma$ es un nuevo camino simple creado borrando todos los bucles de $\gamma$ en orden cronológico. Formalmente, definimos índices $i_{j}$ inductivamente usando

i_{1}=1\,

i_{j+1}=\max\{k:\gamma (k)=\gamma (i_{j})\}+1\,

donde "máx." aquí significa hasta la longitud del camino. $\gamma$ La inducción se detiene cuando para algunos $i_{j}$ tenemos $\gamma (i_ {j})=\gamma (n)$ .

En palabras, para encontrar $i_{j+1}$ , sostenemos $\gamma (i_ {j})$ Con una mano, y con la otra, retrocedemos desde el final: $\gamma (n),\gamma (n-1),...$ , hasta que encontremos alguno $\gamma (k)=\gamma (i_ {j})$ , en cuyo caso establecemos $i_{j+1}=k+1$ o terminamos en $\gamma (i_ {j})$ , en cuyo caso establecemos $i_{j+1}=i_{j}+1$ .

Supongamos que la inducción se detiene en J ie $\gamma (i_ {J})=\gamma (n)$ es el último $i_{J}$ . Luego, el borrado del bucle de $\gamma$ , denotado por $\mathrm {LE} (\gamma)$ es un camino simple de longitud J definido por

\mathrm {LE} (\gamma )(j)=\gamma (i_{j}).\,

Sea G un grafo, v un vértice de G y R un camino aleatorio sobre G que comienza en v . Sea T un tiempo de parada para R. Entonces, el camino aleatorio sin bucles hasta el tiempo T es LE( R ([1, T ])). En otras palabras, si tomamos R desde su inicio hasta T (que es un camino aleatorio) , eliminamos todos los bucles en orden cronológico como se indicó anteriormente y obtenemos un camino aleatorio simple.

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 considerar T como el tiempo de llegada a un conjunto. Por ejemplo, sea G el grafo Z² y sea R un paseo aleatorio que comienza en el punto (0,0). Sea T el tiempo en que R llega por primera vez al círculo de radio 100 (nos referimos aquí, por supuesto, a un círculo discretizado ). LE( R ) se denomina paseo aleatorio borrado del bucle que comienza en (0,0) y se detiene en el círculo.

árbol de expansión uniforme

Para cualquier grafo G , un árbol de expansión de G es un subgrafo de G que contiene todos los vértices y algunas de las aristas, es decir , un árbol conexo y sin ciclos . Un árbol de expansión elegido aleatoriamente entre todos los árboles de expansión posibles con igual probabilidad se denomina árbol de expansión uniforme. Normalmente existen exponencialmente muchos árboles de expansión (demasiados para generarlos todos y luego elegir uno al azar); en cambio, los árboles de expansión uniformes se pueden generar de forma más eficiente mediante un algoritmo llamado algoritmo de Wilson, que utiliza recorridos aleatorios sin bucles.

El algoritmo procede según los siguientes pasos. Primero, se construye un árbol T de un solo vértice eligiendo (arbitrariamente) un vértice. Luego, mientras el árbol T construido hasta el momento no incluya todos los vértices del grafo, sea v un vértice arbitrario que no esté en T , se realiza un recorrido aleatorio sin bucles desde v hasta alcanzar un vértice en T , y se agrega el camino resultante a T. Repitiendo este proceso hasta que se incluyan todos los vértices se obtiene un árbol con distribución uniforme, independientemente de la elección arbitraria de vértices en cada paso.

También se cumple la 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 un único camino. Recorrer este camino en el árbol de expansión uniforme da como resultado un camino simple aleatorio. Resulta que la distribución de este camino es idéntica a la distribución del paseo aleatorio sin bucles que comienza en v y termina en w . Este hecho puede usarse para justificar la corrección del algoritmo de Wilson. Otro corolario es que el paseo aleatorio sin bucles es simétrico en sus puntos de inicio y fin. Más precisamente, la distribución del paseo aleatorio sin bucles que comienza en v y termina en w es idéntica a la distribución de la reversión del paseo aleatorio sin bucles que comienza en w y termina en v . Eliminar los bucles de un paseo aleatorio y del paseo inverso no dan, en general, el mismo resultado, pero según este resultado, las distribuciones de los dos paseos sin bucles son idénticas.

El paseo aleatorio laplaciano

Otra representación de la caminata aleatoria sin bucles proviene de soluciones de la ecuación discreta de Laplace . Sea G nuevamente un grafo y sean v y w dos vértices en G. Construya un camino aleatorio de v a w inductivamente utilizando el siguiente procedimiento. Suponga que ya hemos definido $\gamma (1),...,\gamma (n)$ . Sea f una función de G a R que satisface

f(\gamma (i))=0

a pesar de

i\leq n

y

f(w)=1

f es discretamente armónica 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 definido, elige $\gamma (n+1)$ usando f en los vecinos de $\gamma (n)$ como pesos. En otras palabras, si $x_{1},...,x_{d}$ ¿Son estos vecinos? Elija $x_{i}$ con probabilidad

{\frac {f(x_{i})}{\sum _{j=1}^{d}f(x_{j})}}.

Continuando este proceso, recalculando f en cada paso, se obtendrá un camino simple aleatorio de v a w ; la distribución de este camino es idéntica a la de un paseo aleatorio sin bucles de v a w .

Una perspectiva alternativa es que la distribución de una caminata aleatoria sin bucles, condicionada a comenzar en algún camino β, es idéntica a la distribución sin bucles de una caminata aleatoria condicionada a no alcanzar β. Esta propiedad se conoce a menudo como la propiedad de Markov de la caminata aleatoria sin bucles (aunque la relación con la propiedad de Markov habitual es algo vaga).

Es importante señalar que, si bien la demostración de la equivalencia es bastante sencilla, los modelos que involucran 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 ni sobre la agregación limitada por difusión . Otro modelo algo relacionado es el explorador armónico .

Por último, cabe mencionar otro aspecto: el teorema de Kirchhoff relaciona el número de árboles generadores de un grafo G con los valores propios del laplaciano discreto . Para más detalles, consulte la sección sobre árboles generadores .

cuadrículas

Sea d la dimensión, que asumiremos que es al menos 2. Examine Z ^{d es} decir todos los puntos $(a_{1},...,a_{d})$ con entero $a_{i}$ Este es un grafo infinito de grado 2d cuando se conectan todos los puntos con sus vecinos más cercanos. De ahora en adelante, consideraremos un paseo aleatorio sin bucles en este grafo o en sus subgrafos.

Altas dimensiones

El caso más fácil de analizar es la dimensión 5 y superiores. En este caso, resulta que las intersecciones son solo locales. Un cálculo muestra que si se toma un paseo aleatorio de longitud n , su eliminación de bucles tiene una longitud del mismo orden de magnitud, es decir, n . Escalando en consecuencia, resulta que el paseo aleatorio sin bucles converge (en un sentido apropiado) al movimiento browniano cuando n tiende a infinito. La dimensión 4 es más complicada, pero la imagen general sigue siendo válida. Resulta que la eliminación de bucles de un paseo aleatorio de longitud n tiene aproximadamente $n/\log ^{1/3}n$ vértices, pero de nuevo, después del escalado (que tiene en cuenta el factor logarítmico), el paseo sin bucles converge al movimiento browniano.

Dos dimensiones

En dos dimensiones, los argumentos de la teoría de campos conformes y los resultados de simulaciones llevaron a una serie de conjeturas interesantes. Supongamos que D es un dominio simplemente conexo en el plano y x es un punto en D. Tomemos como gráfica G

G:=D\cap \varepsilon \mathbb {Z} ^{2},

Es decir, una cuadrícula de lado ε restringida a D. Sea v el vértice de G más cercano a x . Examinemos ahora un paseo aleatorio sin bucles que comienza en v y se detiene al alcanzar el "límite" de G , es decir, los vértices de G que corresponden al límite de D. Entonces las conjeturas son:

Cuando ε tiende a cero, la distribución de la trayectoria converge a alguna distribución en trayectorias simples desde x hasta el límite de D (diferente del movimiento browniano, por supuesto ; en 2 dimensiones las trayectorias del movimiento browniano no son simples). Esta distribución (denotemos por $S_{D,x}$ ) se denomina límite de escala del paseo aleatorio sin bucles.
Estas distribuciones son invariantes conformes . Es decir, si φ es una aplicación de Riemann entre D y un segundo dominio E, entonces

\phi (S_{D,x})=S_{E,\phi (x)}.\,

La dimensión de Hausdorff de estos caminos es casi con seguridad 5/4 .

El primer ataque a estas conjeturas provino de la dirección de los recubrimientos de dominó . Tomando un árbol de expansión de G y añadiéndole su dual planar se obtiene un recubrimiento de dominó de un grafo derivado especial (llamémoslo 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 sobre qué arista y qué arista sobre qué cara. Resulta que tomar un árbol de expansión uniforme de G conduce a un recubrimiento de dominó aleatorio uniformemente distribuido de H. El número de recubrimientos de dominó de un grafo se puede calcular utilizando el determinante de matrices especiales, que permiten conectarlo con la función de Green discreta que es aproximadamente conformemente invariante. Estos argumentos permitieron demostrar que ciertas medibles de la caminata aleatoria sin bucles son (en el límite) conformemente invariantes, y que el número esperado de vértices en una caminata aleatoria sin bucles detenida en un círculo de radio r es del orden de $r^{5/4}$ . ^{[ 1 ]}

En 2002, estas conjeturas se resolvieron (positivamente) mediante la evolución estocástica de Löwner . En términos generales, se trata de una ecuación diferencial ordinaria estocástica conformemente invariante que permite capturar la propiedad de Markov de la caminata aleatoria sin bucles (y muchos otros procesos probabilísticos).

Tres dimensiones

El límite de escala existe y es invariante bajo rotaciones y dilataciones. ^{[ 2 ]} Si $L(r)$ denota el número esperado de vértices en el paseo aleatorio sin bucles hasta que llega a una distancia de r , entonces

cr^{1+\varepsilon }\leq L(r)\leq Cr^{5/3}\,

donde ε, c y C son algunos números positivos ^{[ 3 ]} (los números pueden, en principio, calcularse a partir de las demostraciones, pero el autor no lo hizo). Esto sugiere que el límite de escala debería tener una dimensión de Hausdorff entre $1+\varepsilon$ y 5/3 casi con seguridad. Los experimentos numéricos muestran que debería ser $1.62400\pm 0.00005$ . ^{[ 4 ]}

Referencias

Kenyon, Richard (2000a), "El determinante asintótico del laplaciano discreto", Acta Mathematica , 185 (2): 239–286 , arXiv : math-ph/0011042 , doi : 10.1007/BF02392811
Kenyon, Richard (abril de 2000), "Invariancia conforme del teselado de dominó", Annals of Probability , 28 (2): 759–795 , arXiv : math-ph/9910002 , doi : 10.1214/aop/1019160260
Kenyon, Richard (marzo de 2000), "Propiedades de largo alcance de los árboles de expansión" , Journal of Mathematical Physics , 41 (3): 1338– 1363, Bibcode : 2000JMP....41.1338K , doi : 10.1063/1.533190 , archivado del original el 13 de noviembre de 2004.
Kozma, Gady (2007), "El límite de escala de la caminata aleatoria sin bucles en tres dimensiones", Acta Mathematica , 199 (1): 29–152 , arXiv : math.PR/0508344 , doi : 10.1007/s11511-007-0018-8
Lawler, Gregory F. (septiembre de 1980), "Un paseo aleatorio autoevitante", Duke Mathematical Journal , 47 (3): 655– 693, doi : 10.1215/S0012-7094-80-04741-9
Lawler, Gregory F. , «La corrección logarítmica para el paseo aleatorio sin bucles en cuatro dimensiones», Actas de la Conferencia en Honor de Jean-Pierre Kahane ( Orsay , 1993). Número especial del Journal of Fourier Analysis and Applications , pp. 347–362 , ISBN 978-0-429-33283-8
Lawler, Gregory F. (1999), "Paseo aleatorio sin bucles", en Bramson, Maury; Durrett, Richard T. (eds.), Problemas desconcertantes en probabilidad: Festschrift en honor a Harry Kesten , Progress in Probability, vol. 44, Birkhäuser, Boston, MA, pp. 197–217 , doi : 10.1007/978-1-4612-2168-5 , ISBN 978-1-4612-7442-1
Lawler, Gregory F.; Schramm , Oded ; Werner, Wendelin (2004), "Invariancia conforme de caminatas aleatorias planas sin bucles y árboles de expansión uniformes", Annals of Probability , 32 (1B): 939–995 , arXiv : math.PR/0112234 , doi : 10.1214/aop/1079021469
Pemantle, Robin (1991), "Elección uniforme de un árbol de expansión para la red entera", Annals of Probability , 19 (4): 1559–1574 , arXiv : math/0404043 , doi : 10.1214/aop/1176990223
Schramm, Oded (2000), "Límites de escala de paseos aleatorios sin bucles y árboles de expansión uniformes", Israel Journal of Mathematics , 118 : 221–288 , arXiv : math.PR/9904022 , doi : 10.1007/BF02803524
Wilson, David Bruce (1996), "Generación de árboles de expansión aleatorios más rápidamente que el tiempo de cobertura", STOC '96: Actas del Vigésimo Octavo Simposio Anual de la ACM sobre la Teoría de la Computación (Filadelfia, PA, 1996) , Association for Computing Machinery, Nueva York, pp. 296–303 , doi : 10.1145/237814.237880 , S2CID 207198080
Wilson, David Bruce (2010), "La dimensión de la caminata aleatoria sin bucles en tres dimensiones", Physical Review E , 82 (6) 062102, arXiv : 1008.1147 , Bibcode : 2010PhRvE..82f2102W , doi : 10.1103/PhysRevE.82.062102 , PMID 21230692
Wiese, Kay J.; Fedorenko, Andrei A. (2019), "Teorías de campo para caminatas aleatorias sin bucles", Nuclear Physics B , 946 114696, arXiv : 1802.08830 , doi : 10.1016/j.nuclphysb.2019.114696

[1] Kenyon (2000a)

[2] Kozma (2007)

[3] Lawler (1999)

[4] Wilson (2010)

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]