Camino aleatorio

La caminata aleatoria o paseo aleatorio o camino aleatorio, abreviado en inglés como RW (Random Walks), es una formalización matemática de la trayectoria que resulta de hacer sucesivos pasos aleatorios. Por ejemplo, la ruta trazada por una molécula mientras viaja por un líquido o un gas, el camino que sigue un animal en su búsqueda de comida, el precio de una acción fluctuante y la situación financiera de un jugador pueden tratarse como una caminata aleatoria. El término caminata aleatoria fue introducido por Karl Pearson en 1905. Los resultados del estudio de las caminatas aleatorias han sido aplicados a muchos campos como la computación, la física, la química, la ecología, la biología, la psicología o la economía. En particular en este último campo la teoría del paseo aleatorio de Burton G. Malkiel en su obra Un paseo aleatorio por Wall Street se fundamenta en la hipótesis de los mercados eficientes, desarrollado en tres formas o hipótesis. En física el modelo ha servido, por ejemplo, para modelar el camino seguido por una molécula que viaja a través de un líquido o un gas (movimiento browniano). En ecología, se emplea para modelar los movimientos de un animal de pastoreo, etc. Varios tipos diferentes de caminos aleatorios son de interés. A menudo, los caminos aleatorios se suponen que son cadenas de Márkov o proceso de Márkov, pero otros caminos más complicados también son de interés. Algunos caminos aleatorios se dan en grafos finitos, otros en la recta, en el plano, o en dimensiones mayores, mientras algunos caminos aleatorios se dan en grupos.

En su forma más general, las caminatas aleatorias son cualquier proceso aleatorio donde la posición de una partícula en cierto instante depende solo de su posición en algún instante previo y alguna variable aleatoria que determina su subsecuente dirección y la longitud de paso. Los caminos aleatorios también varían con respecto al tiempo. Casos específicos o límites de estos incluyen la caminata de un borracho, el vuelo de Lévy y el movimiento browniano. Los paseos aleatorios están relacionados con los modelos de difusión y son un tema fundamental en la discusión de los procesos de Márkov. Varias propiedades de los paseos aleatorios incluyen distribuciones dispersas, tiempos de primer cruce y rutas de encuentro.

Definición 
Digamos que  define una trayectoria que empieza en la posición . Un paseo aleatorio se modela mediante la siguiente expresión: 

donde  es la variable aleatoria que describe la ley de probabilidad para tomar el siguiente paso y  es el intervalo de tiempo entre pasos subsecuentes. A medida que la longitud y dirección de un paso dado depende solo de la posición  y no de alguna posición previa, se dice que el paseo aleatorio posee la Propiedad de Márkov. Comúnmente la distribución del paso será independiente de la posición o del tiempo transcurrido, una propiedad llamada homogeneidad. De cualquier modo, la formulación es extremadamente general. Los paseos aleatorios pueden ocurrir en cualquier número de dimensiones, ser parciales o imparciales, discretos o continuos en el tiempo y/o espacio, y pueden violar la homogeneidad en algún número de formas.

Caminatas aleatorias en grafos 

En el estudio de la teoría general de las caminatas aleatorias, aparece con bastante frecuencia que el espacio donde se requiere realizar la caminata, puede ser modelado como cierto grafo. La situación usual es como sigue: Dado un grafo  y comenzando en uno de sus vértices, seleccionamos de alguna manera al azar uno de sus vecinos y nos movemos a este; entonces nosotros seleccionamos un vecino de este último vértice y nos movemos de nuevo, etc. La sucesión aleatoria de vértices obtenidos de esta forma es una caminata aleatoria sobre el grafo . La teoría relacionada con caminatas aleatorias se desarrolla en el marco general de la teoría de los procesos estocásticos, más exactamente con la relacionada con las cadenas de Márkov, y no solo eso; no hay mucha diferencia entre la teoría de las caminatas aleatorias en grafos y la teoría de las cadenas de Márkov finitas ya que cada cadena de Márkov de estas, puede ser vista como una caminata aleatoria sobre cierto grafo dirigido. De manera similar, las cadenas de Márkov reversibles pueden ser vistas como caminatas aleatorias en grafos no dirigidos, y las cadenas de Márkov simétricas, como caminatas aleatorias en grafos regulares.

