En matemáticas , economía y física teórica , una caminata aleatoria es un modelo matemático de un sistema que tiene una dinámica discreta compuesta por una sucesión de pasos aleatorios , o tomada "al azar". También se utilizan con frecuencia expresiones de caminata aleatoria , caminata aleatoria o caminata aleatoria en inglés. Además, estos pasos aleatorios están totalmente descorrelacionados entre sí; esta última propiedad fundamental se denomina carácter markoviano del proceso, que lleva el nombre del matemático Markov . Intuitivamente significa que en cada momento, el futuro del sistema depende de su estado presente, pero no de su pasado, ni siquiera del más cercano. En otras palabras, el sistema "pierde memoria" a medida que evoluciona con el tiempo. Por esta razón, un paseo aleatorio a veces también se denomina "paseo en estado de ebriedad".
Este modelo matemático permite dar cuenta de ciertos fenómenos naturales, cuyo ejemplo más famoso es el movimiento browniano , que corresponde por ejemplo a los movimientos aparentemente aleatorios de las partículas presentes en el fluido interno de un grano de polen.
En matemáticas o ciencias de la computación, a menudo estudiamos paseos aleatorios en redes regulares o en gráficos más complejos. Este es, por ejemplo, el método que utiliza el motor de búsqueda de Google para navegar, identificar y clasificar las páginas de la red de Internet .
Técnicamente, los paseos aleatorios son el dominio de la teoría de la probabilidad . Un paseo aleatorio es de hecho un proceso estocástico del tipo de cadena de Markov . Se divide en unidades elementales llamadas pasos , cuya longitud puede ser constante, aleatoria o fija por la red o el gráfico en el que viajamos. En cada paso, existe, por tanto, un abanico de posibilidades para seleccionar aleatoriamente la dirección y el tamaño del paso. Esta gama de posibilidades puede ser discreta (elección entre un número finito de valores) o continua .
La idea de la caminata aleatoria fue introducida (sin el nombre) en 1905 por el bioestadístico Karl Pearson para explicar las migraciones de una población de mosquitos en un bosque. Pearson hace la siguiente pregunta:
“Un hombre parte del punto O y camina 1 yarda (0,914 m ) en línea recta; gira en cualquier ángulo y vuelve a caminar los metros en línea recta. Repite este proceso n veces. Pregunto la probabilidad de que después de n de estos viajes, esté a una distancia entre r y r + dr desde su punto de partida. "
La respuesta a esta pregunta la proporciona Lord Rayleigh una semana después en el siguiente número de la revista Nature : cuando n es lo suficientemente grande, esta probabilidad es:
.Si Rayleigh da la respuesta tan rápidamente es porque en 1880 él mismo estudió un problema relacionado: el comportamiento de una superposición de ondas acústicas todas de la misma amplitud, pero de fases aleatorias. Pearson se encuentra con Rayleigh en10 de agosto :
“Debería haberlo sabido, pero mi lectura en los últimos años se ha desplazado a otras áreas de interés, y no esperaría encontrar el primer paso en un problema biométrico en una disertación sobre acústica. "
Pearson luego continúa:
“La lección de la solución de Lord Rayleigh es que en un campo abierto, el lugar más probable para encontrar un borracho que aún pueda pararse de pie es en las cercanías de su punto de partida. "
El término "caminata aleatoria" no fue introducido hasta alrededor de 1919-1921 por el matemático húngaro George Pólya , quien usó la palabra alemana " Irrfahrt ".
El modelo de paseo aleatorio más simple es el paseo aleatorio discreto unidimensional en la red periódica ℤ. Para formar un ejemplo concreto, podemos imaginar a un individuo (o "partícula") en una escalera, que lanza una moneda para decidir si el siguiente escalón será hacia arriba o hacia abajo. En cada paso, solo hay dos posibilidades: en este ejemplo, un paso adelante o un paso atrás. El único parámetro libre del problema es la probabilidad de que la partícula salte hacia adelante (en lugar de saltar hacia atrás).
Si nombramos esta probabilidad por el número real p tal que: 0 < p <1 , entonces q = 1 - p representa la probabilidad de que la partícula salte hacia atrás .
El caso más simple, que corresponde por ejemplo al movimiento browniano, consiste en formular la hipótesis de isotropía espacial . Siendo las direcciones "adelante / atrás" del espacio físico equivalentes a priori , establecemos la equiprobabilidad :
Es notable que las leyes destacadas en este caso se extiendan a problemas mucho más complejos de caminatas aleatorias.
Cada uno de los disparos al azar para elegir el movimiento constituye una prueba de Bernoulli con resultados igualmente probables : aquí la probabilidad de ascenso o descenso es 1/2.
La figura opuesta muestra una muestra de tres simulaciones numéricas independientes de paseos aleatorios para una partícula: hemos trazado las posiciones sucesivas x ( t ) de la partícula en los tiempos t = 1, 2, ..., a partir de la condición inicial x ( 0) = 0 .
Después de n pasos en total, el número de veces que hemos dibujado “colas” sigue la distribución binomial B ( n , 1/2) , por lo que la probabilidad es:
donde es el número de combinaciones de k elementos tomados de n .
Podemos determinar la posición después de n iteraciones, tomando el valor 0 para el inicio, sumando 1 por cada paso hacia adelante (cruz), restando 1 por cada paso hacia atrás (cara). Por lo que la posición está dada por: . En comparación con la ley binomial clásica, por lo tanto, es suficiente cambiar los resultados por n ⁄ 2 y multiplicar por 2, así:
Concretamente, si repetimos la experiencia con un gran número de participantes, y si los dejamos evolucionar durante un número suficientemente grande de pasos (del orden de n = 100 por ejemplo) esperamos que la nube de posiciones finales esté aproximadamente centrada en el paseo inicial. Esto puede hacerse cuantitativo: colocándonos en el régimen asintótico n >> 1 , demostramos usando la fórmula de Stirling que la ley binomial se comporta asintóticamente como una distribución gaussiana . En particular, se obtiene un orden de magnitud de la dispersión de la nube de participantes: por ejemplo, se espera que aproximadamente el 95% de los participantes hayan permanecido a 20 pasos o menos de la posición inicial (20 = 2 √ 100 ).
Ejemplos deLa galería a continuación contiene cuatro especímenes de caminatas isotrópicas al azar en la celosía ℤ después de 1000 pasos desde el origen. Las líneas de puntos indican respectivamente los valores máximo y mínimo de la posición alcanzada (después de 1000 pasos).
Según la fórmula anterior, la probabilidad de volver al origen después de 2 n pasos vale (por supuesto, es cero después de un número impar de pasos).
El equivalente obtenido por la fórmula de Stirling muestra que esta probabilidad tiende lentamente hacia 0, lo que significa intuitivamente que cuanto mayor sea el tiempo, menos probable es que estemos en el punto de partida. No obstante veremos que cualquier paseo vuelve al menos una vez al origen, sabiendo que la media de los tiempos de primer retorno al origen es infinita.
Probabilidad de paso al origenNos preguntamos cuál es la probabilidad de haber regresado al menos una vez al origen durante un viaje de longitud 2n ; Es notable que el evento opuesto también tiene una probabilidad y que, por lo tanto, tiende hacia 1 cuando n tiende hacia el infinito: una caminata aleatoria isotrópica sobre la línea casi con certeza regresa al menos una vez a su punto de partida (por lo tanto, de hecho y repite un número infinito de veces), y esto se aplica incluso a cualquier punto por el que pasa. Más adelante veremos que esto sigue siendo cierto en la dimensión 2, pero se vuelve falso en la dimensión superior.
Demostración de la fórmula anterior:
En aras de la simetría, el número de pasos aleatorios de longitud que no pasan es el doble del número de los que quedan .
Nuestro problema es contar los pasos que van de a en trazos y estar, aparte , estrictamente a la derecha de .
El primer segmento de un paso tan necesariamente va a , simplemente contar el número de caminos que van en en tiros sin pasar .
En general, el número de caminos que van en en trazos es (la ruta se determina completamente por el movimiento hacia la derecha (o movimiento a la izquierda)) para elegir los desplazamientos totales. Entonces, el número total de pasos que van de a vale
La parte difícil es determinar el número de pasos en con disparos que van a 0. Esto se hace usando el principio de reflexión (ver el artículo sobre el tema electoral ).
Para tal paso, podemos reemplazar biyectivamente la parte entre el inicio y el primer retorno por su simétrico con respecto a : este número es, por lo tanto, el mismo que el de los pasos que van de a en movimientos, es decir
Por tanto, vale la pena el número de pasos que van de a en longitud sin pasar por el eje . Tenga en cuenta que este resultado es equivalente al del teorema de la balota .
Deducimos el número de pasos evitando : ; dando suma telescópica , lo que había que demostrar.
Otra interpretación de los mismos resultados: el número de palabras binarias de longitud de (. Resp a la derecha) (. Resp La inversa), que todos los sub-canales, a partir de la izquierda presente estrictamente más de 1 que de 0 vale (no confundir con las palabras de Dyck ).
Un cálculo similar muestra que, en el caso impar, la probabilidad de volver al origen durante una caminata de longitud también es válida (ver la secuencia A063886 de la OEIS y la secuencia A307768 de la OEIS ).
Hora del primer regreso al origenUsando los resultados anteriores, la probabilidad se puede obtener como caminar de vuelta al origen por primera vez : . Deducimos que la expectativa del tiempo del primer regreso al origen es infinita desde .
Demostración de la fórmula anterior:
Un paso que vuelve al origen en ese momento pasa necesariamente por 1 o por -1 en el tiempo anterior y, siempre por simetría, llegan tantos pasos a 1 como a -1; por lo tanto, el número de pasos que regresan al origen por primera vez vale el doble del número de pasos de longitud que terminan en 1 y quedan> 0; podemos rehacer un razonamiento del tipo anterior o aplicar directamente la fórmula de la papeleta con , desde dónde , lo que quisiéramos.
Tenga en cuenta que es el doble del número de orden catalán .
Consideramos un paseo aleatorio en la red de planos ℤ 2 . Hay cuatro movimientos posibles aquí en cada sitio: adelante, atrás, derecha, izquierda. La figura de al lado muestra una muestra de tres simulaciones numéricas independientes de paseos aleatorios para una partícula: hemos trazado las tres trayectorias obtenidas.
Para caminatas largas, la distribución de la posición final del caminante se comporta asintóticamente como una distribución gaussiana . Esta convergencia se ilustra a continuación: trazamos las distribuciones de las probabilidades de presencia en la red después de 10 pasos, luego después de 60 pasos:
EspecímenesLa galería a continuación contiene cuatro especímenes de caminatas isotrópicas al azar en la celosía ℤ 2 después de 10,000 pasos desde el origen.
Consideramos un paseo aleatorio sobre la celosía cúbica ℤ 3 . Hay seis movimientos posibles aquí en cada sitio: adelante, atrás, derecha, izquierda, arriba, abajo.
La figura de al lado muestra una muestra de tres simulaciones numéricas independientes de caminatas aleatorias para una partícula: hemos graficado las tres trayectorias obtenidas.
EspecímenesLa galería a continuación contiene cuatro especímenes de caminatas isotrópicas al azar en la celosía ℤ 3 después de 10,000 pasos desde el origen.
Consideramos el paseo aleatorio en el plano ℝ 2 definido por el siguiente proceso:
Cada dirección de salto es completamente independiente de la dirección del salto anterior.
La figura de al lado muestra una muestra de tres simulaciones numéricas independientes de caminatas aleatorias para una partícula: hemos graficado las tres trayectorias obtenidas.
EspecímenesLa siguiente galería contiene cuatro muestras de pasos aleatorios isotrópicos en el plano ℝ 2 después de 10,000 pasos desde el origen.
Considere una caminata aleatoria isotrópica sobre el enrejado ℤ d con d dimensiones espaciales. Siempre podemos optar por tomar el punto de inicio de esta caminata como el origen O del sistema de coordenadas cartesianas. La cuestión de la recurrencia consiste entonces en preguntarnos si podemos encontrar al menos un instante t positivo finito para el que la partícula pasa por el origen O nuevamente .
Se dirá que la caminata aleatoria es recurrente si y solo si la probabilidad de que la partícula vuelva al origen O durante un cierto instante finito posterior t es igual a uno.
Esta propiedad de recurrencia depende en gran medida de la dimensión del espacio; de hecho podemos demostrar que (Pólya - 1921):
Algunas personas a veces bromean diciendo que este teorema es la base del proverbio: "Todos los caminos conducen a Roma" . El lector notará que si uno incluye caminos "cósmicos", entonces el proverbio está equivocado.
Probabilidad de retorno al origen en dimensión mayor o igual a tresDe hecho, sabemos cómo calcular la probabilidad de que el caminante, partiendo inicialmente del origen, regrese al origen, y esto para todas las dimensiones d > 2 . Esta probabilidad p ( d ) admite la siguiente expresión:
donde u ( d ) es una integral d- dimensional:
, que se puede expresar utilizando la función de Bessel del primer tipo : .El número representa el número promedio de retornos al origen antes de ir al infinito (ver ley geométrica ).
De hecho, el caso especial d = 3 ya lo habían obtenido previamente Watson, Mc Crea y Whipple y Domb. Glasser y Zucker solo obtuvieron una expresión analítica de la integral en 1977:
donde Γ es la función gamma . Las expresiones analíticas de u ( d ) no se conocen en la dimensión d mayor o igual a 4.
Obtenemos los siguientes valores numéricos:
Consideramos que un grupo asumido aquí es multiplicativo, sin que esto sea esencial para la definición de una caminata aleatoria en un grupo. Nos damos una serie de variables aleatorias independientes con la misma ley (ley llamada aquí, por ejemplo), variables aleatorias todas con valores en . También nos damos una variable aleatoria con valores en , de cualquier ley e independientes de . Luego posamos, para
Entonces, la secuencia es una cadena de Markov , y se denomina caminata aleatoria en G , de pasos . Esta calificación también se aplica a cualquier secuencia aleatoria de la misma distribución que X . Alternativamente, aceptamos como paseo aleatorio una secuencia definida por la relación de recurrencia:
Para distinguir los dos tipos de cadenas de Markov así definidas, a veces hablamos de paseo aleatorio por la derecha y paseo aleatorio por la izquierda . El término general de la matriz de transición de esta cadena de Markov se define, por , por
dependiendo de si el paseo aleatorio es a la derecha oa la izquierda. Podemos verificar fácilmente que
desde y son biyecciones de G en G . Por lo tanto, una medición uniforme sobre es una medición estacionaria .
Ejemplo:las caminatas aleatorias mencionadas anteriormente son caminatas aleatorias en los grupos aditivos ℤ d y ℝ 2 .
Ampliamente utilizado en el modelado de series de tiempo continuas, un paseo aleatorio se puede escribir:
Este es un caso especial de un proceso autorregresivo (es decir, "retrocedió sobre sí mismo") con ρ = 1 . El valor del parámetro ρ es muy importante porque cambia fundamentalmente la propiedad de la serie:
Recursivamente, un paseo aleatorio es simplemente la suma del ruido blanco. Lo escribimos: