Paseo 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.^[1]​ 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.^[2]​^[3]​^[4]​^[5]​^[6]​^[7]​^[8]​^[9]​ 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.

Digamos que ${displaystyle X(t),}$ define una trayectoria que empieza en la posición ${displaystyle X(0)=X_{0},}$. Un paseo aleatorio se modela mediante la siguiente expresión:

${displaystyle X(t+ au )=X(t)+Phi ( au )}$

donde ${displaystyle Phi }$ es la variable aleatoria que describe la ley de probabilidad para tomar el siguiente paso y ${displaystyle au }$ 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 ${displaystyle X(t)}$ 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.

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 ${displaystyle G}$ 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 ${displaystyle G}$. 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.^[10]​

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.

Sea ${displaystyle G=(V,E)}$ un grafo dirigido con componentes conexas no triviales y ${displaystyle Esubset V^{2}}$ un conjunto de aristas tal que ${displaystyle (x,y)in Eiff (y,x)in E}$ con la condición adicional de que no tiene bucles, es decir ${displaystyle (x,x) ot in E}$. Sea ${displaystyle N(x)={yin V:(x,y)in E}}$ el conjunto de vecinos de ${displaystyle xin V}$ y ${displaystyle d(x)=|N(x)|}$ su grado. Una función ${displaystyle c:V^{2}mapsto mathbb {R} }$ simétrica en el sentido de ${displaystyle c(x,y)=c(y,x)}$ y donde ${displaystyle c(x,y)>0}$ si ${displaystyle (x,y)in E}$ y ${displaystyle c(x,y)=0}$ 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 ${displaystyle c}$ modelarían una red eléctrica donde los vértices son sus nodos y las aristas tienen una conductancia eléctrica dada por ${displaystyle c}$. Sea ${displaystyle C(x)=sum _{yin V}c(x,y)}$ y si suponemos ${displaystyle c(x)<infty }$ para cada ${displaystyle xin V}$. La cadena de Márkov ${displaystyle X=(X_{n})_{nin mathbb {N} }}$ con espacio de estados ${displaystyle V}$ y matriz de transición ${displaystyle P}$ dada por:

Es llamada caminata aleatoria en ${displaystyle G}$. Esta cadena describe el movimiento aleatorio de una partícula a lo largo de los vértices de ${displaystyle G}$. Si la partícula está en un vértice ${displaystyle xin V}$ en un momento dado, entonces la partícula estará en un vecino de ${displaystyle x}$ 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 ${displaystyle c}$ por una constante positiva, no hay cambio en la caminata aleatoria asociada.

Suponiendo que cada arista tiene la misma conductancia, esto es que cada vértice tiene grado finito. Entonces

${displaystyle pi _{xy}={egin{cases}1/d(x),&{mbox{si }}yin N(x)\0,&{mbox{si }}y ot in N(x)end{cases}}}$

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

Las caminatas aleatorias sobre las cuadrículas ${displaystyle mathbb {Z} ^{k}}$ con ${displaystyle kin mathbb {N} ^{+}}$ son particularmente interesantes. Considere primero la caminata aleatoria simple ${displaystyle X=(X_{n})_{nin mathbb {N} }}$ sobre ${displaystyle mathbb {Z} }$ con probabilidades de transición:

${displaystyle pi _{xy}=P(X_{n+1}=y|X_{n}=x)={egin{cases}p,&{mbox{si }}y=x+1\1-p,&{mbox{si }}y=x-1\0,&{mbox{en otro caso}}\end{cases}}}$

donde ${displaystyle pin (0,1)}$ 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):^[11]​ 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 ${displaystyle 2n}$ si y solo si hay ${displaystyle n}$ pasos a la derecha y n pasos a la izquierda entonces

De esto se obtiene usando la Fórmula de Stirling ${displaystyle pi _{00}^{(2n)}approx {frac {1}{sqrt {pi n}}}(4p(1-p))^{n}}$ y así ${displaystyle pi _{00}^{*}=sum _{n=0}^{infty }pi _{00}^{(2n)}<infty }$ si ${displaystyle p eq 1/2}$ o lo que es lo mismo 0 es transitorio y al ser la cadena irreducible , resulta ser ${displaystyle X}$ transitoria. Por el contrario si ${displaystyle p=1/2}$ , ${displaystyle pi _{00}^{*}=sum _{n=0}^{infty }pi _{00}^{(2n)}=infty }$ y 0 es recurrente, así como la cadena ${displaystyle X}$.^[11]​ De esta manera, para el caso ${displaystyle p=1/2}$ en el que ${displaystyle X}$ es la caminata simétrica en ${displaystyle mathbb {Z} }$, 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 ${displaystyle mathbb {Z} ^{k}}$ con ${displaystyle kin mathbb {N} ^{+}}$. Para ${displaystyle iin {1,2,cdots ,k}}$ sea ${displaystyle e_{i}in mathbb {Z} ^{k}}$ el vector unitario con un 1 en la posición ${displaystyle i}$ y 0 en todas las demás. La caminata aleatorio simple en ${displaystyle mathbb {Z} ^{k}}$ tiene probabilidades de transición:

donde ${displaystyle p_{i}>0}$, ${displaystyle q_{i}>0}$ para cada ${displaystyle i}$ y ${displaystyle sum _{i=1}^{k}(p_{i}+q_{i})=1}$. Claramente cuando ${displaystyle k}$ es grande es menos probable que partiendo de un vértice se pueda llegar nuevamente a él. Aun así, el comportamiento cuando ${displaystyle k=2}$ es similar al comportamiento cuando ${displaystyle k=1}$. La cadena es recurrente solo en el caso simétrico cuando ${displaystyle p_{1}=q_{1}=p_{2}=q_{2}=1/4}$. Cuando la dimensión de ${displaystyle k}$ es 3 o más, la cadena es transitoria para todos los valores de los parámetros ${displaystyle p_{i},q_{i}}$, 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 ${displaystyle C_{k}}$ es una constante positiva que depende de la dimensión de ${displaystyle k}$. Así ${displaystyle pi _{00}^{*}=infty }$ y la cadena es recurrente si ${displaystyle kin {1,2}}$, mientras ${displaystyle pi _{00}^{*}<infty }$ y la cadena es transitoria si ${displaystyle kin {3,4,cdots }}$.

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 ${displaystyle mathbb {Z} ^{2}}$. 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.

Regresamos al caso general de una caminata aleatoria ${displaystyle X}$ en un grafo ${displaystyle G}$. Se tienen claramente los siguientes hechos:

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

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:

Algunas aplicaciones del camino aleatorio son:

Cuando en un paseo aleatorio unidimensional (como el de ${displaystyle mathbb {Z} }$) 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.^[12]​ 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 ${displaystyle r^{4/3}}$. 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.

---