Caminatas aleatorias en grafos surgen en muchos modelos en matemáticas y en física. De hecho, ésta es una de esas nociones que empiezan a aparecer en todas partes una vez se empieza a buscarlas. Por ejemplo, considere la disposición de una baraja de cartas, construya un grafo cuyos vértices sean todas las permutaciones de las cartas de la baraja de tal manera que dos permutaciones son adyacentes si y solo si una se obtiene a partir de la otra cambiando la posición de dos de las cartas. Barajar el mazo de cartas, corresponde a una caminata aleatoria en este grafo.

Recientemente caminatas aleatorias en grafos más generales, aunque finitos, han recibido mayor atención, y los aspectos estudiados son más cuantitativos: cuánto se debe caminar hasta llegar a la posición inicial, hasta llegar a un vértice dado o hasta pasar por todos los vértices del grafo. Las caminatas aleatorias también están relacionadas con otras ramas de la teoría de grafos; propiedades básicas de las caminatas aleatorias son determinadas por el espectro del grafo y también por la resistencia eléctrica de la red asociada de manera natural con este; es por esto que gran parte de la terminología correspondiente a tales caminatas se da en términos de la teoría de redes eléctricas lo cual resulta ser bastante útil dado que es posible extrapolar resultados de tal teoría a la de caminatas aleatorias en grafos y viceversa. Todas esas conexiones son fructíferas y dan tanto herramientas para el estudio como oportunidades para encontrar nuevas aplicaciones.

Definición 

Sea  un grafo dirigido con componentes conexas no triviales y  un conjunto de aristas tal que  con la condición adicional de que no tiene bucles, es decir . Sea  el conjunto de vecinos de  y  su grado.
Una función  simétrica en el sentido de  y donde  si  y  en caso contrario será llamada una conductancia. Tal como la terminología sugiere, se puede imaginar un electrón viajando por el grafo donde este junto a la función  modelarían una red eléctrica donde los vértices son sus nodos y las aristas tienen una conductancia eléctrica dada por . 
Sea  y si suponemos  para cada . La cadena de Márkov  con espacio de estados  y matriz de transición  dada por: 

 

Es llamada caminata aleatoria en . Esta cadena describe el movimiento aleatorio de una partícula a lo largo de los vértices de . Si la partícula está en un vértice  en un momento dado, entonces la partícula estará en un vecino de  en el siguiente momento, donde el vecino será escogido aleatoriamente de acuerdo a la conductancia. En el caso de una red eléctrica la partícula sería más precisamente un electrón. Note que al multiplicar la conductancia  por una constante positiva, no hay cambio en la caminata aleatoria asociada.

Caminata aleatoria simétrica 
Suponiendo que cada arista tiene la misma conductancia, esto es que cada vértice tiene grado finito. Entonces
 
 La matriz de transición está dada por:

Una cadena como la descrita anteriormente, en la cual si la partícula se encuentra en un vértice  tiene la misma probabilidad de moverse a cada vecino de , es llamada caminata aleatoria simétrica en .

Caminatas aleatorias en cuadrículas 

Las caminatas aleatorias sobre las cuadrículas  con  son particularmente interesantes. Considere primero la caminata aleatoria simple  sobre  con probabilidades de transición:

donde  es un parámetro. Note que la cadena así definida resulta irreducible.
Además la cadena es periódica de periodo 2 (ya que la cadena es irreducible es suficiente revisar si el periodo de 0 es 2): Como al empezar en el vértice 0 la cadena solo puede llegar de nuevo a 0 en una cantidad par de pasos y la cadena regresa a 0 en el tiempo  si y solo si hay  pasos a la derecha y n pasos a la izquierda entonces

 

De esto se obtiene usando la Fórmula de Stirling  y así  si  o lo que es lo mismo 0 es transitorio y al ser la cadena irreducible , resulta ser  transitoria. Por el contrario si  ,  y 0 es recurrente, así como la cadena . De esta manera, para el caso  en el que  es la caminata simétrica en , una partícula que parta de cualquier vértice en algún momento regresará a este.

