Caminata aleatoria - Random walk

Cinco caminatas aleatorias de ocho pasos desde un punto central. Algunos caminos parecen tener menos de ocho pasos donde la ruta se ha duplicado sobre sí misma. ( versión animada )

En matemáticas , una caminata aleatoria es un objeto matemático , conocido como proceso estocástico o aleatorio , que describe una ruta que consiste en una sucesión de pasos aleatorios en algún espacio matemático como los números enteros .

Un ejemplo elemental de una caminata aleatoria es la caminata aleatoria en la recta numérica entera , que comienza en 0 y en cada paso se mueve +1 o -1 con la misma probabilidad . Otros ejemplos incluyen la ruta trazada por una molécula mientras viaja en un líquido o un gas (ver Movimiento browniano ), la ruta de búsqueda de un animal en busca de alimento , el precio de una acción fluctuante y el estado financiero de un jugador : todos pueden ser aproximados. por modelos de caminata aleatoria, aunque no sean realmente aleatorios en la realidad. ${\ Displaystyle \ mathbb {Z}}$

Como ilustran esos ejemplos, 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 . Los paseos aleatorios explican los comportamientos observados de muchos procesos en estos campos y, por lo tanto, sirven como modelo fundamental para la actividad estocástica registrada. Como una aplicación más matemática, el valor de $π$ se puede aproximar mediante el uso de una caminata aleatoria en un entorno de modelado basado en agentes . El término caminata aleatoria fue introducido por primera vez por Karl Pearson en 1905.

Son de interés varios tipos de caminatas aleatorias, que pueden diferir de varias maneras. El término en sí mismo se refiere con mayor frecuencia a una categoría especial de cadenas de Markov , pero muchos procesos dependientes del tiempo se denominan paseos aleatorios, con un modificador que indica sus propiedades específicas. Los paseos aleatorios (de Markov o no) también pueden tener lugar en una variedad de espacios: los comúnmente estudiados incluyen gráficos , otros en los números enteros o en la línea real, en el plano o en espacios vectoriales de dimensiones superiores, en superficies curvas o en Riemann de dimensiones superiores. múltiples , y también en grupos finitos, finitamente generados o Mentira . El parámetro de tiempo también se puede manipular. En el contexto más simple, la caminata es en tiempo discreto, es decir, una secuencia de variables aleatorias $(X t) = (X 1, X 2, ...)$ indexados por los números naturales. Sin embargo, también es posible definir paseos aleatorios que dan sus pasos en momentos aleatorios, y en ese caso, la posición $X t$ debe definirse para todos los tiempos $t \in [0, + \infty)$ . Los casos específicos o límites de caminatas aleatorias incluyen el vuelo de Lévy y los modelos de difusión como el movimiento browniano .

Los paseos aleatorios son un tema fundamental en las discusiones sobre los procesos de Markov. Su estudio matemático ha sido extenso. Se han introducido varias propiedades, incluidas las distribuciones de dispersión, los tiempos de primer paso o de acierto, las tasas de encuentro, la recurrencia o la fugacidad, para cuantificar su comportamiento.

Paseo aleatorio de celosía

Un modelo de caminata aleatoria popular es el de una caminata aleatoria en una celosía regular, donde en cada paso la ubicación salta a otro sitio de acuerdo con alguna distribución de probabilidad. En una simple caminata aleatoria , la ubicación solo puede saltar a los sitios vecinos de la celosía, formando un camino de celosía . En una caminata aleatoria simétrica simple sobre una celosía 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 d- dimensional (a veces llamada red hipercúbica) . ${\ Displaystyle \ mathbb {Z} ^ {d}}$

Si el espacio de estados está limitado a dimensiones finitas, el modelo de paseo aleatorio se llama paseo aleatorio simétrico bordeado simple 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 una caminata aleatoria es la caminata aleatoria en la recta numérica entera , que comienza en 0 y en cada paso se mueve +1 o -1 con la misma probabilidad. ${\ Displaystyle \ mathbb {Z}}$

