Matemáticas - Teoría de grafos

 Camino a una secuencia de vértices dentro de un grafotal que exista una arista entre cada vértice y el siguiente. Se dice que dos vértices están conectados si existe un camino que vaya de uno a otro, de lo contrario estarán desconectados. Dos vértices pueden estar conectados por varios caminos. El número de aristas dentro de un camino es su longitud. Así, los vértices adyacentes están conectados por un camino de longitud 1, y los segundos vecinos por un camino de longitud 2.

Si un camino empieza y termina en el mismo vértice se le llama ciclo.

Grafo camino Pn o Pn
P 6 : Grafo camino de orden 6
Vértices	n
Aristas	n - 1
Radio	⌊ n / 2 ⌋
Diámetro	n - 1
Automorfismos	2
Número cromático	2
Índice cromático	2
Propiedades	árbol grafo bipartito distancia unitaria

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, laquí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árkovo 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.

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

Definición

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+\tau )=X(t)+\Phi (\tau )}$

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

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 ${\displaystyle G}$ y comenzando en uno de sus vértices, seleccionamos de alguna manera al azar uno de sus vecinos y nos movemos a éste; entonces nosotros seleccionamos un vecino de éste ú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.¹⁰

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 éste; 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 ${\displaystyle G=(V,E)}$ un grafo dirigido con componentes conexas no triviales y ${\displaystyle E\subset V^{2}}$ un conjunto de aristas tal que ${\displaystyle (x,y)\in E\iff (y,x)\in E}$ con la condición adicional de que no tiene bucles, es decir ${\displaystyle (x,x)\not \in E}$. Sea ${\displaystyle N(x)=\{y\in V:(x,y)\in E\}}$ el conjunto de vecinos de ${\displaystyle x\in 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 éste junto a la función ${\displaystyle c}$ modelarían una red eléctrica donde los vértices son susnodos y las aristas tienen una conductancia eléctrica dada por ${\displaystyle c}$. Sea ${\displaystyle C(x)=\sum _{y\in V}c(x,y)}$ y si suponemos ${\displaystyle c(x)<\infty }$ para cada ${\displaystyle x\in V}$. La cadena de Márkov ${\displaystyle X=(X_{n})_{n\in \mathbb {N} }}$ con espacio de estados ${\displaystyle V}$ y matriz de transición ${\displaystyle P}$ dada por:

${\displaystyle \pi _{xy}:=P(X_{n+1}=y|X_{n}=x)=\displaystyle {\frac {c(x,y)}{C(x)}},{\mbox{ }}(x,y)\in V^{2}}$

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 x\in 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.

Caminata aleatoria simétrica

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

• ${\displaystyle C(x)=c\cdot d(x){\mbox{ para cada }}x\in V}$
• La matriz de transición está dada por:

${\displaystyle \pi _{xy}={\begin{cases}1/d(x),&{\mbox{si }}y\in N(x)\\0,&{\mbox{si }}y\not \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 llamadacaminata aleatoria simétrica en ${\displaystyle G}$.

Caminatas aleatorias en cuadrículas

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

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

donde ${\displaystyle p\in (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):¹¹ 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

${\displaystyle \pi _{00}^{(2n)}=\displaystyle {\binom {2n}{n}}p^{n}(1-p)^{n}{\mbox{ y }}\pi _{00}^{(2n-1)}=0{\mbox{ para todo }}n\geq 1}$

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\neq 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}$.¹¹ 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 éste.

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

Paseo aleatorio en dos dimensiones.

En el caso general considere ${\displaystyle \mathbb {Z} ^{k}}$ con ${\displaystyle k\in \mathbb {N} ^{+}}$. Para ${\displaystyle i\in \{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:

${\displaystyle \pi _{x,x+e_{i}}=p_{i},\pi _{x,x-e_{i}}=q_{i};{\mbox{ }}x\in \mathbb {Z} ^{k},{\mbox{ }}i\in \{1,2,\cdots ,k\}}$

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

${\displaystyle \pi _{00}^{(2n)}\approx \displaystyle {\frac {C_{k}}{n^{k/2}}}}$

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 k\in \{1,2\}}$, mientras ${\displaystyle \pi _{00}^{*}<\infty }$ y la cadena es transitoria si ${\displaystyle k\in \{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.

Otros resultados

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

1. Si ${\displaystyle G}$ es conexo, entonces ${\displaystyle X}$ es irreducible.
2. Si ${\displaystyle G}$ es conexo y finito, entonces ${\displaystyle X}$ es recurrente.
3. En particular, si ${\displaystyle G}$ no es conexo, las componentes conexas de ${\displaystyle G}$ que son finitas, resultan recurrentes.

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:

1. Una caminata aleatoria positiva recurrente ${\displaystyle X}$ en un grafo ${\displaystyle G}$ es siempre reversible.
2. Recíprocamente, suponga que ${\displaystyle X}$ es una cadena de Márkov reversible con matriz de transición ${\displaystyle P}$ y función de densidad de probabilidad invariante ${\displaystyle f}$. Suponga ${\displaystyle P_{xx}=0}$ para cada ${\displaystyle x\in S}$. Entonces ${\displaystyle X}$ puede ser interpretada como una caminata aleatoria sobre el grafo ${\displaystyle G}$ con ${\displaystyle V=S}$ y ${\displaystyle E=\{(x,y)\in S^{2}:P_{xy}>0\}}$ con función de conductancia dada por:

${\displaystyle {\mbox{ }}c(x,y)=f(x)\cdot P_{xy},{\mbox{ }}(x,y)\in S^{2}}$

Aplicaciones

Quantum Cloud es una escultura hecho por Antony Gormley diseñada con un algoritmo de caminatas aleatorias.

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 lateorí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 ${\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.

Paseo aleatorio simulado bidimensional asemejando unmovimiento 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 Bes 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.