Supongamos que trazamos una marca a cierta distancia del origen del paseo. ¿Cuántas veces cruzará el paseo aleatorio tal marca? La solución es el siguiente teorema (que extiende lo anterior): para cualquier paseo aleatorio unidimensional, cada punto del dominio de definición de una función será casi seguramente cruzado un número infinito de veces. (En dos dimensiones el resultado análogo dice que cualquier línea será cruzada un número infinito de veces). Este problema tiene diversos nombres: el problema de cruce de niveles, el problema de recurrencia o el problema de la ruina del apostador. El origen de este último nombre es el siguiente: si un jugador con una cantidad finita de dinero juega a un juego no sesgado contra una banca con infinito dinero, siempre termina perdiendo. La cantidad de dinero del jugador efectuará un paseo aleatorio según vaya ganando o perdiendo, y siempre, en algún momento, alcanzará el 0 y el juego terminará.

En el caso general considere  con . Para  sea  el vector unitario con un 1 en la posición  y 0 en todas las demás. La caminata aleatorio simple en  tiene probabilidades de transición:

 

donde ,  para cada  y . Claramente cuando  es grande es menos probable que partiendo de un vértice se pueda llegar nuevamente a él. Aun así, el comportamiento cuando  es similar al comportamiento cuando . La cadena es recurrente solo en el caso simétrico cuando . Cuando la dimensión de  es 3 o más, la cadena es transitoria para todos los valores de los parámetros , aún en el caso simétrico. Las pruebas son similares a la recién hecha, aunque los detalles son algo más complejos. Se puede ver que

 

donde  es una constante positiva que depende de la dimensión de . Así  y la cadena es recurrente si , mientras  y la cadena es transitoria si .

Como ilustración de lo anterior, imaginemos ahora un borracho caminando aleatoriamente por una ciudad cuyas calles forman una malla cuadrada. En cada cruce, el borracho elige una de las cuatro posibles direcciones que dan a ese cruce (incluyendo aquella por la que ha venido) con la misma probabilidad. Formalmente, esto sería un paseo aleatorio sobre . El problema de saber si el borracho llegará eventualmente desde el bar a su casa, caminando al azar, tiene una respuesta positiva. Pero si realizamos un problema similar con 3 o más dimensiones, no sucede así. En otros términos, un pájaro despistado podría vagar al azar por el cielo por siempre sin encontrar nunca su nido.

Otros resultados 

Regresamos al caso general de una caminata aleatoria  en un grafo . Se tienen claramente los siguientes hechos:
 Si  es conexo, entonces  es irreducible.
 Si  es conexo y finito, entonces  es recurrente.
 En particular, si  no es conexo, las componentes conexas de  que son finitas, resultan recurrentes.

Además suponiendo que  es una caminata aleatoria en un grafo finito conexo,  es o aperiódica o tiene periodo 2. Más aún,  tiene periodo 2 si y solo si bipartito. Esto es, el conjunto de vértices  puede ser particionado en conjuntos  y  tales que cada arista en  tiene un punto final en  y un punto final en .

Esencialmente todas las cadenas de Márkov reversibles pueden ser interpretadas como caminatas aleatorias en grafos. Este hecho es una de las razones por las cuales tales caminatas son de interés y se tienen los siguientes resultados:
 Una caminata aleatoria positiva recurrente  en un grafo  es siempre reversible.
 Recíprocamente, suponga que  es una cadena de Márkov reversible con matriz de transición  y función de densidad de probabilidad invariante . Suponga  para cada . Entonces  puede ser interpretada como una caminata aleatoria sobre el grafo  con  y  con función de conductancia dada por:

Aplicaciones 

