stringtranslate.com

Paseo aleatorio

Cinco recorridos aleatorios de ocho pasos desde un punto central. Algunos caminos parecen más cortos que ocho pasos cuando la ruta se dobla sobre sí misma. ( versión animada )

En matemáticas , un paseo aleatorio , a veces conocido como el paseo del borracho , es un proceso estocástico 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 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 ), la ruta de búsqueda de un animal en busca de alimento , o el precio de una acción fluctuante y la situación financiera de un jugador . Los paseos aleatorios tienen aplicaciones en la ingeniería y en muchos campos científicos, incluyendo 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 paseo aleatorio fue introducido por primera vez por Karl Pearson en 1905. [1]

Se pueden obtener realizaciones de paseos aleatorios mediante simulación de Monte Carlo . [2]

Paseo aleatorio en red

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 un camino de red . En un paseo aleatorio simétrico simple en 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 paseo aleatorio en la red entera d -dimensional (a veces llamada red hipercúbica) . [3]

Si el espacio de estados está limitado a dimensiones finitas, el modelo de caminata aleatoria se denomina caminata aleatoria simétrica con borde 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. [4]

Paseo aleatorio unidimensional

Un ejemplo elemental de un paseo aleatorio es el paseo aleatorio en la recta de números enteros , , 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 de la línea numérica y se lanza una moneda. Si cae en cara, el marcador se mueve una unidad a la derecha. Si cae en 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 formas de caer en 1 (al sacar tres caras y dos cruces), 10 formas de caer en -1 (al sacar tres cruces y dos caras), 5 formas de caer en 3 (al sacar cuatro caras y una cruz), 5 formas de caer en -3 (al sacar cuatro cruces y una cara), 1 forma de caer en 5 (al sacar cinco caras) y 1 forma de caer en -5 (al sacar cinco cruces). Vea la figura a continuación para ver una ilustración de los posibles resultados de 5 lanzamientos.

Todos los resultados posibles de un paseo aleatorio después de cinco lanzamientos de una moneda justa
Paseo aleatorio en dos dimensiones (versión animada)
Paseo aleatorio en dos dimensiones con 25 mil pasos (versión animada)
Paseo aleatorio 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 se ven más oscuros. En el límite, para pasos muy pequeños, se obtiene un movimiento browniano .

Para definir formalmente este paseo, tome variables aleatorias independientes , donde cada variable es 1 o −1, con una probabilidad del 50% para cualquier valor, y establezca y La serie se llama paseo aleatorio simple en . Esta serie (la suma de la secuencia de −1 y 1) da la distancia neta caminada, si cada parte del paseo tiene una longitud de uno. La expectativa de es cero. Es decir, la media de todos los lanzamientos de moneda se acerca a cero a medida que aumenta el número de lanzamientos. Esto se deduce de la propiedad de aditividad finita de la expectativa:

Un cálculo similar, utilizando la independencia de las variables aleatorias y el hecho de que , muestra que:

Esto sugiere que la distancia de traslación esperada después de n pasos debería ser del orden de . De hecho, [5]


Para responder a la pregunta de cuántas veces cruzará un paseo aleatorio una línea divisoria si se le permite seguir caminando eternamente, un simple paseo aleatorio sobre cada punto cruzará cada punto un número infinito de veces. Este resultado tiene muchos nombres: fenómeno del paso de nivel , recurrencia o la ruina del jugador . La razón del último nombre es la siguiente: un jugador con una cantidad finita de dinero acabará perdiendo cuando juegue un juego justo contra un banco con una cantidad infinita de dinero. El dinero del jugador realizará un paseo aleatorio y llegará a cero en algún momento, y el juego habrá terminado.

Si a y b son números enteros positivos, entonces el número esperado de pasos hasta que un paseo aleatorio simple unidimensional que comienza en 0 llega primero a b o − a es ab . La probabilidad de que este paseo llegue a b antes que a − a es , que se puede derivar del hecho de que el paseo aleatorio simple es una martingala . Y estas expectativas y probabilidades de acierto se pueden calcular en la cadena de Markov general del paseo aleatorio unidimensional.

Algunos de los resultados mencionados anteriormente pueden derivarse de las propiedades del triángulo de Pascal . El número de diferentes paseos de n pasos donde cada paso es +1 o −1 es 2 n . 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 exceda a los de −1 en k . De ello se deduce que +1 debe aparecer ( n  +  k )/2 veces entre n pasos de un paseo, por lo tanto, el número de paseos que satisfacen es igual al número de formas de elegir ( n  +  k )/2 elementos de un conjunto de n elementos, [6] denotado . Para que esto tenga sentido, 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 de que sea igual a . Al representar las entradas del triángulo de Pascal en términos de factoriales y utilizar la fórmula de Stirling , se pueden obtener buenas estimaciones de estas probabilidades para valores grandes de .

Si el espacio se limita a + para abreviar, la cantidad de formas en que un paseo aleatorio 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 . En cero vueltas, la única posibilidad será permanecer en cero. Sin embargo, en una vuelta, hay una probabilidad de caer en −1 o una probabilidad de caer en 1. En dos vueltas, 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 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 los paseos aleatorios simples en . En particular, el 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 y utilizando la fórmula de Stirling se tiene

Arreglando la escala , para fijo, y usando la expansión cuando se desvanece, se deduce

Tomando el límite (y observando que corresponde al espaciado de la cuadrícula de escala) se encuentra la densidad gaussiana . En efecto, para una variable aleatoria absolutamente continua con densidad se cumple , con correspondiente a un espaciado infinitesimal.

Como generalización directa, se pueden considerar los recorridos aleatorios en redes cristalinas (grafos de recubrimiento abeliano de pliegue infinito sobre grafos finitos). En realidad, es posible establecer el teorema del límite central y el teorema de la gran desviación en este contexto. [7] [8]

Como una cadena de Markov

Un paseo aleatorio unidimensional también puede verse como una cadena de Markov cuyo espacio de estados está dado por los números enteros Para algún número p que satisface , las probabilidades de transición (la probabilidad P i,j de moverse del estado i al estado j ) están dadas por

Generalización heterogénea

El paseo aleatorio heterogéneo dibuja en cada paso de tiempo un número aleatorio que determina las probabilidades locales de salto y luego un número aleatorio que determina la dirección real del salto. La cuestión principal es la probabilidad de permanecer en cada uno de los diversos sitios después de los saltos, y en el límite de esta probabilidad cuando es muy grande.

Dimensiones superiores

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 autosimilitud estocástica en grandes escalas. En escalas pequeñas, se puede observar "irregularidad" resultante de la cuadrícula en 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 el momento en que el recorrido 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 el recorrido (ambos son, en promedio, del orden de ).

Para visualizar el caso bidimensional, podemos imaginar a una persona caminando al azar por una ciudad. La ciudad es efectivamente infinita y está organizada en una cuadrícula 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 por el conjunto de todos los puntos del plano con coordenadas enteras .

Para responder a la pregunta de si la persona regresará alguna vez al punto de partida original del paseo, este es el equivalente bidimensional del problema del paso a nivel discutido anteriormente. En 1921, George Pólya demostró que la persona casi seguramente regresaría al punto de partida en un paseo aleatorio bidimensional, pero para 3 dimensiones o más, la probabilidad de regresar al punto de origen disminuye a medida que aumenta el número de dimensiones. En 3 dimensiones, la probabilidad disminuye a aproximadamente el 34%. [9] El matemático Shizuo Kakutani era conocido por referirse a este resultado con la siguiente cita: "Un hombre borracho encontrará su camino a casa, pero un pájaro borracho puede perderse para siempre". [10]

La probabilidad de recurrencia es en general , que puede derivarse mediante funciones generadoras [11] o el proceso de Poisson. [12]

