Caminata aleatoria

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

formalización matemática de un camino que consiste en una sucesión de pasos aleatorios

Cinco pasos aleatorios de ocho pasos desde un punto central. Algunos caminos parecen más cortos que ocho pasos donde la ruta se ha duplicado en sí misma. (versión animada)

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

Un ejemplo elemental de un paseo aleatorio es el paseo aleatorio en la línea número entero $mathbb {Z}$ que comienza a 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 gas (ver movimiento marroniano), el camino de búsqueda de un animal de forraje, o el precio de un stock fluctuante y el estado financiero de un jugador. Los paseos aleatorios tienen aplicaciones de ingeniería y muchos campos científicos incluyendo ecología, psicología, informática, física, química, biología, economía y sociología. El término caminar al azar fue presentado por Karl Pearson en 1905.

Paseo aleatorio de celosía

Un popular modelo de paseo aleatorio es el de un paseo aleatorio en una celosa regular, donde a cada paso la ubicación salta a otro sitio de acuerdo con alguna distribución de probabilidad. En un sencillo paseo aleatorio, la ubicación sólo puede saltar a sitios vecinos de la celosía, formando un camino de celo. En un sencillo paseo simétrico aleatorio en una celo localmente finito, las probabilidades de la ubicación saltando a cada uno de sus vecinos inmediatos son las mismas. El ejemplo mejor estudiado es el paseo aleatorio en el d- lattiza integer dimensional (a veces llamada la rejilla hipercubica) $mathbb {Z} ^{d}$ .

Si el espacio de estado 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.

Paseo aleatorio unidimensional

Un ejemplo elemental de un paseo aleatorio es el paseo aleatorio en la línea número entero, $mathbb {Z}$ , que comienza a 0 y a cada paso se mueve +1 o −1 con igual probabilidad.

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

Todos los posibles resultados aleatorios después de 5 vueltas de una moneda justa

Camina aleatoriamente en dos dimensiones (versión animada)

Camina aleatoriamente en dos dimensiones con 25 mil pasos (versión animada)

Camina aleatoriamente en dos dimensiones con dos millones de pasos incluso más pequeños. Esta imagen se generó de tal manera que los puntos que son más frecuentemente atravesados son más oscuros. En el límite, para pasos muy pequeños, se obtiene movimiento marroniano.

Para definir este paseo formalmente, tome variables aleatorias independientes $Z_{1},Z_{2},dots$ , donde cada variable es 1 o −1, con una probabilidad del 50% para valor y conjunto $S_{0}=0$ y ${textstyle S_{n}=sum _{j=1}^{n}Z_{j}.}$ La serie ${displaystyle {S_{n}}}$ se llama sencillo paseo al azar $mathbb {Z}$ . Esta serie (la suma de la secuencia de −1s y 1s) da la distancia neta caminada, si cada parte de la caminata es de la longitud uno. La expectativa ${displaystyle E(S_{n})}$ de $S_{n}$ es cero. Es decir, la media de todas las monedas se acerca a cero a medida que aumenta el número de volteretas. Esto sigue por la propiedad de la aditividad finita de la expectativa:

{displaystyle E(S_{n})=sum _{j=1}^{n}E(Z_{j})=0.}

Un cálculo similar, utilizando la independencia de las variables aleatorias y el hecho de que $E(Z_{n}^{2})=1$ , muestra que:

<math alttext="{displaystyle E(S_{n}^{2})=sum _{i=1}^{n}E(Z_{i}^{2})+2sum _{1leq iE()Sn2)=.. i=1nE()Zi2)+2.. 1≤ ≤ i.j≤ ≤ nE()ZiZj)=n.{displaystyle E(S_{n}{2}=sum ¿Por qué? E (Z_{i})=n.}<img alt="{displaystyle E(S_{n}^{2})=sum _{i=1}^{n}E(Z_{i}^{2})+2sum _{1leq i

Esto sugiere que $E(|S_{n}|),!$ , la distancia de traducción esperada después n medidas, deben ser del orden ${sqrt {n}}$ . De hecho,

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

Para responder a la pregunta de cuántas veces un paseo al azar cruza una línea de límites si se permite seguir caminando para siempre, un simple paseo al azar $mathbb {Z}$ cruzará cada punto un número infinito de veces. Este resultado tiene muchos nombres: fenómeno de cruce de niveles, recurrencia o el La ruina del jugador. La razón del apellido es la siguiente: un jugador con una cantidad finita de dinero eventualmente perderá al jugar 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 se terminará.

Si a y b son números enteros positivos, luego el número esperado de pasos hasta que un simple paseo aleatorio de una dimensión que comienza en 0 primeros éxitos b o −a es ab. La probabilidad de que este paseo golpee b antes -a es $a/(a+b)$ , que puede derivarse del hecho de que simple caminata al azar es un martingale. Y estas expectativas y probabilidades de golpear pueden ser calculadas ${displaystyle O(a+b)}$ en la cadena general de Markov.

Algunos de los resultados mencionados anteriormente pueden derivarse de propiedades del triángulo de Pascal. El número de diferentes paseos de n pasos donde cada paso es +1 o −1 es 2ⁿ. Para el simple paseo aleatorio, cada uno de estos paseos es igualmente probable. Para S_n ser igual a un número k es necesario y suficiente que el número de +1 en la caminata supere los de −1 por k. Se sigue +1 debe aparecer (n+k)/2 veces entre n pasos de un paseo, por lo tanto el número de caminatas que satisfacen $S_{n}=k$ iguala el número de formas de elegir (n+k)/2 elementos de un n elemento set, denotado ${textstyle n choose (n+k)/2}$ . Para que esto tenga sentido, es necesario que n+k ser un número uniforme, lo que implica n y k son ambos o ambos raros. Por lo tanto, la probabilidad de que $S_{n}=k$ es igual a ${textstyle 2^{-n}{n choose (n+k)/2}}$ . Al representar las entradas del triángulo de Pascal en términos de factoriales y utilizando la fórmula de Stirling, se puede obtener buenas estimaciones para estas probabilidades para grandes valores de $n$ .

Si el espacio se limita a $mathbb {Z}$ + para la brevedad, el número de maneras en que un paseo aleatorio aterrizará en cualquier número dado con cinco vueltas se puede mostrar como {0,5,0,4,0,1}.

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

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

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

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

Como una cadena de Markov

Una dimensión caminar al azar también se puede ver como una cadena Markov cuyo espacio estatal es dado por los enteros $i=0,pm 1,pm 2,dots.$ Para algunos números p satisfacción $<math alttext="{displaystyle ,0<p0.p.1{displaystyle ,0 seleccione1} <img alt=",0<p$ , las probabilidades de transición (la probabilidad P_i,j de moverse del estado i al estado j) se dan por

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

Generalización heterogénea

La caminata aleatoria heterogénea dibuja en cada paso del tiempo un número aleatorio que determina las probabilidades de salto local y luego un número aleatorio que determina la dirección de salto real. La pregunta principal es la probabilidad de permanecer en cada uno de los sitios después de $t$ saltos, y en el límite de esta probabilidad cuando $t$ es muy grande.

Dimensiones más altas

Tres paseos aleatorios en tres dimensiones

En dimensiones superiores, el conjunto de puntos andados al azar tiene interesantes propiedades geométricas. De hecho, se obtiene un fractal discreto, es decir, un conjunto que exhibe auto-similaridad estocástica en grandes escalas. En pequeñas escalas, se puede observar la "adhesividad" resultante de la rejilla en la que se realiza el paseo. La trayectoria de un paseo aleatorio es la colección de puntos visitados, considerados como un conjunto con desprecio a cuando el paseo 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 (ambas son, en promedio, por orden de $sqrt{n}$ ).

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

Para responder a la pregunta de si la persona vuelve alguna vez al punto de partida original de la caminata, este es el equivalente bidimensional del problema del paso a nivel discutido anteriormente. En 1921, George Pólya demostró que la persona casi seguramente lo haría en una caminata aleatoria bidimensional, pero para 3 dimensiones o más, la probabilidad de regresar al origen disminuye a medida que aumenta el número de dimensiones. En 3 dimensiones, la probabilidad disminuye a aproximadamente el 34%. Se sabe que el matemático Shizuo Kakutani se refirió a este resultado con la siguiente cita: "Un hombre borracho encontrará el camino a casa, pero un pájaro borracho puede perderse para siempre".

Otra variación de esta pregunta que también hizo Pólya es: "si dos personas parten del mismo punto de partida, ¿se volverán a encontrar?" Se puede demostrar que la diferencia entre sus ubicaciones (dos paseos aleatorios independientes) también es un paseo aleatorio simple, por lo que es casi seguro que se encuentran de nuevo en un paseo bidimensional, pero para 3 dimensiones y más, la probabilidad disminuye con el número de dimensiones. Paul Erdős y Samuel James Taylor también demostraron en 1960 que para dimensiones menores o iguales a 4, dos caminatas aleatorias independientes que comienzan desde dos puntos dados tienen casi con certeza infinitas intersecciones, pero para dimensiones mayores a 5, casi con certeza se intersecan 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 aproximando 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 en sentido estricto se trata de una confusión de un modelo con el fenómeno que se está modelando).

Un proceso de Wiener es el límite de escala de la caminata aleatoria en la dimensión 1. Esto significa que si hay una caminata aleatoria con pasos muy pequeños, existe una aproximación a un proceso de Wiener (y, con menor precisión, al movimiento browniano). Para ser más precisos, si el tamaño del paso es ε, se necesita dar un paseo de longitud L/ε² para aproximar 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 la máxima topología, y si M es el espacio de medida sobre B con la topología normal, entonces 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.

Una caminata aleatoria es un fractal discreto (una función con dimensiones enteras; 1, 2,...), pero la trayectoria de un proceso de Wiener es un verdadero fractal y existe una conexión entre los dos. Por ejemplo, realice una caminata aleatoria hasta que llegue a un círculo de radio r veces la longitud del paso. El promedio de pasos que realiza es r². Este hecho es la versión discreta del hecho de que un paseo del proceso de Wiener es un fractal de la 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 corresponde al hecho de que el límite de la trayectoria de un proceso de Wiener es un fractal de dimensión 4/3, un hecho predicho por Mandelbrot usando simulaciones pero probado solo en 2000. por Lawler, Schramm y Werner.

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

La caminata aleatoria y el proceso de Wiener se pueden acoplar, es decir, se manifiestan en el mismo espacio de probabilidad de una manera dependiente que los obliga a estar bastante cerca. El acoplamiento de este tipo más simple es la incrustación de Skorokhod, pero existen acoplamientos más precisos, como el teorema de aproximación de Komlós-Major-Tusnády.

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

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

Donde t es el tiempo transcurrido desde el comienzo de la caminata al azar, $varepsilon$ es el tamaño de un paso de la caminata al azar, y $delta t$ es el tiempo transcurrido entre dos pasos sucesivos.

Esto corresponde a la función de Green de la ecuación de difusión que controla el proceso de Wiener, lo que sugiere que, después de 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 asintótico de Wiener hacia el cual converge el paseo aleatorio después de un gran número de pasos:

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

Las dos expresiones de la diferencia anterior corresponden a la distribución asociada al vector ${vec {R}}$ que vincula los dos extremos de la caminata al azar, en 3D. La diferencia asociada a cada componente $R_{x}$ , $R_{y}$ o $R_{z}$ es sólo un tercio de este valor (todavía en 3D).

Para 2D:

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

Para 1D:

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

Paseo aleatorio gaussiano

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

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

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

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

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

{displaystyle Z=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}}(mu _{X}+mu _{Y},sigma _{X}^{2}+sigma _{Y}^{2})}

En nuestro caso, $μ X = μ Y = 0$ y $σ 2 X = σ 2 Y = σ 2$ rendimiento

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

{displaystyle Zsim {mathcal {N}}(0,nsigma ^{2}).}

{displaystyle {sqrt {Var(S_{n})}}={sqrt {E[S_{n}^{2}]}}=sigma {sqrt {n}}.}

Pero para el paseo aleatorio de Gauss, esto es sólo la desviación estándar de la distribución de la distancia de traducción después n pasos. Por lo tanto, si μ es igual a cero, y puesto que la distancia de traducción media raíz cuadrado (RMS) es una desviación estándar, hay 68.27% probabilidad de que la distancia de traducción RMS después de n los pasos caerán entre ${displaystyle pm sigma {sqrt {n}}}$ . Asimismo, hay un 50% de probabilidad de que la distancia de traducción después n los pasos caerán entre ${displaystyle pm 0.6745sigma {sqrt {n}}}$ .

Número de sitios distintos

El número de sitios distintos visitados por un solo caminante aleatorio $S(t)$ ha sido estudiado extensamente para la rejilla cuadrada y cúbica y para fractales. Esta cantidad es útil para el análisis de problemas de captura y reacciones cinéticas. También está relacionado con la densidad vibracional de estados, procesos de reacciones de difusión y diseminación de poblaciones en ecología.