Algunas aplicaciones del camino aleatorio son:
 En genética de poblaciones, el camino aleatorio describe las propiedades estadísticas de la deriva genética.
 En física, los caminos aleatorios son utilizados como modelos simplificados del movimiento browniano y difusión tales como el movimiento aleatorio de las moléculas en líquidos y gases. Véase, por ejemplo, la agregación limitada por difusión. Además, los caminos aleatorios y algunos de los caminos que interactúan consigo mismos juegan un papel en la teoría cuántica de campos.
 En biología matemática, los caminos aleatorios son utilizados para describir los movimientos individuales de los animales, para apoyar empíricamente los procesos de biodifusión, y en ocasiones para desarrollar la dinámica de poblaciones.
 En otros campos de las matemáticas, el camino aleatorio se utiliza para calcular las soluciones de la ecuación de Laplace, para estimar la media armónica, y para varias construcciones en el análisis y la combinatoria.
 En informática, los caminos aleatorios son utilizados para estimar el tamaño de la Web. En la World Wide Web conference-2006, Bar-Yossef et al. publicó sus descubrimientos y algoritmos para lo mismo.
 En el procesamiento de imágenes, los caminos aleatorios son utilizados para determinar las etiquetas (es decir, "objeto" o "fondo") para asociarlas con cada píxel. Este algoritmo se suele denominar como algoritmo de segmentación del camino aleatorio.

Relación con el movimiento browniano 
Cuando en un paseo aleatorio unidimensional (como el de ) se disminuye la longitud del paso a valores muy pequeños se obtiene un proceso de Wiener, un proceso estocástico que se comporta como un movimiento browniano.

Para ser más precisos, si la longitud del paso es ε, se necesita que el paseo tenga longitud L/ε² para que se aproxime a un paseo de Wiener de longitud L. Según el límite de la longitud del paso tiende a 0 (y en consecuencia se aumenta el número de pasos necesarios para completar el paseo) 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 del máximo, y si M es un espacio de medida sobre B con la topología normada, entonces se tiene convergencia en M. De manera similar, un proceso de Wiener en varias dimensiones puede expresarse como el límite de un paseo aleatorio en las mismas dimensiones. 

Un paseo aleatorio es un fractal discreto, pero la trayectoria de un proceso de Wiener es un fractal auténtico, relacionado con el anterior. Por ejemplo, consideremos un paseo aleatorio de dos dimensiones que toca un círculo de radio r veces la longitud del paso. El número medio de pasos que el paseo dará dentro del círculo es de r². Esto es la versión discreta del hecho de que los paseos de Wiener bidimensionales tienen una dimensión de Hausdorff fractal de 2

En dos dimensiones el número medio de pasos que un paseo aleatorio da en el entorno de su trayectoria es . Esto se corresponde con el hecho de que el entorno del proceso de Wiener es un fractal de dimensión 4/3, como predijo Mandelbrot mediante simulaciones, y pudo finalmente probarse en el año 2000.

Referencias

Bibliografía 

 Aldous, David; Fill, Jim, Reversible Markov Chains and Random Walks on Graphs, 

 Blanco, Liliana, Probabilidad, U. Nacional de Colombia. ISBN 978-958-719-576-7

 Doyle, Peter G.; Snell, J. Laurie (1984). Random Walks and Electric Networks. Carus Mathematical Monographs 22. Mathematical Association of America. . ISBN 978-0-88385-024-4. MR 920811

 Feller, William (1968), An Introduction to Probability Theory and its Applications (Volume 1). ISBN 0-471-25708-7

 Hughes, Barry D. (1996), Random Walks and Random Environments, Oxford University Press. ISBN 0-19-853789-1

 Norris, James (1998), Markov Chains, 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, March 1921.

 Révész, Pal (2013), Random Walk in Random and Non-random Environments (Third Edition), World Scientific Pub Co. ISBN 978-981-4447-50-8

 Rincón, Luis, Introducción a los procesos estocásticos .

 Weiss G. Aspects and Applications of the Random Walk, North-Holland, 1994.

 Woess, Wolfgang (2000), Random Walks on Infinite Graphs and Groups, Cambridge tracts in mathematics 138, Cambridge University Press. ISBN 0-521-55292-3

Véase también 
 Proceso de Bernoulli
 Cadena de Márkov
 Paseo aleatorio en los mercados financieros

Enlaces externos 

 Pólya's Random Walk Constants
 Random walk in Java Applet
 Quantum random walk

Procesos estocásticos
Conceptos de la mecánica estadística
Modelos estadísticos
Conectividad de grafos
Variantes de caminos aleatorios