Paseo aleatorio

Un ejemplo elemental de paseo aleatorio es el paseo aleatorio en la recta numérica entera ,${\displaystyle \mathbb {Z} }$, que comienza en 0 y en cada paso se mueve +1 o −1 con igual probabilidad.

Este recorrido se puede ilustrar de la siguiente manera. Se coloca un marcador en cero en la recta numérica y se lanza una moneda justa. Si cae cara, el marcador se mueve una unidad a la derecha. Si cae cruz, el marcador se mueve una unidad a la izquierda. Después de cinco lanzamientos, el marcador podría estar ahora en -5, -3, -1, 1, 3, 5. Con cinco lanzamientos, tres caras y dos cruces, en cualquier orden, caerá en 1. Hay 10 maneras de caer en 1 (lanzando tres caras y dos cruces), 10 maneras de caer en -1 (lanzando tres cruces y dos caras), 5 maneras de caer en 3 (lanzando cuatro caras y una cruz), 5 maneras de caer en -3 (lanzando cuatro cruces y una cara), 1 manera de caer en 5 (lanzando cinco caras) y 1 manera de caer en -5 (lanzando cinco cruces). Consulte la siguiente figura para ver una ilustración de los posibles resultados de 5 lanzamientos.

Para definir formalmente este recorrido, tomemos variables aleatorias independientes.${\displaystyle Z_{1},Z_{2},\puntos }$, donde cada variable es 1 o −1, con una probabilidad del 50% para cualquiera de los dos valores, y se establece${\displaystyle S_{0}=0}$y${\textstyle S_{n}=\sum _{j=1}^{n}Z_{j}.}$La serie${\displaystyle \{S_{n}\}}$se llama paseo aleatorio simple en${\displaystyle \mathbb {Z} }$Esta serie (la suma de la secuencia de -1s y 1s) da la distancia neta recorrida, si cada parte del camino tiene una longitud de uno. La esperanza${\displaystyle E(S_{n})}$de${\displaystyle S_{n}}$es cero. Es decir, la media de todos los lanzamientos de moneda se aproxima a cero a medida que aumenta el número de lanzamientos. Esto se deduce de la propiedad de aditividad finita de la esperanza matemática: $${\displaystyle E(S_{n})=\sum _{j=1}^{n}E(Z_{j})=0.}$$

Un cálculo similar, utilizando la independencia de las variables aleatorias y el hecho de que${\displaystyle E(Z_{n}^{2})=1}$, muestra que: $${\displaystyle E(S_{n}^{2})=\sum _{i=1}^{n}E(Z_{i}^{2})+2\sum _{1\leq i<j\leq n}E(Z_{i}Z_{j})=n.}$$

Esto sugiere que${\displaystyle E(|S_{n}|)\,\!}$, la distancia de traslación esperada después de n pasos, debería ser del orden de${\displaystyle {\sqrt {n}}}$. De hecho, ^{[ 5 ]}$${\displaystyle \lim _{n\to \infty }{\frac {E(|S_{n}|)}{\sqrt {n}}}={\sqrt {\frac {2}{\pi }}}.}$$

Para responder a la pregunta de cuántas veces un paseo aleatorio cruzará una línea límite si se le permite continuar caminando para siempre, un paseo aleatorio simple en${\displaystyle \mathbb {Z} }$cruzará cada punto un número infinito de veces. Este resultado recibe muchos nombres: fenómeno de cruce de nivel , recurrencia o ruina del jugador . La razón de este último nombre es la siguiente: un jugador con una cantidad finita de dinero acabará perdiendo al jugar un juego justo contra una banca con una cantidad infinita de dinero. El dinero del jugador realizará un recorrido aleatorio, llegará a cero en algún momento y el juego terminará.

Si a y b son enteros positivos, entonces el número esperado de pasos hasta que una caminata aleatoria simple unidimensional que comienza en 0 alcance primero b o − a es ab . La probabilidad de que esta caminata alcance b antes que − a es${\displaystyle a/(a+b)}$, que se puede derivar del hecho de que un paseo aleatorio simple es una martingala . Y estas expectativas y probabilidades de acierto se pueden calcular en${\displaystyle O(a+b)}$en la cadena de Markov de paseo aleatorio unidimensional general.

