Camino aleatorio

Compartir Imprimir Citar

En matemáticas, una caminata aleatoria, paseo aleatorio o camino aleatorio es un proceso aleatorio que describe un camino que consiste en una sucesión de pasos aleatorios en algún espacio matemático.

Un ejemplo elemental de un paseo aleatorio es el paseo aleatorio en la línea de números enteros $matemáticas {Z}$ que comienza en 0, y en cada paso se mueve +1 o −1 con igual probabilidad. Otros ejemplos incluyen el camino trazado por una molécula mientras viaja en un líquido o un gas (ver movimiento browniano), el camino de búsqueda de un animal en busca de alimento o el precio de una acción fluctuante y el estado financiero de un jugador. Los paseos aleatorios tienen aplicaciones en la ingeniería y en muchos campos científicos, como la ecología, la psicología, la informática, la física, la química, la biología, la economía y la sociología. El término caminata aleatoria fue introducido por primera vez por Karl Pearson en 1905.

Recorrido aleatorio de celosía

Un modelo popular de paseo aleatorio es el de un paseo aleatorio en una red regular, donde en cada paso la ubicación salta a otro sitio de acuerdo con alguna distribución de probabilidad. En un paseo aleatorio simple, la ubicación solo puede saltar a sitios vecinos de la red, formando una ruta de red. En un paseo aleatorio simétrico simple sobre una red localmente finita, las probabilidades de que la ubicación salte a cada uno de sus vecinos inmediatos son las mismas. El ejemplo mejor estudiado es el de la caminata aleatoria en la red de enteros de dimensión d (a veces llamada red hipercúbica) $mathbb{Z} ^{d}$ .

Si el espacio de estados está limitado a dimensiones finitas, el modelo de caminata aleatoria se denomina caminata aleatoria simétrica con bordes simples, y las probabilidades de transición dependen de la ubicación del estado porque en los estados de margen y esquina el movimiento es limitado.

Paseo aleatorio unidimensional

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

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

Todos los posibles resultados de la caminata aleatoria después de 5 lanzamientos de una moneda justa

Para definir esta caminata formalmente, tome variables aleatorias independientes $Z_{1},Z_{2},puntos$ , donde cada variable es 1 o −1, con un 50% de probabilidad para cualquiera de los valores, y establezca $S_{0}=0$ y ${textstyle S_{n}=sum_{j=1}^{n}Z_{j}.}$ La serie ${ estilo de visualización {S_ {n} }}$ se llama la caminata aleatoria simple en. Esta serie (la suma de la secuencia de −1s y 1s) da la distancia neta recorrida, si cada parte de la caminata tiene una longitud de uno. La expectativa ${ estilo de visualización E (S_ {n})}$ de $S_{n}$ es cero. Es decir, la media de todos los lanzamientos de monedas 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:

{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 $E(Z_{n}^{2})=1$ , muestra que:

<img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/dc53b30ae698e97b1426672eff7fa528f9ed65d4" alt="{displaystyle E(S_{n}^{2})=sum_{i=1}^{n}E(Z_{i}^{2})+2sum_{1leq i

Esto sugiere que $E(|S_{n}|),!$ , la distancia de traslación esperada después de n pasos, debería ser del orden de ${ sqrt {n}}$ . De hecho,

{displaystyle lim _{nto infty }{frac {E(|S_{n}|)}{sqrt {n}}}={sqrt {frac {2}{pi }} }.}

Este resultado muestra que la difusión es ineficaz para mezclar debido a la forma en que se comporta la raíz cuadrada para grandes $norte$ .

Para responder a la pregunta de cuántas veces una caminata aleatoria cruzará una línea límite si se le permite continuar caminando para siempre, una caminata aleatoria simple $matemáticas {Z}$ cruzará cada punto un número infinito de veces. Este resultado tiene muchos nombres: el fenómeno del paso a nivel, la recurrencia o la ruina del jugador. La razón del apellido es la siguiente: un jugador con una cantidad finita de dinero eventualmente perderá cuando juegue un juego justo contra un banco 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 llegue primero a b o − a es ab. La probabilidad de que esta caminata llegue a b antes de − a es $a/(a+b)$ , que se puede derivar del hecho de que la caminata aleatoria simple es una martingala. Y estas expectativas y probabilidades de acierto se pueden calcular en ${ estilo de visualización O (a + b)}$ la cadena de Markov de caminata aleatoria unidimensional general.

Algunos de los resultados mencionados anteriormente pueden derivarse 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 el paseo aleatorio simple, cada uno de estos paseos 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 el paseo supere a los de −1 en k. De ello se deduce que +1 debe aparecer (n + k)/2 veces entre n pasos de un recorrido, por lo que el número de recorridos que satisfacen $S_{n}=k$ es igual al número de formas de elegir (n + k)/2 elementos de un nconjunto de elementos, denotado ${textstyle n elegir (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 son pares o impares. Por lo tanto, la probabilidad de que $S_{n}=k$ sea igual a ${estilo de texto 2^{-n}{n elegir (n+k)/2}}$ . Al representar las entradas del triángulo de Pascal en términos de factoriales y usar la fórmula de Stirling, se pueden obtener buenas estimaciones de estas probabilidades para valores grandes de $norte$ .

Si el espacio se limita a $matemáticas {Z}$ + por brevedad, la cantidad de formas en que una caminata aleatoria aterrizará en cualquier número dado que tenga cinco lanzamientos se puede mostrar como {0,5,0,4,0,1}.

Esta relación con el triángulo de Pascal se demuestra para valores pequeños de n. A cero vueltas, la única posibilidad será permanecer en cero. Sin embargo, en un turno, hay una posibilidad de caer en −1 o una posibilidad de caer en 1. En dos turnos, un marcador en 1 podría moverse a 2 o volver a cero. Un marcador en −1 podría moverse a −2 o volver a cero. Por lo tanto, hay una posibilidad de caer en −2, dos posibilidades de caer en cero y una posibilidad de caer en 2.

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

Como generalización directa, se pueden considerar caminatas aleatorias en redes cristalinas (gráficos de cobertura abeliana de pliegues infinitos sobre gráficos finitos). En realidad, es posible establecer el teorema del límite central y el teorema de la gran desviación en este contexto.

Como una cadena de Markov

Una caminata aleatoria unidimensional también se puede ver como una cadena de Markov cuyo espacio de _estado está dado por los $i=0,pm 1,pm 2,puntos.$ números enteros . por <img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0e012548bbb920982ecd319844e0c00267876213" alt=",0<p

{displaystyle ,P_{i,i+1}=p=1-P_{i,i-1}.}

Generalización heterogénea

Dimensiones superiores

En dimensiones superiores, el conjunto de puntos recorridos aleatoriamente tiene interesantes propiedades geométricas. De hecho, se obtiene un fractal discreto, es decir, un conjunto que exhibe autosimilitud estocástica a gran escala. En escalas pequeñas, se pueden observar "irregularidades" resultantes de la cuadrícula en la que se realiza la caminata. La trayectoria de una caminata aleatoria es la colección de puntos visitados, considerados como un conjunto sin tener en cuenta cuándo llegó la caminata al punto. En una dimensión, la trayectoria son simplemente todos los puntos entre la altura mínima y la altura máxima que alcanzó la caminata (ambos son, en promedio, del orden de $sqrt{n}$ ).

Para visualizar el caso bidimensional, uno puede imaginarse a una persona caminando aleatoriamente por una ciudad. La ciudad es efectivamente infinita y está dispuesta 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, se trata de un paseo aleatorio sobre el conjunto de todos los puntos del plano con coordenadas enteras.

Para responder a la pregunta de si la persona alguna vez regresa al punto de partida original de la caminata, este es el equivalente bidimensional del problema del paso a nivel discutido anteriormente. En 1921, George Pólya demostró que la persona casi seguramente lo haría en una caminata aleatoria bidimensional, pero para 3 dimensiones o más, la probabilidad de regresar al origen disminuye a medida que aumenta el número de dimensiones. En 3 dimensiones, la probabilidad disminuye a aproximadamente el 34%. Se sabe que 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".

Otra variación de esta pregunta que también hizo Pólya es: "si dos personas parten del mismo punto de partida, ¿se volverán a encontrar?" Se puede demostrar que la diferencia entre sus ubicaciones (dos paseos aleatorios independientes) también es un paseo aleatorio simple, por lo que es casi seguro que se encuentran de nuevo en un paseo bidimensional, pero para 3 dimensiones y más, la probabilidad disminuye con el número de los dimensiones. Paul Erdős y Samuel James Taylor también demostraron en 1960 que para dimensiones menores o iguales a 4, dos recorridos aleatorios independientes que comienzan desde dos puntos dados tienen un número infinito de intersecciones casi con certeza, pero para dimensiones mayores a 5, es casi seguro que se intersecan solo una frecuencia finita..

La función asintótica para un paseo aleatorio 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.

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

Relación con el proceso de Wiener

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, el proceso de Wiener se denomina "movimiento browniano", aunque estrictamente hablando, se trata de una confusión de un modelo con el fenómeno que se modela).

Un proceso de Wiener es el límite de escala de la caminata aleatoria en la dimensión 1. Esto significa que si hay 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 ε, es necesario realizar una caminata de longitud L / ε para aproximar una longitud de Wiener de L. Como 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 todos los caminos de longitud L con la topología máxima, y si M es el espacio de medida sobre B con la topología norma, entonces la convergencia está en el espaciom _ De manera similar, un proceso de Wiener en varias dimensiones es el límite de escala de la caminata aleatoria en el mismo número de dimensiones.

Una caminata aleatoria es un fractal discreto (una función con dimensiones enteras; 1, 2,...), pero la trayectoria de un proceso de Wiener es un verdadero fractal, y existe una conexión entre los dos. Por ejemplo, realice una caminata aleatoria hasta que llegue a un círculo de radio r veces la longitud del paso. El número promedio de pasos que realiza es r. Este hecho es la versión discreta del hecho de que un proceso de Wiener es un fractal de dimensión 2 de Hausdorff.

En dos dimensiones, el número promedio de puntos que tiene la misma caminata aleatoria en el límite de su trayectoria es r. 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 usando simulaciones pero probado solo en 2000 por Lawler, Schramm y Werner.

Un proceso de Wiener disfruta de muchas simetrías que no tiene un paseo aleatorio. Por ejemplo, la caminata de un proceso de Wiener es invariable a las rotaciones, pero la caminata aleatoria no lo es, ya que la cuadrícula subyacente no lo es (la caminata aleatoria es invariante a las rotaciones de 90 grados, pero los procesos de Wiener son invariantes a las rotaciones de, por ejemplo, 17 grados). también). Esto significa que, en muchos casos, los problemas en un recorrido aleatorio son más fáciles de resolver traduciéndolos a un proceso de Wiener, resolviendo el problema allí y luego traduciéndolos de vuelta. Por otro lado, algunos problemas son más fáciles de resolver con paseos aleatorios debido a su naturaleza discreta.

La caminata aleatoria y el proceso de Wiener pueden acoplarse, es decir, manifestarse en el mismo espacio de probabilidad de una manera dependiente que los obliga a estar bastante 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 de acuerdo con 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 de la caminata aleatoria, $varepsilon$ es el tamaño de un paso de la caminata aleatoria y $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, la caminata aleatoria 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:

{ estilo de visualización sigma ^ {2} = 6 , D , t.}

Igualando esta cantidad con la varianza asociada a la posición del caminante aleatorio, se obtiene el coeficiente de difusión equivalente a considerar 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}}{6delta t}}}