Este paseo 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 hacia la derecha. Si cae en cruz, el marcador se mueve una unidad hacia 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, aterrizará 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 cola), 5 formas de aterrizar en −3 (volteando cuatro cruces y una cara), 1 forma de aterrizar en 5 (volteando cinco caras) y 1 forma de aterrizar en −5 (volteando cinco cruces). Consulte la figura siguiente para ver una ilustración de los posibles resultados de 5 giros.

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

Paseo aleatorio en dos dimensiones ( versión animada )

Caminata aleatoria en dos dimensiones con 25 mil pasos ( versión animada )

Caminata aleatoria en dos dimensiones con dos millones de pasos aún más pequeños. Esta imagen se generó de tal manera que los puntos que se recorren con mayor frecuencia sean más oscuros. En el límite, para pasos muy pequeños, se obtiene el movimiento browniano .

Para definir esta caminata formalmente, tome variables aleatorias independientes , donde cada variable es 1 o -1, con una probabilidad del 50% para cualquiera de los valores, y establezca y La serie se llama caminata aleatoria simple . Esta serie (la suma de la secuencia de −1s y 1s) da la distancia neta caminada, si cada parte de la caminata es de longitud uno. La expectativa de es cero. Es decir, la media de todos los lanzamientos de monedas se acerca a cero a medida que aumenta el número de lanzamientos. Esto sigue por la propiedad de aditividad finita de la expectativa: ${\ Displaystyle Z_ {1}, Z_ {2}, \ dots}$ ${\ Displaystyle S_ {0} = 0 \, \!}$ ${\ Displaystyle S_ {n} = \ sum _ {j = 1} ^ {n} Z_ {j}.}$ ${\ Displaystyle \ {S_ {n} \} \, \!}$ ${\ Displaystyle \ mathbb {Z}}$ ${\ Displaystyle E (S_ {n}) \, \!}$ ${\ Displaystyle S_ {n} \, \!}$

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