Algunos de los resultados mencionados anteriormente se pueden derivar de las propiedades del triángulo de Pascal . El número de caminatas diferentes de n pasos donde cada paso es +1 o −1 es 2 ⁿ . Para la caminata aleatoria simple, cada una de estas caminatas es igualmente probable. Para que S _n sea igual a un número k, es necesario y suficiente que el número de +1 en la caminata supere al de −1 en k . De ello se deduce que +1 debe aparecer ( n  + k )/2 veces entre n pasos de una caminata, por lo tanto, el número de caminatas que satisfacen ${\displaystyle S_{n}=k}$es igual al número de maneras de elegir ( n  + k )/2 elementos de un conjunto de n elementos, ^{[ 6 ]} denotado ${\textstyle n \choose (n+k)/2}$Para que esto tenga sentido, es necesario que n  + k sea un número par, lo que implica que n y k sean ambos pares o ambos impares. Por lo tanto, la probabilidad de que ${\displaystyle S_{n}=k}$es igual a${\textstyle 2^{-n}{n \choose (n+k)/2}}$Al representar las entradas del triángulo de Pascal en términos de factoriales y utilizando la fórmula de Stirling , se pueden obtener buenas estimaciones para estas probabilidades para valores grandes de${\displaystyle n}$.

Esta relación con el triángulo de Pascal se demuestra para valores pequeños de n . En cero turnos, la única posibilidad es permanecer en cero. Sin embargo, en un turno, hay una probabilidad de caer en -1 o una probabilidad de caer en 1. En dos turnos, una ficha en 1 podría moverse a 2 o volver a cero. Una ficha en -1 podría moverse a -2 o volver a cero. Por lo tanto, hay una probabilidad de caer en -2, dos probabilidades de caer en cero y una probabilidad de caer en 2.

El teorema del límite central y la ley del logaritmo iterado describen aspectos importantes del comportamiento de las caminatas aleatorias simples en${\displaystyle \mathbb {Z} }$. En particular, lo primero implica que a medida que n aumenta, las probabilidades (proporcionales a los números en cada fila) se aproximan a una distribución normal .

Para ser precisos, sabiendo que${\textstyle \mathbb {P} (X_{n}=k)=2^{-n}{\binom {n}{(n+k)/2}}}$y usando la fórmula de Stirling se tiene

$${\displaystyle {\log \mathbb {P} (X_{n}=k)}=n\left[\left({1+{\frac {k}{n}}+{\frac {1}{2n}}}\right)\log \left(1+{\frac {k}{n}}\right)+\left({1-{\frac {k}{n}}+{\frac {1}{2n}}}\right)\log \left(1-{\frac {k}{n}}\right)\right]+\log {\frac {\sqrt {2}}{\sqrt {\pi }}}+o(1).}$$

Corregir el escalado${\textstyle k=\lfloor {\sqrt {n}}x\rfloor }$, para${\textstyle x}$fijo y utilizando la expansión${\textstyle \log(1+{k}/{n})=k/n-k^{2}/2n^{2}+\dots }$cuando${\textstyle k/n}$desaparece, sigue

$${\displaystyle {\mathbb {P} \left({\frac {X_{n}}{n}}={\frac {\lfloor {\sqrt {n}}x\rfloor }{\sqrt {n}}}\right)}={\frac {1}{\sqrt {n}}}{\frac {1}{2{\sqrt {\pi }}}}e^{-{x^{2}}}(1+o(1)).}$$

tomando el límite (y observando que${\textstyle {1}/{\sqrt {n}}}$corresponde al espaciado de la cuadrícula de escalado) se encuentra la densidad gaussiana${\textstyle f(x)={\frac {1}{2{\sqrt {\pi }}}}e^{-{x^{2}}}}$De hecho, para una variable aleatoria absolutamente continua${\textstyle X}$con densidad${\textstyle f_{X}}$lo sostiene${\textstyle \mathbb {P} \left(X\in [x,x+dx)\right)=f_{X}(x)dx}$, con${\textstyle dx}$correspondiente a un espaciado infinitesimal.

Como generalización directa, se pueden considerar caminatas aleatorias en redes cristalinas (grafos de recubrimiento abelianos de pliegue infinito sobre grafos finitos). De hecho, es posible establecer el teorema del límite central y el teorema de grandes desviaciones en este contexto. ^{[ 7 ] [ 8 ]}