(válido solo en 3D).

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

Para 2D:

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

Para 1D:

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

Paseo aleatorio gaussiano

Una caminata aleatoria que tiene un tamaño de paso que varía según una distribución normal se usa como modelo para datos de series temporales del mundo real, como los mercados financieros. La fórmula de Black-Scholes para modelar los precios de las opciones, por ejemplo, utiliza un paseo aleatorio gaussiano como suposición subyacente.

Aquí, el tamaño del paso es la distribución normal acumulativa inversa $Phi^{-1}(z,mu,sigma)$ donde 0 ≤ z ≤ 1 es un número aleatorio distribuido uniformemente, y μ y σ son la media y las desviaciones estándar de la distribución normal, respectivamente.

Si μ es distinto de cero, la caminata aleatoria variará en torno a una tendencia lineal. Si v _s es el valor inicial de la caminata aleatoria, el valor esperado después de n pasos será v _s + n μ.

Para el caso especial donde μ es igual a cero, después de n pasos, la distribución de probabilidad de la distancia de traslación viene dada por N (0, n σ), donde N () es la notación para la distribución normal, n es el número de pasos, y σ es de la distribución normal acumulativa inversa como se indicó anteriormente.

Prueba: La caminata aleatoria gaussiana se puede considerar como la suma de una secuencia de variables aleatorias independientes e idénticamente distribuidas, X _i de la distribución normal acumulativa inversa con media igual a cero y σ de la distribución normal acumulativa inversa original:

pero tenemos la distribución para la suma de dos variables aleatorias independientes normalmente distribuidas, Z = X + Y, está dada por

{displaystyle {mathcal {N}}(mu_{X}+mu_{Y},sigma_{X}^{2}+sigma_{Y}^{2})}