Otra variación de esta pregunta, que también fue formulada por Pólya, es: "si dos personas parten del mismo punto de partida, ¿volverán a encontrarse alguna vez?" [13] Se puede demostrar que la diferencia entre sus posiciones (dos recorridos aleatorios independientes) también es un recorrido aleatorio simple, por lo que es casi seguro que se volverán a encontrar en un recorrido bidimensional, pero para dimensiones tridimensionales y superiores 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 4, dos recorridos aleatorios independientes que parten de dos puntos dados tienen casi con seguridad infinitas intersecciones, pero para dimensiones superiores a 5, es casi seguro que se intersecan solo con una frecuencia finita. [14]

La función asintótica para un paseo aleatorio bidimensional a medida que aumenta el número de pasos se da mediante 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]

Relación con el proceso de Wiener

Pasos simulados que aproximan un proceso de Wiener en dos dimensiones

Un proceso de Wiener es un proceso estocástico con un comportamiento similar al del movimiento browniano , el fenómeno físico en el que una partícula diminuta se difunde en un fluido. (A veces, el proceso de Wiener se denomina "movimiento browniano", aunque, en sentido estricto, se trata de una confusión entre un modelo y el fenómeno que se modela).

Un proceso de Wiener es el límite de escala del paseo aleatorio en dimensión 1. Esto significa que si hay un paseo aleatorio con pasos muy pequeños, hay una aproximación a un proceso de Wiener (y, con menor precisión, a un movimiento browniano). Para ser más precisos, si el tamaño del paso es ε, uno necesita tomar un paseo de longitud L2 para aproximarse a 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), el paseo aleatorio 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 de norma, entonces la convergencia está en el espacio M . De manera similar, un proceso de Wiener en varias dimensiones es el límite de escala del paseo aleatorio en el mismo número de dimensiones.

Un paseo aleatorio es un fractal discreto (una función con dimensiones enteras; 1, 2, ...), pero una trayectoria de proceso de Wiener es un fractal verdadero, y existe una conexión entre los dos. Por ejemplo, tomemos un paseo aleatorio hasta que llegue a un círculo de radio r multiplicado por la longitud del paso. El número promedio de pasos que realiza es r 2 . [ cita requerida ] Este hecho es la versión discreta del hecho de que un paseo de proceso de Wiener es un fractal de dimensión  2 de Hausdorff . [ cita requerida ]

En dos dimensiones, el número promedio de puntos que un mismo paseo aleatorio tiene 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 disfruta de muchas simetrías que un paseo aleatorio no tiene. Por ejemplo, un paseo de proceso de Wiener es invariante a las rotaciones, pero el paseo aleatorio no lo es, ya que la cuadrícula subyacente no lo es (el paseo aleatorio es invariante a las rotaciones de 90 grados, pero los procesos de Wiener también lo son a las rotaciones de, por ejemplo, 17 grados). Esto significa que, en muchos casos, los problemas en un paseo aleatorio son más fáciles de resolver traduciéndolos a un proceso de Wiener, resolviendo el problema allí y luego traduciendo de nuevo. Por otro lado, algunos problemas son más fáciles de resolver con paseos aleatorios debido a su naturaleza discreta.

El proceso de caminata aleatoria y el proceso de Wiener pueden estar acoplados , 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 de este tipo 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 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 el paseo aleatorio, la posición del caminante se distribuye de acuerdo con una distribución normal de varianza total :

donde t es el tiempo transcurrido desde el inicio del paseo aleatorio, es el tamaño de un paso del paseo aleatorio y 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, que sugiere que, después de una gran cantidad de pasos, el camino 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:

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: (válido sólo en 3D).

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 sólo un tercio de este valor (aún en 3D).

Para 2D: [17]

Para 1D: [18]

Paseo aleatorio gaussiano

Un paseo aleatorio 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.