En dimensiones superiores, el conjunto de puntos recorridos aleatoriamente tiene propiedades geométricas interesantes. De hecho, se obtiene un fractal discreto , es decir, un conjunto que exhibe autosimilitud estocástica a gran escala. A pequeña escala, se puede observar una "irregularidad" resultante de la cuadrícula sobre la que se realiza el recorrido. La trayectoria de un recorrido aleatorio es la colección de puntos visitados, considerados como un conjunto sin tener en cuenta cuándo llegó el recorrido a cada punto. En una dimensión, la trayectoria es simplemente todos los puntos entre la altura mínima y la altura máxima alcanzada por el recorrido (ambas son, en promedio, del orden de${\displaystyle {\sqrt {n}}}$).

Para visualizar el caso bidimensional, podemos imaginar a una persona caminando aleatoriamente por una ciudad. La ciudad es prácticamente infinita y está organizada en una cuadrícula cuadrada de aceras. En cada intersección, la persona elige aleatoriamente una de las cuatro rutas posibles (incluida la ruta original). Formalmente, esto es un paseo aleatorio sobre el conjunto de todos los puntos del plano con coordenadas enteras .

Para responder a la pregunta de si una persona puede regresar al punto de partida original de la caminata, este es el equivalente bidimensional del problema del cruce de nivel mencionado anteriormente. En 1921, George Pólya demostró que la persona casi con seguridad regresaría al origen en una caminata aleatoria bidimensional, pero para tres dimensiones o más, la probabilidad de regresar al origen disminuye a medida que aumenta el número de dimensiones. En tres dimensiones, la probabilidad disminuye a aproximadamente un 34 %. ^{[ 9 ]} El matemático Shizuo Kakutani se refirió a este resultado con la siguiente cita: «Un hombre borracho encontrará el camino a casa, pero un pájaro borracho puede perderse para siempre». ^{[ 10 ]}

La probabilidad de recurrencia es en general${\displaystyle p=1-\left({\frac {1}{(2\pi )^{d}}}\int _{[-\pi ,\pi ]^{d}}{\frac {\prod _{i=1}^{d}d\theta _{i}}{1-{\frac {1}{d}}\sum _{i=1}^{d}\cos \theta _{i}}}\right)^{-1}}$, que se pueden derivar mediante funciones generadoras ^{[ 11 ]} o procesos de Poisson. ^{[ 12 ]}

Otra variante de esta pregunta, también planteada por Pólya, es: «Si dos personas parten del mismo punto, ¿volverán a encontrarse alguna vez?» ^{[ 13 ]} Se puede demostrar que la diferencia entre sus ubicaciones (dos caminatas aleatorias independientes) también es una caminata aleatoria simple, por lo que casi con seguridad se encontrarán de nuevo en una caminata bidimensional, pero para tres dimensiones o más, la probabilidad disminuye con el número de dimensiones. Paul Erdős y Samuel James Taylor también demostraron en 1960 que, para dimensiones menores o iguales a cuatro, dos caminatas aleatorias independientes que parten de dos puntos cualesquiera tienen infinitas intersecciones casi con seguridad, pero para dimensiones mayores a cinco, casi con seguridad se intersecan solo con una frecuencia finita. ^{[ 14 ]}

La función asintótica para una caminata aleatoria bidimensional a medida que aumenta el número de pasos viene dada por una distribución de Rayleigh . La distribución de probabilidad es una función del radio desde el origen y la longitud del paso es constante para cada paso. Aquí, se supone que la longitud del paso es 1, N es el número total de pasos y r es el radio desde el origen. ^{[ 15 ]}

$${\displaystyle P(r)={\frac {2r}{N}}e^{-r^{2}/N}}$$

Un proceso de Wiener es un proceso estocástico con un comportamiento similar al movimiento browniano , el fenómeno físico de una partícula diminuta que se difunde en un fluido. (A veces, al proceso de Wiener se le llama "movimiento browniano", aunque, estrictamente hablando, esto es una confusión entre el modelo y el fenómeno que se está modelando).