(mira aquí).

En nuestro caso, μ _X = μ _Y = 0 y σ _X = σ _Y = σ rendimiento

{displaystyle {mathcal {N}}(0,2sigma ^{2})}

Por inducción, para n pasos tenemos ${displaystyle Zsim {mathcal {N}}(0,nsigma ^{2}).}$ Para pasos distribuidos de acuerdo con cualquier distribución con media cero y una varianza finita (no necesariamente solo una distribución normal), la distancia de traslación de raíz cuadrática media después de n pasos es

{displaystyle {sqrt {E|S_{n}^{2}|}}=sigma {sqrt {n}}.}

Pero para el paseo aleatorio gaussiano, esto es solo la desviación estándar de la distribución de la distancia de traslación después de n pasos. Por lo tanto, si μ es igual a cero, y dado que la distancia de traducción de la raíz cuadrada media (RMS) es una desviación estándar, hay un 68,27% de probabilidad de que la distancia de traducción RMS después de n pasos se encuentre entre ${ estilo de visualización pm sigma { sqrt {n}}}$ . Asimismo, existe un 50% de probabilidad de que la distancia de traslación después de n pasos se encuentre entre ${ estilo de visualización pm 0,6745 sigma { sqrt {n}}}$ .

Número de sitios distintos

La cantidad de sitios distintos visitados por un solo caminante aleatorio $S t)$ se ha estudiado ampliamente para redes cuadradas y cúbicas y para fractales. Esta cantidad es útil para el análisis de problemas de atrapamiento y reacciones cinéticas. También está relacionado con la densidad vibratoria de estados, procesos de reacciones de difusión y dispersión de poblaciones en ecología.

Tasa de información

La tasa de información de un paseo aleatorio gaussiano 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

{displaystyle R(D_{theta })={frac {1}{2}}int_{0}^{1}max{0,log_{2}left(S( varphi)/theta right)},dvarphi,}

{displaystyle D_{theta }=int _{0}^{1}min{S(varphi),theta },dvarphi,}

donde ${displaystyle S(varphi)=left(2sin(pi varphi /2)right)^{-2}}$ _ Por lo tanto, es imposible codificar ${displaystyle {{Z_{n}}_{n=1}^{N}}}$ usando 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 0">, existe un ${displaystyle Nen mathbb {N} }$ código lo suficientemente grande y binario de no más que ${displaystyle 2^{NR(D_{theta })}}$ elementos distintos, de modo 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}$ .

Aplicaciones

Como se mencionó, la variedad de fenómenos naturales que han sido objeto de intentos de descripción mediante algún tipo de caminata aleatoria es considerable, particularmente en física y química, ciencia de los materiales y biología. Las siguientes son algunas aplicaciones específicas de los paseos aleatorios:

En economía financiera, la hipótesis del paseo aleatorio se utiliza para modelar los precios de las acciones y otros factores. Los estudios empíricos encontraron algunas desviaciones de este modelo teórico, especialmente en las correlaciones a corto y largo plazo. Ver precios de las acciones.
En genética de poblaciones, el paseo aleatorio describe las propiedades estadísticas de la deriva genética.
En física, los paseos aleatorios se utilizan como modelos simplificados de movimiento y difusión brownianos físicos, como el movimiento aleatorio de moléculas en líquidos y gases. Véase, por ejemplo, agregación limitada por difusión. También en física, los paseos aleatorios y algunos de los paseos que interactúan entre sí juegan un papel en la teoría cuántica de campos.
En ecología matemática, los paseos aleatorios se utilizan para describir los movimientos de animales individuales, para respaldar empíricamente los procesos de biodifusión y, en ocasiones, para modelar la dinámica de la población.
En física de polímeros, el paseo aleatorio describe una cadena ideal. Es el modelo más simple para estudiar polímeros.
En otros campos de las matemáticas, la caminata aleatoria se usa para calcular soluciones a la ecuación de Laplace, para estimar la medida armónica y para varias construcciones en análisis y combinatoria.
En informática, los paseos aleatorios se utilizan para estimar el tamaño de la Web.
En la segmentación de imágenes, se utilizan paseos aleatorios para determinar las etiquetas (es decir, "objeto" o "fondo") para asociar con cada píxel. Este algoritmo se conoce típicamente como el algoritmo de segmentación del caminante aleatorio.