{\ 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 , la distancia de traslación esperada después de n pasos, debería ser del orden de . De hecho, ${\ Displaystyle E (| S_ {n} |) \, \!}$ ${\ Displaystyle {\ sqrt {n}}}$

{\ Displaystyle \ lim _ {n \ to \ infty} {\ frac {E (| S_ {n} |)} {\ sqrt {n}}} = {\ sqrt {\ frac {2} {\ pi}} }.}

Este resultado muestra que la difusión es ineficaz para la mezcla debido a la forma en que se comporta la raíz cuadrada para grandes . ${\ Displaystyle N}$

¿Cuántas veces una caminata aleatoria cruzará una línea fronteriza si se le permite continuar caminando para siempre? Un simple paseo al azar 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 limpio contra un banco con una cantidad infinita de dinero. El dinero del jugador realizará una caminata aleatoria, llegará a cero en algún momento y el juego habrá terminado. ${\ Displaystyle \ mathbb {Z}}$

Si a y b son números enteros positivos, entonces el número esperado de pasos hasta que una caminata aleatoria simple unidimensional que comienza en 0 primero llegue a bo - a es ab . La probabilidad de que esta caminata golpee b antes que - a es , lo que puede derivarse del hecho de que la caminata aleatoria simple es una martingala . ${\ Displaystyle a / (a + b)}$

Algunos de los resultados mencionados anteriormente se pueden derivar de las propiedades del triángulo de Pascal . El número de recorridos 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 a los de -1 en k . Se sigue que +1 debe aparecer ( n + k ) / 2 veces entre n pasos de una caminata, por lo tanto, el número de caminatas que satisfacen es igual al número de formas de elegir ( n + k ) / 2 elementos de un n conjunto de elementos, denotado . Para que esto tenga significado, es necesario que n + k sea un número par, lo que implica que n y k son ambos pares o ambos impares. Por lo tanto, la probabilidad que es igual a . Al representar las entradas del triángulo de Pascal en términos de factoriales y al utilizar la fórmula de Stirling , se pueden obtener buenas estimaciones de estas probabilidades para valores grandes de . ${\ Displaystyle S_ {n} = k}$ ${\ Displaystyle n \ elige (n + k) / 2}$ ${\ Displaystyle S_ {n} = k}$ ${\ Displaystyle 2 ^ {- n} {n \ Choose (n + k) / 2}}$ ${\ Displaystyle n}$

Si el espacio se limita a + por brevedad, el número de formas en que un paseo aleatorio aterrizará en cualquier número dado que tenga cinco giros se puede mostrar como {0,5,0,4,0,1}. ${\ Displaystyle \ mathbb {Z}}$

Esta relación con el triángulo de Pascal se demuestra para valores pequeños de n . En giros cero, la única posibilidad será permanecer en cero. Sin embargo, en un turno, hay una posibilidad de aterrizar en -1 o una posibilidad de aterrizar 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 aterrizar en -2, dos posibilidades de aterrizar en cero y una posibilidad de aterrizar en 2.

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

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

Como generalización directa, se pueden considerar recorridos aleatorios sobre celosías cristalinas (gráficas de cobertura abeliana de pliegues infinitos sobre gráficas finitas). En realidad, es posible establecer el teorema del límite central y el teorema de la gran desviación en este contexto.

Como cadena de Markov

Un paseo aleatorio unidimensional también se puede considerar como una cadena de Markov cuyo espacio de estados está dado por los números enteros Para algún número p satisfactorio , se dan las probabilidades de transición (la probabilidad P _{i, j} de pasar del estado i al estado j ) por ${\ Displaystyle i = 0, \ pm 1, \ pm 2, \ dots.}$ ${\ Displaystyle \, 0 <p <1}$

{\ Displaystyle \, P_ {i, i + 1} = p = 1-P_ {i, i-1}.}

Generalización heterogénea

Mayores dimensiones

Tres paseos aleatorios en tres dimensiones

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 una auto-semejanza estocástica a gran escala. En escalas pequeñas, se pueden observar "irregularidades" que resultan de la cuadrícula sobre la que se realiza la caminata. Los dos libros de Lawler a los que se hace referencia a continuación son una buena fuente sobre este tema. La trayectoria de una caminata aleatoria es la colección de puntos visitados, considerada como un conjunto sin tener en cuenta cuando la caminata llegó al punto. En una dimensión, la trayectoria es simplemente todos los puntos entre la altura mínima y la altura máxima alcanzada por la caminata (ambos son, en promedio, del orden de ). ${\ Displaystyle {\ sqrt {n}}}$

Para visualizar el caso bidimensional, uno puede imaginar a una persona caminando al azar por una ciudad. La ciudad es efectivamente infinita y está dispuesta en una cuadrícula de aceras. En cada intersección, la persona elige al azar una de las cuatro rutas posibles (incluida la que recorrió originalmente). Formalmente, este es un paseo aleatorio sobre el conjunto de todos los puntos del plano con coordenadas enteras .

¿Volverá alguna vez la persona 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 se reduce a aproximadamente el 34%. Se sabía que el matemático Shizuo Kakutani se refería a este resultado con la siguiente cita: "Un 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 salen del mismo punto de partida, ¿se volverán a encontrar alguna vez? Se puede demostrar que la diferencia entre sus ubicaciones (dos caminatas aleatorias independientes) también es una caminata aleatoria simple, por lo que es casi seguro que se reencuentren en una caminata bidimensional, pero para 3 dimensiones y 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 que 4, dos caminatas aleatorias independientes que comienzan desde dos puntos dados tienen casi con seguridad infinitas intersecciones, pero para dimensiones superiores a 5, es casi seguro que se cruzan solo con 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

Pasos simulados que se aproximan a un proceso de Wiener en dos dimensiones

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 esto es, estrictamente hablando, una confusión de un modelo con el fenómeno que se está modelando).