Un proceso de Wiener es el límite de escala de una caminata aleatoria en dimensión 1. Esto significa que si existe una caminata aleatoria con pasos muy pequeños, existe una aproximación a un proceso de Wiener (y, con menor precisión, al movimiento browniano). Para ser más precisos, si el tamaño del paso es ε, se necesita una caminata de longitud L /ε ² para aproximar una longitud de Wiener de L . A medida que el tamaño del paso tiende a 0 (y el número de pasos aumenta proporcionalmente), la caminata aleatoria converge a un proceso de Wiener en un sentido apropiado. Formalmente, si B es el espacio de todas las trayectorias de longitud L con la topología máxima, y ​​si M es el espacio de medida sobre B con la topología de norma, entonces la convergencia se da en el espacio M . De manera similar, un proceso de Wiener en varias dimensiones es el límite de escala de una caminata aleatoria en el mismo número de dimensiones.

Un paseo aleatorio es un fractal discreto (una función con dimensiones enteras: 1, 2, ...), pero la trayectoria de un proceso de Wiener es un fractal verdadero, y existe una conexión entre ambos. Por ejemplo, consideremos un paseo aleatorio hasta que alcance un círculo de radio r multiplicado por la longitud del paso. El número promedio de pasos que realiza es r² ^. Este hecho constituye la versión discreta del hecho de que un paseo de un proceso de Wiener es un fractal de dimensión de Hausdorff 2. 

En dos dimensiones, el número promedio de puntos que tiene el mismo paseo aleatorio en el límite de su trayectoria es r ^4/3 . Esto corresponde al hecho de que el límite de la trayectoria de un proceso de Wiener es un fractal de dimensión 4/3, un hecho predicho por Mandelbrot mediante simulaciones, pero demostrado recién en 2000 por Lawler , Schramm y Werner . ^{[ 16 ]}

Un proceso de Wiener posee muchas simetrías que un paseo aleatorio no tiene. Por ejemplo, un paseo de Wiener es invariante a las rotaciones, mientras que un paseo aleatorio no lo es, dado que la cuadrícula subyacente no lo es (un paseo aleatorio es invariante a rotaciones de 90 grados, pero los procesos de Wiener también lo son, por ejemplo, a rotaciones de 17 grados). Esto significa que, en muchos casos, los problemas en un paseo aleatorio se resuelven más fácilmente transformándolos a un proceso de Wiener, resolviéndolos allí y luego volviendo a transformarlos. Por otro lado, algunos problemas se resuelven más fácilmente con paseos aleatorios debido a su naturaleza discreta.

Los paseos aleatorios y los procesos de Wiener pueden acoplarse , es decir, manifestarse en el mismo espacio de probabilidad de forma dependiente, lo que los obliga a estar muy cerca. El acoplamiento más simple es la incrustación de Skorokhod , pero existen acoplamientos más precisos, como el teorema de aproximación de Komlós-Major-Tusnády .

La convergencia de una caminata aleatoria hacia el proceso de Wiener está controlada por el teorema del límite central y por el teorema de Donsker . Para una partícula en una posición fija conocida en t  =  0, el teorema del límite central nos dice que después de un gran número de pasos independientes en la caminata aleatoria, la posición del caminante se distribuye según una distribución normal de varianza total :

$${\displaystyle \sigma ^{2}={\frac {t}{\delta t}}\,\varepsilon ^{2},}$$

donde t es el tiempo transcurrido desde el inicio del paseo aleatorio,${\displaystyle \varepsilon }$es el tamaño de un paso del paseo aleatorio, y${\displaystyle \delta t}$es el tiempo transcurrido entre dos pasos sucesivos.

Esto corresponde a la función de Green de la ecuación de difusión que controla el proceso de Wiener, lo que sugiere que, después de un gran número de pasos, el paseo aleatorio converge hacia un proceso de Wiener.

En 3D, la varianza correspondiente a la función de Green de la ecuación de difusión es: $${\displaystyle \sigma ^{2}=6\,D\,t.}$$

Al igualar esta cantidad con la varianza asociada a la posición del caminante aleatorio, se obtiene el coeficiente de difusión equivalente que debe considerarse para el proceso asintótico de Wiener hacia el cual converge el paseo aleatorio después de un gran número de pasos: $${\displaystyle D={\frac {\varepsilon ^{2}}{6\delta t}}}$$(Válido solo en 3D).