En la investigación del cerebro, los paseos aleatorios y los paseos aleatorios reforzados se utilizan para modelar cascadas de disparos de neuronas en el cerebro.
En la ciencia de la visión, la deriva ocular tiende a comportarse como un paseo aleatorio. Según algunos autores, los movimientos oculares de fijación en general también están bien descritos por un paseo aleatorio.
En psicología, los paseos aleatorios explican con precisión la relación entre el tiempo necesario para tomar una decisión y la probabilidad de que se tome una determinada decisión.
Los recorridos aleatorios se pueden utilizar para tomar muestras de un espacio de estado desconocido o muy grande, por ejemplo, para seleccionar una página aleatoria de Internet. En informática, este método se conoce como Markov Chain Monte Carlo (MCMC).

En las redes inalámbricas, se utiliza un recorrido aleatorio para modelar el movimiento de los nodos.
Las bacterias móviles participan en caminatas aleatorias sesgadas.
En física, los paseos aleatorios son la base del método de estimación de Fermi.
En la web, el sitio web de Twitter utiliza recorridos aleatorios para sugerir a quién seguir
Dave Bayer y Persi Diaconis han demostrado que 7 barajes rápidos son suficientes para mezclar un paquete de cartas (ver más detalles en barajar). Este resultado se traduce en una declaración sobre la caminata aleatoria en el grupo simétrico, que es lo que prueban, con un uso crucial de la estructura del grupo a través del análisis de Fourier.

Variantes

Se han considerado varios tipos de procesos estocásticos que son similares a los paseos aleatorios puros pero en los que se permite que la estructura simple sea más generalizada. La estructura pura se puede caracterizar porque los pasos están definidos por variables aleatorias independientes e idénticamente distribuidas. Los paseos aleatorios pueden tener lugar en una variedad de espacios, como gráficos, números enteros, la línea real, el plano o espacios vectoriales de dimensiones superiores, en superficies curvas o variedades de Riemann de dimensiones superiores y en grupos. También es posible definir paseos aleatorios que dan sus pasos en momentos aleatorios, y en ese caso, la posición X_ttiene que definirse para todos los tiempos t ∈ [0, +∞). Los casos específicos o límites de caminatas aleatorias incluyen los modelos de vuelo y difusión de Lévy, como el movimiento browniano.

En gráficos

Una caminata aleatoria de longitud k en un gráfico G posiblemente infinito con una raíz 0 es un proceso estocástico con variables aleatorias $X_{1},X_{2},puntos,X_{k}$ tales que $X_{1}=0$ y ${X_{i+1}}$ es un vértice elegido uniformemente al azar entre los vecinos de $X_{yo}$ . Entonces, el número $p_{v,w,k}(G)$ es la probabilidad de que una caminata aleatoria de longitud k que comience en v termine en w. En particular, si G es un gráfico con raíz 0, $p_{0,0,2k}$ es la probabilidad de que una $2k$ caminata aleatoria de pasos regrese a 0.

Sobre la base de la analogía de la sección anterior sobre dimensiones superiores, suponga ahora que nuestra ciudad ya no es una cuadrícula cuadrada perfecta. Cuando nuestra persona llega a un determinado cruce, elige entre los diversos caminos disponibles con la misma probabilidad. Así, si el cruce tiene siete salidas, la persona irá a cada una con una séptima probabilidad. Esta es una caminata aleatoria en un gráfico. ¿Llegará nuestra persona a su casa? Resulta que, en condiciones bastante suaves, la respuesta sigue siendo sí, pero según el gráfico, la respuesta a la pregunta variante "¿Se volverán a encontrar dos personas?" no puede ser que se encuentren infinitamente a menudo casi con seguridad.

Un ejemplo de un caso en el que la persona llegará a su casa casi con seguridad es cuando las longitudes de todos los bloques están entre a y b (donde a y b son dos números positivos finitos cualesquiera). Tenga en cuenta que no asumimos que el gráfico es plano, es decir, la ciudad puede contener túneles y puentes. Una forma de probar este resultado es utilizando la conexión a redes eléctricas. Tome un mapa de la ciudad y coloque una resistencia de un ohmio en cada bloque. Ahora mide la "resistencia entre un punto y el infinito". En otras palabras, elija algún número R y tome todos los puntos en la red eléctrica con una distancia mayor que Rdesde nuestro punto y cablearlos juntos. Esta es ahora una red eléctrica finita, y podemos medir la resistencia desde nuestro punto hasta los puntos cableados. Lleva R hasta el infinito. El límite se llama la resistencia entre un punto y el infinito. Resulta que lo siguiente es cierto (una prueba 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 es importante qué punto se elige si la gráfica es conexa.

En otras palabras, en un sistema transitorio, solo se necesita vencer 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.

Una caminata aleatoria en un gráfico es un caso muy especial de una cadena de Markov. A diferencia de una cadena de Markov general, la caminata aleatoria en un gráfico disfruta de una propiedad llamada simetría temporal o reversibilidad. En términos generales, esta propiedad, también llamada principio de equilibrio detallado, significa que las probabilidades de recorrer un camino dado en una dirección u otra tienen una conexión muy simple entre ellas (si la gráfica es regular, son simplemente iguales). Esta propiedad tiene consecuencias importantes.

A partir de la década de 1980, se han realizado muchas investigaciones para conectar las propiedades del gráfico con los recorridos aleatorios. Además de la conexión de la red eléctrica descrita anteriormente, existen conexiones importantes con las desigualdades isoperimétricas, vea más aquí, desigualdades funcionales como las desigualdades de Sobolev y Poincaré y las propiedades de las soluciones de la ecuación de Laplace. Una parte importante de esta investigación se centró en los gráficos de Cayley de grupos generados finitamente. En muchos casos, estos resultados discretos se trasladan o se derivan de variedades y grupos de Lie.

En el contexto de grafos aleatorios, particularmente el del modelo Erdős-Rényi, se han obtenido resultados analíticos de algunas propiedades de los caminantes aleatorios. Estos incluyen la distribución de los tiempos de primer y último golpe del caminante, donde el primer tiempo de golpe viene dado por la primera vez que el caminante entra en un sitio visitado previamente del gráfico, y el último tiempo de golpe corresponde a la primera vez que el caminante no puede realizar un movimiento adicional sin volver a visitar un sitio visitado anteriormente.

Una buena referencia para la caminata aleatoria en gráficos es el libro en línea de Aldous y Fill. Para grupos ver el libro de Woess. Si el kernel de transición $p(x,y)$ es en sí mismo aleatorio (basado en un entorno $omega$ ), entonces la caminata aleatoria se denomina "caminata aleatoria en un entorno aleatorio". Cuando la ley del paseo aleatorio incluye la aleatoriedad de $omega$ , la ley se denomina ley recocida; en cambio, si $omega$ se considera fija, la ley se llama ley extinguida. Véase el libro de Hughes, el libro de Revesz o las notas de lectura de Zeitouni.

Podemos pensar en elegir cada borde posible con la misma probabilidad que maximizar la incertidumbre (entropía) localmente. También podríamos hacerlo globalmente: en el paseo aleatorio de máxima entropía (MERW) queremos que todos los caminos sean igualmente probables, o en otras palabras: por cada dos vértices, cada camino de longitud dada es igualmente probable. Este paseo aleatorio tiene propiedades de localización mucho más fuertes.

Caminatas aleatorias auto-interactivas

Hay una serie de modelos interesantes de caminos aleatorios en los que cada paso depende del pasado de una manera complicada. Todos son más complejos para resolver analíticamente que la caminata aleatoria habitual; aún así, el comportamiento de cualquier modelo de un caminante aleatorio se puede obtener usando computadoras. Ejemplos incluyen:

El caminar autoevasivo.

La caminata autoevitable de longitud n on $mathbb{Z} ^{d}$ es la ruta aleatoria de n pasos que comienza en el origen, hace transiciones solo entre sitios adyacentes en $mathbb{Z} ^{d}$ , nunca vuelve a visitar un sitio y se elige uniformemente entre todas esas rutas. En dos dimensiones, debido al autoatrapamiento, una caminata típica para evitarse a sí mismo es muy corta, mientras que en una dimensión superior 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).

La caminata aleatoria borrada en bucle.
El paseo aleatorio reforzado.
El proceso de exploración.
El paseo aleatorio multiagente.

Paseos aleatorios sesgados en gráficos

Caminata aleatoria de máxima entropía

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

Paseos aleatorios correlacionados

Paseos aleatorios en los que la dirección del movimiento en un momento se correlaciona con la dirección del movimiento en el siguiente momento. Se utiliza para modelar los movimientos de los animales.

k	−5	−4	−3	−2	−1	0	1	2	3	4	5
$P[S_{0}=k]$						1
$2P[S_{1}=k]$					1		1
$2^{2}P[S_{2}=k]$				1		2		1
$2^{3}P[S_{3}=k]$			1		3		3		1
$2^{4}P[S_{4}=k]$		1		4		6		4		1
$2^{5}P[S_{5}=k]$	1		5		10		10		5		1