Aquí, el tamaño del paso es la distribución normal acumulativa inversa 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 μ no es cero, el recorrido aleatorio variará en torno a una tendencia lineal. Si v s es el valor inicial del recorrido aleatorio, 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 está dada por N (0, n σ 2 ), 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: El paseo aleatorio gaussiano puede considerarse 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 distribuidas normalmente, Z = X + Y , está dada por (ver aquí) .

En nuestro caso, μ X = μ Y = 0 y σ 2 X = σ 2 Y = σ 2 da Por inducción, para n pasos tenemos Para pasos distribuidos según cualquier distribución con media cero y una varianza finita (no necesariamente solo una distribución normal), la distancia de traslación cuadrática media después de n pasos es (ver la identidad de Bienaymé )

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 cuadrática media (RMS) es una desviación estándar, existe un 68,27 % de probabilidad de que la distancia de traslación RMS después de n pasos se encuentre entre . Del mismo modo, existe un 50 % de probabilidad de que la distancia de traslación después de n pasos se encuentre entre .

Número de sitios distintos

La cantidad de sitios distintos visitados por un único caminante aleatorio se ha estudiado ampliamente para redes cuadradas y cúbicas y para fractales. [19] [20] Esta cantidad 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]

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 , se da paramétricamente por [26] donde . Por lo tanto, es imposible codificar utilizando un código binario de menos de bits y recuperarlo con un error cuadrático medio esperado menor que . Por otro lado, para cualquier , existe un código binario suficientemente grande y de no más de elementos distintos tal que el error cuadrático medio esperado en la recuperación de este código es como máximo .

Aplicaciones

La escultura Nube Cuántica de Antony Gormley en Londres fue diseñada por una computadora utilizando un algoritmo de caminata aleatoria.

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, particularmente en física [27] [28] y química, [29] ciencia de los materiales , [30] [31] y biología. [32] [33] [34] Las siguientes son algunas aplicaciones específicas de los paseos aleatorios:

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 por los pasos que se definen mediante variables aleatorias independientes e idénticamente distribuidas . Los paseos aleatorios pueden tener lugar en una variedad de espacios, como grafos , los 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 toman sus pasos en tiempos aleatorios y, en ese caso, la posición X
a
debe definirse para todos los tiempos t ∈ [0, +∞) . Los casos específicos o límites de los paseos aleatorios incluyen los modelos de vuelo y difusión de Lévy, como el movimiento browniano .

En gráficos

Un recorrido aleatorio de longitud k sobre un grafo G posiblemente infinito con raíz 0 es un proceso estocástico con variables aleatorias tales que y es un vértice elegido de manera uniforme al azar entre los vecinos de . Entonces, el número es la probabilidad de que un recorrido aleatorio de longitud k que comience en v termine en w . En particular, si G es un grafo con raíz 0 , es la probabilidad de que un recorrido aleatorio de -pasos regrese 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 un determinado cruce, elige entre las diversas carreteras disponibles con la misma probabilidad. Por tanto, si el cruce tiene siete salidas, la persona irá a cada una de ellas con una probabilidad de un séptimo. Se trata de un paseo aleatorio en un gráfico. ¿Llegará nuestra persona a su casa? Resulta que, en condiciones más bien suaves, la respuesta sigue siendo sí [44], pero, dependiendo del gráfico, la respuesta a la pregunta variante "¿Se volverán a encontrar dos personas?" puede no ser que se encuentren infinitamente a menudo, casi con toda seguridad [45] .

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). Nótese que no asumimos que el gráfico sea plano , es decir, que la ciudad puede contener túneles y puentes. Una forma de demostrar este resultado es utilizando la conexión a las 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 en la red eléctrica con una distancia mayor que R desde nuestro punto y conéctelos. Esta es ahora una red eléctrica finita, y podemos medir la resistencia desde nuestro punto hasta los puntos cableados. Lleve 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 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 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 transitoriedad 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 grafo es un caso muy especial de una cadena de Markov . A diferencia de una cadena de Markov general, el paseo aleatorio en un grafo 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 el grafo 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 paseos aleatorios. Además de la conexión de la red eléctrica descrita anteriormente, existen conexiones importantes con las desigualdades isoperimétricas (ver más aquí) , las 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 finitamente generados . En muchos casos, estos resultados discretos se trasladan 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 Erdős–Rényi , se han obtenido resultados analíticos para algunas propiedades de los caminantes aleatorios. Estos incluyen la distribución de los tiempos de primer [46] y último golpe [47] del caminante, donde el tiempo de primer golpe está dado por la primera vez que el caminante pisa un sitio previamente visitado del grafo, y el tiempo de último golpe 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 el paseo aleatorio 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 es aleatorio en sí mismo (se basa en un entorno ), entonces el paseo aleatorio se denomina "paseo aleatorio en un entorno aleatorio". Cuando la ley del paseo aleatorio incluye la aleatoriedad de , la ley se denomina ley recocida; por otro lado, si se considera fija, la ley se denomina ley apagada. Consulte el libro de Hughes, el libro de Revesz o las notas de la conferencia de Zeitouni.

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

