thumb|right|400px|Ejemplo de ocho caminos aleatorios en una dimensión empezando en 0. La gráfica muestra la posición actual sobre una línea (eje vertical) versus los intervalos de tiempo (eje horizontal). thumb|right|300px|Un ejemplo animado de un movimiento browniano-como camino aleatorio en un toro 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.Pearson, K. (1905). The Problem of the Random Walk. Nature. 72, 294. 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.Van Kampen N. G., Stochastic Processes in Physics and Chemistry, revised and enlarged edition (North-Holland, Amsterdam) 1992.Redner S., A Guide to First-Passage Process (Cambridge University Press, Cambridge, UK) 2001.Goel N. W. and Richter-Dyn N., Stochastic Models in Biology (Academic Press, New York) 1974.Doi M. and Edwards S. F., The Theory of Polymer Dynamics (Clarendon Press, Oxford) 1986De Gennes P. G., Scaling Concepts in Polymer Physics (Cornell University Press, Ithaca and London) 1979.Risken H., The Fokker–Planck Equation (Springer, Berlin) 1984..Cox D. R., Renewal Theory (Methuen, London) 1962. 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.P. Diaconis, Group Representations in Probability and Statistics, Inst. of Math. Statistics, Hayward, Californis, 1988
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á.
right|thumb|350px|Paseo aleatorio en dos dimensiones.
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 .