Un proceso de Wiener es el límite de escala del paseo aleatorio en la dimensión 1. Esto significa que si realiza un paseo aleatorio con pasos muy pequeños, obtendrá una aproximación a un proceso de Wiener (y, con menos precisión, al movimiento browniano). Para ser más precisos, si el tamaño de paso es ε, hay que tener un pie de longitud L / ε ² para aproximarse a una longitud 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 el máximo de topología, y si M es el espacio de medida sobre B con la topología de la norma, a continuación, la convergencia está en el espacio M . 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.

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 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 multiplicado por la longitud del paso. El número medio 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 ^4/3 . Esto se corresponde con el 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 probado solo en 2000 por Lawler , Schramm y Werner .

Un proceso de Wiener disfruta de muchas simetrías que la caminata aleatoria no tiene. Por ejemplo, una caminata del proceso de Wiener es invariante 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, por ejemplo, 17 grados). también). Esto significa que, en muchos casos, los problemas en una caminata aleatoria son más fáciles de resolver al traducirlos a un proceso de Wiener, resolver el problema allí y luego traducirlos. Por otro lado, algunos problemas son más fáciles de resolver con caminatas aleatorias 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 el incrustado de Skorokhod, pero existen acoplamientos más precisos, como el teorema de aproximación de Komlós-Major-Tusnády .

La convergencia de un paseo aleatorio 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 una gran cantidad 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, es el tamaño de un paso de la caminata aleatoria y es el tiempo transcurrido entre dos pasos sucesivos. ${\ Displaystyle \ varepsilon}$ ${\ Displaystyle \ delta t}$

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 una gran cantidad 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:

{\ 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 a considerar para el proceso de Wiener asintótico hacia el cual el camino aleatorio converge después de un gran número de pasos:

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

(válido solo en 3D).

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

Para 2D:

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

Para 1D:

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

Paseo aleatorio gaussiano

Una caminata aleatoria que tiene un tamaño de paso que varía según una distribución normal se utiliza como modelo para datos de series de tiempo 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 supuesto subyacente.

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

Si μ es distinto de cero, la caminata aleatoria variará alrededor de 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 de la distribución normal, n es el número de pasos , y σ es de la distribución normal acumulada inversa como se indica arriba.

Demostración: El paseo aleatorio gaussiano se puede considerar como la suma de una secuencia de variables aleatorias independientes e idénticamente distribuidas, X _i de la distribución normal acumulada inversa con media igual a cero y σ de la distribución normal acumulativa inversa original:

Z = ,

{\ Displaystyle \ sum _ {i = 0} ^ {n} {X_ {i}}}

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

{\ Displaystyle {\ mathcal {N}}}

(μ _X + μ _Y , σ ²_X + σ ²_Y ) (ver aquí) .

En nuestro caso, μ _X = μ _Y = 0 y σ ²_X = σ ²_Y = σ ² producen

{\ Displaystyle {\ mathcal {N}}}

(0, 2σ ² )

Por inducción, para n pasos tenemos

Z ~ (0, n σ ² ).

{\ Displaystyle {\ mathcal {N}}}

Para los 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 la raíz cuadrada media después de n pasos es

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

Pero para el paseo aleatorio gaussiano, esta 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 traslació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 traslación RMS después de n pasos caiga entre ± σ . Asimismo, existe un 50% de probabilidad de que la distancia de traslación después de n pasos caiga entre ± 0,6745σ . ${\ Displaystyle {\ sqrt {n}}}$ ${\ Displaystyle {\ sqrt {n}}}$

Difusión anómala

En sistemas desordenados, como medios porosos y fractales, puede que no sea proporcional a sino a . El exponente se llama exponente de difusión anómala y puede ser mayor o menor que 2. La difusión anómala también se puede expresar como σ _r² ~ Dt ^α donde α es el parámetro de anomalía. Algunas difusiones en un entorno aleatorio son incluso proporcionales a la potencia del logaritmo del tiempo, véase, por ejemplo, la caminata de Sinai o la difusión de Brox. ${\ Displaystyle \ sigma ^ {2}}$ ${\ Displaystyle t}$ ${\ Displaystyle t ^ {2 / d_ {w}}}$ ${\ Displaystyle d_ {w}}$

Número de sitios distintos

El número de sitios distintos visitados por un solo caminante aleatorio se ha estudiado extensamente para celosías 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. La generalización de este problema al número de sitios distintos visitados por caminantes aleatorios , se ha estudiado recientemente para celosías euclidianas d-dimensionales. El número de sitios distintos visitados por N caminantes no está simplemente relacionado con el número de sitios distintos visitados por cada caminante. ${\ Displaystyle S (t)}$ ${\ Displaystyle N}$ ${\ Displaystyle S_ {N} (t)}$

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) \} \, d \ varphi,}