Paseos aleatorios que interactúan entre sí

Existen varios 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 el paseo aleatorio habitual; aun así, el comportamiento de cualquier modelo de un caminante aleatorio se puede obtener mediante computadoras. Algunos ejemplos incluyen:

El camino autoevitativo de longitud n en es el camino aleatorio de n pasos que comienza en el origen, hace transiciones solo entre sitios adyacentes en , nunca vuelve a visitar un sitio y se elige uniformemente entre todos esos caminos. En dos dimensiones, debido al autoatrapamiento, un camino autoevitativo típico es muy corto, [50] mientras que en una dimensión superior crece más allá de todos los límites. Este modelo se ha utilizado a menudo en física de polímeros (desde la década de 1960).

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

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

Véase también

Referencias

  1. ^ Pearson, Karl (1905). "El problema del paseo aleatorio". Nature . 72 (1865): 294. Bibcode :1905Natur..72..294P. doi :10.1038/072294b0. S2CID  4010776.
  2. ^ Teoría y aplicaciones de simulaciones de Monte Carlo. (2013). Croacia: IntechOpen. Página 229, https://books.google.com/books?id=3HWfDwAAQBAJ&pg=PA229
  3. ^ Pal, Révész (1990) Paseo aleatorio en entornos aleatorios y no aleatorios , World Scientific
  4. ^ Kohls, Moritz; Hernandez, Tanja (2016). "Cobertura esperada del algoritmo de movilidad de paseo aleatorio". arXiv : 1611.02861 [stat.AP].
  5. ^ "Random Walk-1-Dimensional – de Wolfram MathWorld". Mathworld.wolfram.com. 26 de abril de 2000. Consultado el 2 de noviembre de 2016 .
  6. ^ Edward A. Codling et al., Modelos de paseo aleatorio en biología, Journal of the Royal Society Interface, 2008
  7. ^ Kotani, M.; Sunada, T. (2003). Geometría espectral de redes cristalinas . Matemáticas contemporáneas. Vol. 338. págs. 271–305. doi : 10.1090/conm/338/06077 . ISBN. 978-0-8218-3383-4.
  8. ^ Kotani, M.; Sunada, T. (2006). "Gran desviación y el cono tangente en el infinito de una red cristalina". Math. Z. 254 ( 4): 837–870. doi :10.1007/s00209-006-0951-9. S2CID  122531716.
  9. ^ "Constantes de caminata aleatoria de Pólya". Mathworld.wolfram.com . Consultado el 2 de noviembre de 2016 .
  10. ^ Durrett, Rick (2010). Probabilidad: teoría y ejemplos . Cambridge University Press. pp. 191. ISBN 978-1-139-49113-6.
  11. ^ Novak, Jonathan (2014). "Teorema del paseo aleatorio de Pólya". The American Mathematical Monthly . 121 (8): 711–716. arXiv : 1301.3916 . doi :10.4169/amer.math.monthly.121.08.711. ISSN  0002-9890. JSTOR  10.4169/amer.math.monthly.121.08.711.
  12. ^ Lange, Kenneth (2015). "Revisión del teorema del paseo aleatorio de Polya". The American Mathematical Monthly . 122 (10): 1005–1007. doi :10.4169/amer.math.monthly.122.10.1005. ISSN  0002-9890. JSTOR  10.4169/amer.math.monthly.122.10.1005.
  13. ^ Pólya, George (1984). Probabilidad; Combinatoria; Enseñanza y aprendizaje de las matemáticas . Rota, Gian-Carlo, 1932-1999., Reynolds, MC, Shortt, Rae Michael. Cambridge, Mass.: MIT Press. págs. 582–585. ISBN. 0-262-16097-8.OCLC 10208449  .
  14. ^ Erdős, P.; Taylor, SJ (1960). "Algunas propiedades de intersección de caminos aleatorios". Acta Mathematica Academiae Scientiarum Hungaricae . 11 (3–4): 231–248. CiteSeerX 10.1.1.210.6357 . doi :10.1007/BF02020942. ISSN  0001-5954. S2CID  14143214. 
  15. ^ https://ocw.mit.edu/courses/18-366-random-walks-and-diffusion-fall-2006/aef0a2690183294e59ea8cb29f8dd448_lec01.pdf [ URL desnuda PDF ]
  16. ^ MacKenzie, D. (2000). "MATEMÁTICAS: tomando la medida de la danza más salvaje de la Tierra". Science . 290 (5498): 1883–4. doi :10.1126/science.290.5498.1883. PMID  17742050. S2CID  12829171. (Fe de erratas:  doi :10.1126/science.291.5504.597)
  17. ^ Capítulo 2 DIFUSIÓN. dartmouth.edu.
  18. ^ Ecuación de difusión para el paseo aleatorio Archivado el 21 de abril de 2015 en Wayback Machine . physics.uakron.edu.
  19. ^ Weiss, George H.; Rubin, Robert J. (1982). "Paseos aleatorios: teoría y aplicaciones seleccionadas". Avances en física química . Vol. 52. págs. 363–505. doi :10.1002/9780470142769.ch5. ISBN. 978-0-470-14276-9.
  20. ^ Blumen, A.; Klafter, J.; Zumofen, G. (1986). "Modelos para la dinámica de la reacción en vidrios". Espectroscopia óptica de vidrios . Física y química de materiales con estructuras de baja dimensión. Vol. 1. págs. 199–265. Código Bibliográfico :1986PCMLD...1..199B. doi :10.1007/978-94-009-4650-7_5. ISBN: 978-94-010-8566-3.
  21. ^ Alexander, S.; Orbach, R. (1982). "Densidad de estados en fractales: "fractones"" (PDF) . Journal de Physique Lettres . 43 (17): 625–631. doi :10.1051/jphyslet:019820043017062500. S2CID  67757791.
  22. ^ Rammal, R.; Toulouse, G. (1983). "Paseos aleatorios sobre estructuras fractales y cúmulos de percolación". Journal de Physique Lettres . 44 (1): 13–22. doi :10.1051/jphyslet:0198300440101300.
  23. ^ Smoluchowski, MV (1917). "Versuch einer mathematischen Theorie der Koagulationskinetik kolloider Lösungen". Z. Phys. Química. (29): 129-168., Rice, SA (1 de marzo de 1985). Reacciones limitadas por difusión. Cinética química integral. Vol. 25. Elsevier. ISBN 978-0-444-42354-2. Recuperado el 13 de agosto de 2013 .
  24. ^ Skellam, JG (1951). "Dispersión aleatoria en poblaciones teóricas". Biometrika . 38 (1/2): 196–218. doi :10.2307/2332328. JSTOR  2332328. PMID  14848123.
  25. ^ Skellam, JG (1952). "Estudios en ecología estadística: I. Patrón espacial". Biometrika . 39 (3/4): 346–362. doi :10.2307/2334030. JSTOR  2334030.
  26. ^ Berger, T. (1970). "Tasas de información de los procesos de Wiener". IEEE Transactions on Information Theory . 16 (2): 134–139. doi :10.1109/TIT.1970.1054423.
  27. ^ Risken H. (1984) La ecuación de Fokker-Planck . Springer, Berlín.
  28. ^ De Gennes PG (1979) Conceptos de escalamiento en física de polímeros . Cornell University Press, Ithaca y Londres.
  29. ^ Van Kampen NG (1992) Procesos estocásticos en física y química , edición revisada y ampliada. Holanda Septentrional, Ámsterdam.
  30. ^ Weiss, George H. (1994). Aspectos y aplicaciones del recorrido aleatorio . Materiales y procesos aleatorios. North-Holland Publishing Co., Ámsterdam. ISBN 978-0-444-81606-1.Señor 1280031  .
  31. ^ Doi M. y Edwards SF (1986) La teoría de la dinámica de polímeros . Clarendon Press, Oxford
  32. ^ Goel NW y Richter-Dyn N. (1974) Modelos estocásticos en biología . Academic Press, Nueva York.
  33. ^ Redner S. (2001) Una guía para el proceso de primer paso . Cambridge University Press, Cambridge, Reino Unido.
  34. ^ Cox DR (1962) Teoría de la renovación . Methuen, Londres.
  35. ^ David A. Kodde y Hein Schreuder (1984), Pronóstico de ingresos y beneficios corporativos: modelos de series temporales frente a gestión y analistas, Journal of Business Finance and Accounting, vol. 11, n.º 3, otoño de 1984
  36. ^ Jones, RAL (2004). Materia condensada blanda (edición reimpresa). Oxford [ua]: Oxford Univ. Pr. pp. 77–78. ISBN 978-0-19-850589-1.
  37. ^ Bar-Yossef, Ziv; Gurevich, Maxim (2008). "Muestreo aleatorio del índice de un motor de búsqueda". Revista de la ACM . 55 (5). Association for Computing Machinery (ACM): 1–74. doi :10.1145/1411509.1411514. ISSN  0004-5411.
  38. ^ Grady, L (2006). "Random walks for image segmentation" (PDF) . IEEE Transactions on Pattern Analysis and Machine Intelligence . 28 (11): 1768–83. CiteSeerX 10.1.1.375.3389 . doi :10.1109/TPAMI.2006.233. PMID  17063682. S2CID  489789. Archivado desde el original (PDF) el 5 de julio de 2017 . Consultado el 2 de noviembre de 2016 . 
  39. ^ Rucci, M; Victor, JD (2015). "El ojo inestable: una etapa de procesamiento de información, no un error". Tendencias en neurociencias . 38 (4): 195–206. doi :10.1016/j.tins.2015.01.005. PMC 4385455 . PMID  25698649. 
  40. ^ Engbert, R.; Mergenthaler, K.; Sinn, P.; Pikovsky, A. (2011). "Un modelo integrado de movimientos oculares de fijación y microsaccades". Actas de la Academia Nacional de Ciencias . 108 (39): E765-70. Bibcode :2011PNAS..108E.765E. doi : 10.1073/pnas.1102730108 . PMC 3182695 . PMID  21873243. 
  41. ^ Nosofsky, RM; Palmeri, TJ (1997). "Un modelo de paseo aleatorio basado en ejemplos de clasificación rápida" (PDF) . Psychological Review . 104 (2): 266–300. doi :10.1037/0033-295x.104.2.266. PMID  9127583. Archivado desde el original (PDF) el 10 de diciembre de 2004.
  42. ^ Codling, E. A; Plank, M. J; Benhamou, S. (6 de agosto de 2008). "Modelos de paseo aleatorio en biología". Journal of the Royal Society Interface . 5 (25): 813–834. doi :10.1098/rsif.2008.0014. PMC 2504494 . PMID  18426776. 
  43. ^ Gupta, Pankaj et al. WTF: El sistema de a quién seguir en Twitter, Actas de la 22.ª conferencia internacional sobre la World Wide Web
  44. ^ Es interesante observar que en un gráfico general el encuentro de dos caminantes aleatorios independientes no siempre se reduce al problema de un único paseo aleatorio que regresa a su punto de partida.
  45. ^ Krishnapur, Manjunath; Peres, Yuval (2004). "Gráficos recurrentes donde dos recorridos aleatorios independientes colisionan con una frecuencia finita". Comunicaciones electrónicas en probabilidad . 9 : 72–81. arXiv : math/0406487 . Bibcode :2004math......6487K. doi :10.1214/ECP.v9-1111. ISSN  1083-589X. S2CID  16584737.
  46. ^ Tishby, Ido; Biham, Ofer; Katzav, Eytan (2017). "La distribución de los tiempos de primer impacto de los paseos aleatorios en redes Erdős–Rényi". Journal of Physics A: Mathematical and Theoretical . 50 (11): 115001. arXiv : 1606.01560 . Código Bibliográfico :2017JPhA...50k5001T. doi :10.1088/1751-8121/aa5af3. S2CID  118850609.
  47. ^ Tishby, Ido; Biham, Ofer; Katzav, Eytan (2016). "La distribución de las longitudes de caminos de los paseos autoevitativos en redes Erdős–Rényi". Journal of Physics A: Mathematical and Theoretical . 49 (28): 285002. arXiv : 1603.06613 . Código Bibliográfico :2016JPhA...49B5002T. doi :10.1088/1751-8113/49/28/285002. S2CID  119182848.
  48. ^ Burda, Z.; Duda, J.; Luck, JM; Waclaw, B. (2009). "Localización del paseo aleatorio de máxima entropía". Physical Review Letters . 102 (16): 160602. arXiv : 0810.4113 . Código Bibliográfico :2009PhRvL.102p0602B. doi :10.1103/PhysRevLett.102.160602. PMID  19518691. S2CID  32134048.
  49. ^ Madras, Neal y Slade, Gordon (1996) El paseo que evita uno mismo , Birkhäuser Boston. ISBN 0-8176-3891-1
  50. ^ Hemmer, S.; Hemmer, PC (1984). "Un paseo aleatorio autoevitativo promedio en la red cuadrada dura 71 pasos". J. Chem. Phys . 81 (1): 584–585. Bibcode :1984JChPh..81..584H. doi : 10.1063/1.447349 .
  51. ^ Lawler, Gregory (1996). Intersección de paseos aleatorios , Birkhäuser Boston. ISBN 0-8176-3892-X
  52. ^ Lawler, Gregory Procesos conformemente invariantes en el plano , libro.ps.
  53. ^ Pemantle, Robin (2007). "Un estudio de procesos aleatorios con refuerzo" (PDF) . Encuestas de probabilidad . 4 : 1–79. arXiv : math/0610076 . doi :10.1214/07-PS094. S2CID  11964062.
  54. ^ Alamgir, M. y von Luxburg, U. (2010). "Recorridos aleatorios de múltiples agentes para agrupamiento local en grafos" Archivado el 15 de abril de 2012 en Wayback Machine , IEEE 10th International Conference on Data Mining (ICDM) , pp. 18–27.
  55. ^ Bovet, Pierre; Benhamou, Simon (1988). "Análisis espacial de los movimientos de los animales utilizando un modelo de caminata aleatoria correlacionada". Revista de biología teórica . 131 (4): 419–433. Código Bibliográfico :1988JThBi.131..419B. doi :10.1016/S0022-5193(88)80038-9.
  56. ^ Kareiva, PM; Shigesada, N. (1983). "Análisis del movimiento de los insectos como un paseo aleatorio correlacionado". Oecologia . 56 (2–3): 234–238. Bibcode :1983Oecol..56..234K. doi :10.1007/BF00379695. PMID  28310199. S2CID  20329045.

Bibliografía

Enlaces externos