Las dos expresiones de la varianza anteriores corresponden a la distribución asociada al vector${\displaystyle {\vec {R}}}$que une los dos extremos del paseo aleatorio, en 3D. La varianza asociada a cada componente${\displaystyle R_{x}}$,${\displaystyle R_{y}}$o${\displaystyle R_{z}}$es solo un tercio de este valor (todavía en 3D).

Para 2D: ^{[ 17 ]}

$${\displaystyle D={\frac {\varepsilon ^{2}}{4\delta t}}.}$$

Para 1D: ^{[ 18 ]}

$${\displaystyle D={\frac {\varepsilon ^{2}}{2\delta t}}.}$$

El número de sitios distintos visitados por un único caminante aleatorio.${\displaystyle S(t)}$Se ha estudiado extensamente para redes cuadradas y cúbicas y para fractales. ^{[ 19 ] [ 20 ]} Esta magnitud es útil para el análisis de problemas de atrapamiento y reacciones cinéticas. También está relacionada con la densidad vibracional de estados, ^{[ 21 ] [ 22 ]} procesos de reacciones de difusión ^{[ 23 ]} y propagación de poblaciones en ecología. ^{[ 24 ] [ 25 ]}

La tasa de información de una caminata aleatoria gaussiana con respecto a la distancia de error al cuadrado, es decir, su función de distorsión de tasa cuadrática , viene dada paramétricamente por ^{[ 26 ].}$${\displaystyle R(D_{\theta })={\frac {1}{2}}\int _{0}^{1}\max\{0,\log _{2}\left(S(\varphi )/\theta \right)\}\,d\varphi ,}$$$${\displaystyle D_{\theta }=\int _{0}^{1}\min\{S(\varphi ),\theta \}\,d\varphi ,}$$ dónde${\displaystyle S(\varphi )=\left(2\sin(\pi \varphi /2)\right)^{-2}}$Por lo tanto, es imposible codificar.${\displaystyle {\{Z_{n}\}_{n=1}^{N}}}$utilizando un código binario de menos de${\displaystyle NR(D_{\theta })}$bits y recuperarlo con un error cuadrático medio esperado menor que${\displaystyle D_{\theta }}$. Por otro lado, para cualquier${\displaystyle \varepsilon >0}$, existe un${\displaystyle N\in \mathbb {N} }$lo suficientemente grande y un código binario de no más de${\displaystyle 2^{NR(D_{\theta })}}$elementos distintos tales que el error cuadrático medio esperado en la recuperación${\displaystyle {\{Z_{n}\}_{n=1}^{N}}}$de este código es como máximo${\displaystyle D_{\theta }-\varepsilon }$.

En economía financiera , la hipótesis del paseo aleatorio se utiliza para modelar los precios de las acciones y otros factores. ^{[ 27 ]} Los estudios empíricos encontraron algunas desviaciones de este modelo teórico, especialmente en las correlaciones a corto y largo plazo .

En la fabricación de semiconductores , se utilizan paseos aleatorios para analizar los efectos del tratamiento térmico en nodos más pequeños. Se aplican para comprender la difusión de dopantes , defectos y otras impurezas durante las etapas críticas de fabricación. Los tratamientos de paseo aleatorio también se utilizan para estudiar la difusión de reactivos, productos y plasma durante los procesos de deposición química en fase vapor ( CVD). La difusión continua se ha utilizado para estudiar el flujo de gases, a escalas macroscópicas, en reactores CVD. Sin embargo, las dimensiones más pequeñas y la mayor complejidad nos han obligado a tratarlos con paseos aleatorios. Esto permite un análisis preciso de los procesos estocásticos , a nivel molecular y menores, en la fabricación de semiconductores.

En ciencias de la computación , se han utilizado caminatas aleatorias para estimar el tamaño de la Web . ^{[ 28 ]} En programación de computadoras es posible calcular pi con una caminata aleatoria. ^{[ 29 ]}

Los paseos aleatorios se han utilizado en el análisis de redes para calcular la probabilidad de que dos nodos no conectados se conecten en el futuro, basándose en el estado actual de la red. En ^{[ 30 ]} se analizan varios algoritmos , incluidos PageRank y los paseos aleatorios supervisados.