{\ Displaystyle D _ {\ theta} = \ int _ {0} ^ {1} \ min \ {S (\ varphi), \ theta \} \, d \ varphi,}

donde . Por lo tanto, es imposible codificar usando un código binario de menos de bits y recuperarlo con un error cuadrático medio esperado menor que . Por otro lado, para cualquiera , existe un código binario suficientemente grande de no más de elementos distintos, de modo que el error cuadrático medio esperado en la recuperación de este código es como máximo . ${\ Displaystyle S (\ varphi) = \ left (2 \ sin (\ pi \ varphi / 2) \ right) ^ {- 2}}$ ${\ Displaystyle {\ {Z_ {n} \} _ {n = 1} ^ {N}}}$ ${\ Displaystyle NR (D _ {\ theta})}$ ${\ Displaystyle D _ {\ theta}}$ ${\ Displaystyle \ varepsilon> 0}$ ${\ Displaystyle N \ in \ mathbb {N}}$ ${\ Displaystyle 2 ^ {NR (D _ {\ theta})}}$ ${\ Displaystyle {\ {Z_ {n} \} _ {n = 1} ^ {N}}}$ ${\ Displaystyle D _ {\ theta} - \ varepsilon}$

Aplicaciones

Antony Gormley 's Nube Quantum escultura en Londres fue diseñado por un equipo que utiliza un algoritmo de recorrido aleatorio.

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

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. Consulte los precios de las acciones .
En genética de poblaciones , la caminata aleatoria describe las propiedades estadísticas de la deriva genética.
En física , los paseos aleatorios se utilizan como modelos simplificados del movimiento y la 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, las caminatas aleatorias y algunas de las caminatas que interactúan con uno mismo juegan un papel en la teoría cuántica de campos .
En ecología matemática , las caminatas aleatorias 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 , la caminata aleatoria 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 recorridos aleatorios para determinar las etiquetas (es decir, "objeto" o "fondo") que se asociarán con cada píxel. Este algoritmo se denomina típicamente algoritmo de segmentación de caminantes aleatorios .

En todos estos casos, la caminata aleatoria a menudo se sustituye por el movimiento browniano.

En la investigación del cerebro , las caminatas aleatorias y las caminatas aleatorias reforzadas se utilizan para modelar cascadas de activación 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 una caminata aleatoria.
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 paseos aleatorios se pueden utilizar para tomar muestras de un espacio estatal que es desconocido o muy grande, por ejemplo, para seleccionar una página aleatoria de Internet o, para investigar las condiciones de trabajo, un trabajador aleatorio en un país determinado.

Cuando este último enfoque se utiliza en informática , se conoce como cadena de Markov Monte Carlo o MCMC para abreviar. A menudo, el muestreo de algún espacio de estados complicado también permite obtener una estimación probabilística del tamaño del espacio. La estimación de la permanente de una gran matriz de ceros y unos fue el primer gran problema que se abordó con este enfoque.