Tasa de información

La tasa de información de una caminata aleatoria gaussiana con respecto a la distancia de error al cuadrado, es decir, su función de distorsión de tasa cuadrática, viene dada paramétricamente por

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

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

{displaystyle S(varphi)=left(2sin(pi varphi /2)right)^{-2}}

{displaystyle {{Z_{n}}_{n=1}^{N}}}

{displaystyle NR(D_{theta })}

{displaystyle D_{theta }}

0}" xmlns="http://www.w3.org/1998/Math/MathML">ε ε ■0{displaystyle varepsilon }0" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e04ec3670b50384a3ce48aca42e7cc5131a06b12" style="vertical-align: -0.338ex; width:5.344ex; height:2.176ex;"/>

{displaystyle Nin mathbb {N} }

{displaystyle 2^{NR(D_{theta })}}

{displaystyle {{Z_{n}}_{n=1}^{N}}}

{displaystyle D_{theta }-varepsilon }

Aplicaciones

Antony Gormley Quantum Cloud escultura en Londres fue diseñada por un ordenador usando un algoritmo de caminar al azar

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

En la economía financiera, la hipótesis de caminar aleatorio se utiliza para modelar las acciones precios y otros factores. Estudios empíricos encontraron algunas desviaciones de este modelo teórico, especialmente en correlaciones a corto y largo plazo. Ver precios de acciones.
En la genética poblacional, caminar al azar describe las propiedades estadísticas de la deriva genética
En física, los paseos aleatorios se utilizan como modelos simplificados de movimiento y difusión físico Brownian, como el movimiento aleatorio de moléculas en líquidos y gases. Véase por ejemplo la agregación limitada a la difusión. También en la física, los paseos aleatorios y algunos de los paseos auto interactuando juegan un papel en la teoría del campo cuántico.
En la fabricación semiconductora, los paseos aleatorios se utilizan para analizar los efectos del tratamiento térmico en los nodos más pequeños. Se aplica para entender la difusión de dopants, defects, impurezas etc, durante pasos críticos de fabricación. También se utilizan tratamientos aleatorios para estudiar la difusión de reactantes, productos y plasma durante procesos de deposición de vapor químico. La difusión continua se ha utilizado para estudiar el flujo de gases, a escalas macroscópicas, en reactores CVD. Sin embargo, dimensiones más pequeñas y mayor complejidad nos ha obligado a tratarlas con paseo aleatorio. Esto permite un análisis preciso de los procesos estocásticos, a nivel molecular y menor, en la fabricación semiconductora.
En la ecología matemática, los paseos aleatorios se utilizan para describir movimientos individuales de animales, para apoyar empíricamente procesos de biodiffusión, y ocasionalmente para modelar dinámicas de población.
En la física polímero, caminar al azar describe una cadena ideal. Es el modelo más simple para estudiar polímeros.
En otros campos de las matemáticas, caminata aleatoria se utiliza 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 la informática, los paseos aleatorios se utilizan para estimar el tamaño de la Web.
En segmentación de imágenes, los paseos aleatorios se utilizan para determinar las etiquetas (es decir, "objeto" o "background") para asociarse con cada pixel. Este algoritmo se conoce típicamente como el algoritmo de segmentación del caminante aleatorio.

En investigación cerebral, los paseos aleatorios y los paseos aleatorios reforzados se utilizan para modelar cascadas de tiro de neurona 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 fijos en general también están bien descritos por un paseo aleatorio.
En psicología, los paseos aleatorios explican con precisión la relación entre el tiempo necesario para tomar una decisión y la probabilidad de que se tome una decisión determinada.
Los paseos aleatorios se pueden utilizar para probar desde un espacio estatal que es desconocido o muy grande, por ejemplo para elegir una página aleatoria fuera de Internet. En la informática, este método se conoce como Markov Chain Monte Carlo (MCMC).