En la segmentación de imágenes , se utilizan recorridos aleatorios para determinar las etiquetas (es decir, "objeto" o "fondo") que se asocian a cada píxel. ^{[ 31 ]} Este algoritmo se conoce comúnmente como algoritmo de segmentación de recorrido aleatorio .

El sitio web de Twitter utilizó recorridos aleatorios para hacer sugerencias sobre a quién seguir. ^{[ 32 ]}

Como se mencionó, la variedad de fenómenos naturales que han sido objeto de intentos de descripción mediante algún tipo de caminatas aleatorias es considerable. Este es el caso particularmente en los campos de la física, ^{[ 33 ] [ 34 ]} la química, ^{[ 35 ]} la ciencia de los materiales , ^{[ 36 ] [ 37 ]} y la biología. ^{[ 38 ] [ 39 ] [ 40 ]}

Un paseo aleatorio de longitud k en un grafo G posiblemente infinito con raíz 0 es un proceso estocástico con variables aleatorias.${\displaystyle X_{1},X_{2},\dots ,X_{k}}$de tal manera que${\displaystyle X_{1}=0}$y ${\displaystyle {X_{i+1}}}$es un vértice elegido uniformemente al azar entre los vecinos de${\displaystyle X_{i}}$. Entonces el número${\displaystyle p_{v,w,k}(G)}$es la probabilidad de que un paseo aleatorio de longitud k que comienza en v termine en w . En particular, si G es un grafo con raíz 0 ,${\displaystyle p_{0,0,2k}}$es la probabilidad de que un${\displaystyle 2k}$-El paseo aleatorio de -pasos regresa a 0 .

Partiendo de la analogía de la sección anterior sobre dimensiones superiores, supongamos ahora que nuestra ciudad ya no es una cuadrícula cuadrada perfecta. Cuando nuestra persona llega a una intersección determinada, elige entre las distintas carreteras disponibles con igual probabilidad. Así, si la intersección tiene siete salidas, la persona irá a cada una con una probabilidad de un séptimo. Esto es un paseo aleatorio en un grafo. ¿Llegará nuestra persona a su casa? Resulta que, bajo condiciones bastante suaves, la respuesta sigue siendo sí, ^{[ 48 ]} pero dependiendo del grafo, la respuesta a la pregunta variante "¿Se volverán a encontrar dos personas?" puede no ser que se encuentren infinitas veces casi con seguridad. ^{[ 49 ]}

Un ejemplo de un caso en el que la persona llegará a su casa casi con seguridad es cuando las longitudes de todas las manzanas están entre a y b (donde a y b son dos números positivos finitos cualesquiera). Nótese que no asumimos que el grafo sea plano , es decir, la ciudad puede contener túneles y puentes. Una forma de demostrar este resultado es utilizando la conexión con las redes eléctricas . Tomemos un mapa de la ciudad y coloquemos una resistencia de un ohmio en cada manzana. Ahora midamos la "resistencia entre un punto y el infinito". En otras palabras, elijamos un número R y tomemos todos los puntos de la red eléctrica cuya distancia a nuestro punto sea mayor que R y conectémoslos entre sí. Esta es ahora una red eléctrica finita, y podemos medir la resistencia desde nuestro punto hasta los puntos conectados. Hagamos que R tienda a infinito. El límite se llama resistencia entre un punto y el infinito . Resulta que lo siguiente es cierto (una demostración elemental se puede encontrar en el libro de Doyle y Snell):

Teorema : Un grafo es transitorio si y solo si la resistencia entre un punto y el infinito es finita. No importa qué punto se elija si el grafo es conexo.

En otras palabras, en un sistema transitorio, basta con superar una resistencia finita para llegar al infinito desde cualquier punto. En un sistema recurrente, la resistencia desde cualquier punto hasta el infinito es infinita.

Esta caracterización de la transitoriedad y la recurrencia es muy útil y, en concreto, nos permite analizar el caso de una ciudad dibujada en el plano con las distancias acotadas.