Los paseos aleatorios también se han utilizado para muestrear gráficos masivos en línea, como los servicios de redes sociales .
En las redes inalámbricas , se utiliza una caminata aleatoria para modelar el movimiento de los nodos.
Las bacterias móviles se involucran en una caminata aleatoria sesgada .
Los paseos al azar se utilizan para modelar el juego .
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 hacer sugerencias sobre a quién seguir.
Dave Bayer y Persi Diaconis han demostrado que 7 barajas son suficientes para mezclar un mazo de cartas (ver más detalles en barajar ). Este resultado se traduce en una afirmació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 donde se permite que la estructura simple sea más generalizada. La estructura pura se puede caracterizar porque los pasos se definen mediante variables aleatorias independientes e idénticamente distribuidas .

En gráficos

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

Basándonos en 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 un cierto cruce, elige entre las diversas carreteras disponibles con la misma probabilidad. Por lo tanto, si el cruce tiene siete salidas, la persona irá a cada una con una probabilidad de un séptimo. Este es un paseo aleatorio 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?" Puede que no se encuentren infinitamente a menudo, casi con seguridad.

Un ejemplo de un caso en que la persona va a llegar a su casa es casi seguro que es cuando las longitudes de todos los bloques son entre una y b (donde un y b son dos números enteros positivos). 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 demostrar este resultado es mediante la conexión a redes eléctricas . Tome un mapa de la ciudad y coloque una resistencia de un ohmio en cada bloque. Ahora mida la "resistencia entre un punto y el infinito". En otras palabras, elija un número R y tome todos los puntos de la red eléctrica con una distancia mayor que R desde nuestro punto y conéctelos juntos. Esta es ahora una red eléctrica finita y podemos medir la resistencia desde nuestro punto hasta los puntos cableados. Lleva R al infinito. El límite se llama resistencia entre un punto y el infinito . Resulta que lo siguiente es cierto (se puede encontrar una prueba elemental en el libro de Doyle y Snell):

Teorema : un gráfico es transitorio si y solo si la resistencia entre un punto y el infinito es finita. No es importante qué punto se elige si el gráfico está conectado.

En otras palabras, en un sistema transitorio, solo se necesita 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 fugacidad y 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 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 atravesar un camino determinado en una dirección u otra tienen una conexión muy simple entre ellas (si la gráfica es regular , son iguales). Esta propiedad tiene importantes consecuencias.

A partir de la década de 1980, se han realizado muchas investigaciones para conectar las propiedades del gráfico con recorridos aleatorios. Además de la conexión a la red eléctrica descrita anteriormente, existen conexiones importantes con las desigualdades isoperimétricas , ver 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 de forma finita . En muchos casos, estos resultados discretos se transfieren o se derivan de variedades y grupos de Lie .

En el contexto de los gráficos aleatorios , en particular el del modelo Erdős-Rényi , se han obtenido resultados analíticos para algunas propiedades de los caminantes aleatorios. Estos incluyen la distribución del primer y último tiempo de golpe del andador, donde el primer tiempo de golpe se da cuando el caminante ingresa a un sitio previamente visitado 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 caminar aleatoriamente sobre gráficos es el libro en línea de Aldous y Fill . Para grupos, consulte el libro de Woess. Si el núcleo de transición es en sí mismo aleatorio (basado en un entorno ), entonces el paseo aleatorio se denomina "paseo aleatorio en un entorno aleatorio". Cuando la ley de la caminata aleatoria incluye la aleatoriedad de , la ley se llama ley recocida; por otro lado, si se ve como fija, la ley se llama ley apagada. Vea el libro de Hughes, el libro de Revesz o las notas de la conferencia de Zeitouni. ${\ Displaystyle p (x, y)}$ ${\ Displaystyle \ omega}$ ${\ Displaystyle \ omega}$ ${\ Displaystyle \ omega}$

Podemos pensar en elegir todos los bordes posibles con la misma probabilidad que maximizar la incertidumbre (entropía) localmente. También podríamos hacerlo globalmente: en la caminata aleatoria de entropía máxima (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. Esta caminata aleatoria tiene propiedades de localización mucho más fuertes.

Caminatas aleatorias que interactúan con uno mismo

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 de 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:

La caminata de auto-evitación .

La caminata autoevitante de longitud n on es la ruta aleatoria de n pasos que comienza en el origen, hace transiciones solo entre sitios adyacentes en , nunca vuelve a visitar un sitio, y se elige de manera uniforme entre todos esos caminos. En dos dimensiones, debido al auto-atrapamiento, una caminata típica de auto-evitación 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). ${\ Displaystyle \ mathbb {Z} ^ {d}}$ ${\ Displaystyle \ mathbb {Z} ^ {d}}$

El paseo aleatorio borrado de bucles .
El paseo aleatorio reforzado .
El proceso de exploración .
El paseo aleatorio de agentes múltiples .

Caminatas correlacionadas de largo alcance

Las series de tiempo correlacionadas de largo alcance se encuentran en muchos sistemas biológicos, climatológicos y económicos.

Registros de latidos
Secuencias de ADN no codificantes
Serie temporal de volatilidad de las acciones
Registros de temperatura en todo el mundo

Paseos aleatorios sesgados en gráficos

Paseo aleatorio de entropía máxima

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

Paseos aleatorios correlacionados

Caminatas al azar donde 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.

Ver también

Referencias

Bibliografía

Aldous, David ; Rellenar, James Allen (2002). Cadenas de Markov reversibles y paseos aleatorios en gráficos . Archivado desde el original el 27 de febrero de 2019.
Ben-Avraham D .; Havlin S. , Difusión y reacciones en fractales y sistemas desordenados , Cambridge University Press, 2000.
Doyle, Peter G .; Snell, J. Laurie (1984). Paseos aleatorios y redes eléctricas . Monografías matemáticas de Carus. 22 . Asociación Matemática de América . arXiv : math.PR/0001057 . ISBN 978-0-88385-024-4. Señor 0920811 .
Feller, William (1968), Introducción a la teoría de la probabilidad y sus aplicaciones (Volumen 1). ISBN 0-471-25708-7
Hughes, Barry D. (1996), Paseos aleatorios y entornos aleatorios , Oxford University Press. ISBN 0-19-853789-1
Norris, James (1998), Cadenas de Markov , Cambridge University Press. ISBN 0-521-63396-6
Pólya G. (1921), "Über eine Aufgabe der Wahrscheinlichkeitsrechnung betreffend die Irrfahrt im Strassennetz" , Mathematische Annalen , 84 (1-2): 149-160, marzo de 1921.
Révész, Pal (2013), Random Walk in Random and Non-random Environments (tercera edición) , World Scientific Pub Co. ISBN 978-981-4447-50-8
Sunada, Toshikazu (2012). Cristalografía topológica: con miras al análisis geométrico discreto . Encuestas y Tutorías en Ciencias Matemáticas Aplicadas. 6 . Saltador. ISBN 978-4-431-54177-6.
Weiss G. Aspectos y aplicaciones de la caminata aleatoria , Holanda Septentrional, 1994.
Woess, Wolfgang (2000), Random Walks on Infinite Graphs and Groups , Cambridge Tracts in Math 138, Cambridge University Press. ISBN 0-521-55292-3

enlaces externos

Constantes de caminata aleatoria de Pólya
Caminata aleatoria en el applet de Java
Paseo aleatorio cuántico
Estimador de paseo aleatorio gaussiano
Modelos de conductancia electrónica que utilizan entropía máxima Paseos aleatorios Proyecto de demostraciones de Wolfram

Languages

In other projects