En redes inalámbricas, un paseo aleatorio se utiliza para modelar el movimiento de nodos.
Las bacterias motiles se dedican a paseos aleatorios parciales.
En física, los paseos aleatorios subyacen al método de estimación de Fermi.
En la web, el sitio web de Twitter utiliza paseos aleatorios para hacer sugerencias de quién seguir
Dave Bayer y Persi Diaconis han demostrado que 7 riffles son suficientes para mezclar una cubierta de tarjetas (ver más detalles bajo shuffle). Este resultado se traduce en una declaración sobre la marcha aleatoria en el grupo simétrico que es lo que demuestran, con un uso crucial de la estructura del grupo a través del análisis Fourier.

Variantes

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

En gráficos

Un paseo aleatorio de longitud k en un gráfico posiblemente infinito G con una raíz 0 es un proceso estocástico con variables aleatorias $X_{1},X_{2},dotsX_{k}$ tales que $X_{1}=0$ y ${X_{i+1}}$ es un vértice elegido uniformemente al azar de los vecinos de $X_{i}$ . Entonces el número $p_{v,w,k}(G)$ es la probabilidad de que un paseo aleatorio de longitud k empezando v finales w. En particular, si G es un gráfico con raíz 0, $p_{0,0,2k}$ es la probabilidad de que $2k$ - paso aleatorio regresa a 0.

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 determinado cruce, elige entre los diversos caminos disponibles con la misma probabilidad. Así, si el cruce tiene siete salidas, la persona irá a cada una con una séptima probabilidad. Esta es una caminata aleatoria en un gráfico. ¿Llegará nuestra persona a su casa? Resulta que, en condiciones bastante suaves, la respuesta sigue siendo sí, pero según el gráfico, la respuesta a la pregunta variante '¿Se volverán a encontrar dos personas?' no puede ser que se encuentren infinitamente a menudo casi con seguridad.

Un ejemplo de un caso en el que la persona llegará a su casa casi con seguridad es cuando las longitudes de todos los bloques están entre a y b (donde a y b son dos números positivos finitos). Tenga en cuenta que no asumimos que el gráfico es plano, es decir, la ciudad puede contener túneles y puentes. Una forma de probar este resultado es utilizando la conexión a redes eléctricas. Tome un mapa de la ciudad y coloque una resistencia de un ohmio en cada bloque. Ahora mide la "resistencia entre un punto y el infinito". En otras palabras, elija algún número R y tome todos los puntos en la red eléctrica con una distancia mayor que 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 (una prueba elemental se puede encontrar en el libro de Doyle y Snell):

Teorema: un grafo es transitorio si y solo si la resistencia entre un punto y el infinito es finita. No importa qué punto se elija si la gráfica es conexa.

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 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.

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

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

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

Una buena referencia para caminar al azar sobre gráficos es el libro en línea de Aldous y Fill. Para grupos ver el libro de Woess. Si el núcleo de transición $p(x,y)$ es aleatorio (basado en un entorno $omega$ ) entonces el paseo al azar se llama "una caminata rara en el entorno al azar". Cuando la ley de la caminata al azar incluye la aleatoriedad $omega$ , la ley se llama la ley aniquilada; por otro lado, si $omega$ es visto como fijo, la ley se llama una ley ancha. Vea el libro de Hughes, el libro de Revesz, o las notas de conferencias de Zeitouni.

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

Paseos aleatorios interactivos

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

El paseo autoevitable.

El caminar autoevitable de la longitud n on $mathbb {Z} ^{d}$ es el azar n- paso que comienza en el origen, hace transiciones sólo entre sitios adyacentes en $mathbb {Z} ^{d}$ , nunca volver a visitar un sitio, y es elegido uniformemente entre todos estos caminos. En dos dimensiones, debido al auto-trapping, un típico paseo auto-evitado es muy corto, mientras que en dimensión superior crece más allá de todos los límites. Este modelo se ha utilizado a menudo en la física polímero (desde los años 60).

El paseo al azar de la izquierda.
El paseo al azar reforzado.
El proceso de exploración.
El paseo aleatorio multiagente.

Paseos aleatorios sesgados en gráficos

Paseo aleatorio de máxima entropía

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

Paseos aleatorios correlacionados

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

Más resultados...