Un paseo aleatorio en un grafo es un caso muy especial de cadena de Markov . A diferencia de una cadena de Markov general, un paseo aleatorio en un grafo posee una propiedad llamada simetría temporal o reversibilidad . En términos generales, esta propiedad, también conocida como principio de equilibrio detallado , implica que las probabilidades de recorrer un camino determinado en una dirección u otra tienen una relación muy simple entre sí (si el grafo es regular , son iguales). Esta propiedad tiene consecuencias importantes.

A partir de la década de 1980, se ha investigado mucho sobre la relación entre las propiedades de los grafos y los paseos aleatorios. Además de la conexión con las redes eléctricas descrita anteriormente, existen importantes conexiones con las desigualdades isoperimétricas (véase más información aquí) , las desigualdades funcionales como las de Sobolev y Poincaré , y las propiedades de las soluciones de la ecuación de Laplace . Una parte significativa de esta investigación se centró en los grafos de Cayley de grupos finitamente generados . En muchos casos, estos resultados discretos se extienden a las variedades y los grupos de Lie , o se derivan de ellos .

En el contexto de los grafos aleatorios , en particular el del modelo de Erdős-Rényi , se han obtenido resultados analíticos sobre algunas propiedades de los caminantes aleatorios. Estos incluyen la distribución de los tiempos de primer ^{[ 50 ]} y último impacto ^{[ 51 ]} del caminante, donde el primer impacto viene dado por la primera vez que el caminante entra en un sitio previamente visitado del grafo, y el último impacto corresponde a la primera vez que el caminante no puede realizar un movimiento adicional sin volver a visitar un sitio previamente visitado.

Una buena referencia para paseos aleatorios en grafos es el libro en línea de Aldous y Fill . Para grupos, consulte el libro de Woess. Si el núcleo de transición${\displaystyle p(x,y)}$es en sí mismo aleatorio (basado en un entorno)${\displaystyle \omega }$) entonces el paseo aleatorio se llama "paseo aleatorio en un entorno aleatorio". Cuando la ley del paseo aleatorio incluye la aleatoriedad de${\displaystyle \omega }$, la ley se llama ley recocida; por otro lado, si${\displaystyle \omega }$Si se considera fija, la ley se denomina ley extinguida. Véase el libro de Hughes, el libro de Revesz o los apuntes de clase de Zeitouni.

Podemos pensar en elegir cada arista posible con la misma probabilidad como maximizar la incertidumbre (entropía) localmente. También podríamos hacerlo globalmente: en el paseo aleatorio de entropía máxima (MERW) queremos que todos los caminos sean igualmente probables, o dicho de otro modo: para cada par de vértices, cada camino de longitud dada es igualmente probable. ^{[ 52 ]} Este paseo aleatorio tiene propiedades de localización mucho más fuertes.

Existen varios modelos interesantes de trayectorias aleatorias en los que cada paso depende del pasado de una manera compleja. Todos son más complejos de resolver analíticamente que el paseo aleatorio habitual; sin embargo, el comportamiento de cualquier modelo de un caminante aleatorio se puede obtener mediante ordenadores. Algunos ejemplos son:

• La caminata autoevitante . ^{[ 53 ]}

El paseo autoevitante de longitud n en${\displaystyle \mathbb {Z} ^{d}}$es la ruta aleatoria de n pasos que comienza en el origen, hace transiciones solo entre sitios adyacentes en${\displaystyle \mathbb {Z} ^{d}}$Nunca vuelve a visitar un sitio y se elige uniformemente entre todos esos caminos. En dos dimensiones, debido al autoatrapamiento, un típico recorrido autoevitante es muy corto, ^{[ 54 ]} mientras que en dimensiones superiores crece más allá de todos los límites. Este modelo se ha utilizado a menudo en la física de polímeros (desde la década de 1960).

• El paseo aleatorio sin bucles . ^{[ 55 ] [ 56 ]}
• El paseo aleatorio reforzado . ^{[ 57 ]}
• El proceso de exploración .
• El paseo aleatorio multiagente . ^{[ 58 ]}

Un paseo aleatorio elegido para maximizar la tasa de entropía tiene propiedades de localización mucho más fuertes.

Caminatas aleatorias donde la dirección del movimiento en un momento está correlacionada con la dirección del movimiento en el siguiente momento. Se utiliza para modelar los movimientos de los animales. ^{[ 59 ] [ 60 ]}