Saltar al contenido principal
Library homepage
 
LibreTexts Español

16.14: Caminatas Aleatorias en Gráficas

  • Page ID
    152013
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    \(\newcommand{\P}{\mathbb{P}}\)\(\newcommand{\E}{\mathbb{E}}\)\(\newcommand{\R}{\mathbb{R}}\)\(\newcommand{\N}{\mathbb{N}}\)\(\newcommand{\Z}{\mathbb{Z}}\)\(\newcommand{\bs}{\boldsymbol}\)

    Teoría Básica

    Introducción

    Supongamos que\( G = (S, E) \) es una gráfica con conjunto de vértices\( S \) y conjunto de bordes\( E \subseteq S^2 \). Suponemos que la gráfica es desdirigida (quizás un término mejor sería bidirigido) en el sentido de que\( (x, y) \in E \) si y solo si\( (y, x) \in E \). El conjunto de vértices\( S \) es contable, pero puede ser infinito. Dejar\( N(x) = \{y \in S: (x, y) \in E\} \) denotar el conjunto de vecinos de un vértice\( x \in S \), y dejar\( d(x) = \#[N(x)] \) denotar el grado de\( x \). Suponemos que\( N(x) \neq \emptyset \) para\( x \in S \), así no\( G \) tiene puntos aislados.

    Supongamos ahora que hay una conductancia\( c(x, y) \gt 0 \) asociada a cada borde\( (x, y) \in E \). La conductancia es simétrica en el sentido de que\( c(x, y) = c(y, x) \) para\( (x, y) \in E \). Nos extendemos\( c \) a una función en todos\( S \times S \) definiendo\( c(x, y) = 0 \) para\( (x, y) \notin E \). Que\[ C(x) = \sum_{y \in S} c(x, y), \quad x \in S \] así\( C(x) \) sea la conductancia total de los bordes que vienen de\( x \). Nuestra suposición principal es que\( C(x) \lt \infty \) para\( x \in S \). Como sugiere la terminología, imaginamos un fluido de algún tipo que fluye a través de los bordes de la gráfica, de manera que la conductancia de un borde mide la capacidad del borde en algún sentido. Una de las mejores interpretaciones es que la gráfica es una red eléctrica y los bordes son resistencias. En esta interpretación, la conductancia de una resistencia es la recíproca de la resistencia.

    En algunas aplicaciones, específicamente la red de resistencias que acabamos de mencionar, es apropiado imponer la suposición adicional de que no\( G \) tiene bucles, de manera que\( (x, x) \notin E \) para cada una\( x \in S \). No obstante, esa suposición no es matemáticamente necesaria para las cadenas de Markov que consideraremos en esta sección.

    La cadena de Markov de tiempo discreto\( \bs{X} = (X_0, X_1, X_2, \ldots) \) con espacio de estado\( S \) y matriz de probabilidad de transición\( P \) dada por\[ P(x, y) = \frac{c(x, y)}{C(x)}, \quad (x, y) \in S^2 \] se denomina caminata aleatoria en la gráfica\( G \).

    Justificación

    Primero,\( P(x, y) \ge 0 \) para\( x, \, y \in S \). A continuación, por definición de\( C \),\[ \sum_{y \in S} P(x, y) = \sum_{y \in S} \frac{c(x, y)}{C(x)} = \frac{C(x)}{C(x)} = 1, \quad x \in S \] sp\( P \) es una matriz de transición válida en\( S \). Además,\( P(x, y) \gt 0 \) si y solo\( c(x, y) \gt 0 \) si y solo si\( (x, y) \in E \), entonces la gráfica de estado de\( \bs{X} \) es\( G \), la gráfica con la que empezamos.

    Esta cadena gobierna una partícula que se mueve a lo largo de los vértices de\( G \). Si la partícula está en el vértice\( x \in S \) en un momento dado, entonces la partícula estará en un vecino de\( x \) en la próxima vez; el vecino se elige aleatoriamente, en proporción a la conductancia. En el ajuste de una red eléctrica, es natural interpretar la partícula como un electrón. Tenga en cuenta que multiplicar la función de conductancia\( c \) por una constante positiva no tiene ningún efecto en la caminata aleatoria asociada.

    Supongamos que\( d(x) \lt \infty \) para cada uno\( x \in S \) y eso\( c \) es constante en los bordes. Entonces

    1. \( C(x) = c d(x) \)para cada\( x \in S \).
    2. La matriz de transición\( P \) viene dada por\( P(x, y) = \frac{1}{d(x)}\) for\( x \in S\) y\(y \in N(x) \), y de\( P(x, y) = 0 \) otra manera.

    La cadena de Markov de tiempo discreto\( \bs{X} \) es la caminata aleatoria simétrica\( G \).

    Prueba
    1. \( C(x) = \sum_{y \in N(x)} c(x, y) = c \#[N(x)] = c d(x) \)para\( x \in S \).
    2. \( P(x, y) = c(x, y) / C(x) = c / c d(x) = 1 / d(x) \)para\( x \in S \) y\( y \in N(x) \)

    Así, para la caminata aleatoria simétrica, si el estado está\( x \in S \) en un momento dado, entonces es igualmente probable que el siguiente estado sea cualquiera de los vecinos de\( x \). La suposición de que cada vértice tiene grados finitos significa que la gráfica\( G \) es localmente finita.

    Dejar\( \bs{X} \) ser un paseo al azar sobre una gráfica\( G \).

    1. Si\( G \) está conectado entonces\( \bs{X} \) es irreducible.
    2. Si no\( G \) está conectado entonces las clases de equivalencia de\( \bs{X} \) son los componentes de\( G \) (los subconjuntos conectados máximos de\( S \)).
    Prueba
    1. Recordemos que hay una ruta de longitud\( n \in \N_+ \) entre distintos estados\( x, \, y \in S \) en la gráfica de estado de\( \bs{X} \) si y solo si\( P^n(x, y) \gt 0 \). Si\( G \) está conectado, hay un camino entre cada par de vértices distintos y por lo tanto la cadena\( \bs{X} \) es irreducible.
    2. Esto se desprende de (a).

    Entonces, como de costumbre, usualmente asumiremos que\( G \) está conectado, pues de lo contrario podríamos simplemente restringir nuestra atención a un componente de\( G \). En el caso de que no\( G \) tenga bucles (nuevamente, un caso especial importante por aplicaciones), es fácil caracterizar la periodicidad de la cadena. Para el teorema que sigue, recuerde que\( G \) es bipartito si el conjunto de vértices se\( S \) puede dividir en conjuntos no vacíos y disjuntos\( A \) y\( B \) (las partes) de tal manera que cada borde en\( E \) tiene un punto final en\( A \) y un punto final en\( B \).

    Supongamos que\( \bs{X} \) es una caminata aleatoria sobre una gráfica conectada\( G \) sin bucles. Entonces\( \bs{X} \) es o aperiódica o tiene periodo 2. Además,\( \bs{X} \) tiene periodo 2 si y sólo si\( G \) es bipartita, en cuyo caso las partes son las clases cíclicas de\( \bs{X} \).

    Prueba

    Primero tenga en cuenta que ya que\( G \) está conectada, la cadena\( \bs{X} \) es irreducible, y así todos los estados tienen el mismo periodo. Si\( (x, y) \in E \) entonces\( (y, x) \in E \) también, así vuelve a\( x \in S \), a partir de siempre\( x \) puede ocurrir en enteros incluso positivos. Si\( G \) es bipartita, entonces vuelve a\( x \) comenzar en claramente solo\( x \) puede ocurrir en enteros positivos pares, por lo que el periodo es 2. Por el contrario, si no\( G \) es bipartito entonces\( G \) tiene un ciclo de longitud impar\( k \). Si\( x \) es un vértice en el ciclo, entonces vuelve a\( x \), comenzando en\( x \), puede ocurrir en 2 pasos o en\( k \) pasos, por lo que el periodo de\( x \) es 1.

    Recurrencia positiva y distribuciones invariantes

    Supongamos nuevamente que\( \bs{X} \) es un paseo aleatorio sobre una gráfica\( G \), y supongamos que\( G \) está conectado de manera que eso\( \bs{X} \) es irreducible.

    La función\( C \) es invariante para\( P \). La caminata aleatoria\( \bs{X} \) es recurrente positiva si y solo si\[ K = \sum_{x \in S} C(x) = \sum_{(x, y) \in S^2} c(x, y) \lt \infty \] en cuyo caso la función de densidad de probabilidad invariante\( f \) viene dada por\( f(x) = C(x) / K \) for\( x \in S \).

    Prueba

    Para\( y \in S \),\[ (C P)(y) = \sum_{x \in S} C(x) P(x, y) = \sum_{x \in N(y)} C(x) \frac{c(x, y)}{C(x)} = \sum_{x \in N(y)} c(x, y) = C(y) \] así\( C \) es invariante para\( P \). Los otros resultados se derivan de la teoría general.

    Tenga en cuenta que\( K \) es la conductancia total sobre todos los bordes en\( G \). En particular, por supuesto, si\( S \) es finito entonces\( \bs{X} \) es recurrente positivo, con\( f \) como la función de densidad de probabilidad invariante. Para la caminata aleatoria simétrica, esta es la única forma en que puede ocurrir la recurrencia positiva:

    La caminata aleatoria simétrica\( G \) es recurrente positiva si y solo si el conjunto de vértices\( S \) es finito, en cuyo caso la función\( f \) de densidad de probabilidad invariante viene dada por\[ f(x) = \frac{d(x)}{2 m}, \quad x \in S \] dónde\( d \) está la función de grado y dónde\( m \) está el número de bordes no dirigidos.

    Prueba

    Si tomamos la función de conductancia para ser la constante 1 en los bordes, entonces\( C(x) = d(x) \) y\( K = 2 m \).

    Por otro lado, cuando\( S \) es infinito, la clasificación de\( \bs{X} \) como recurrente o transitoria es complicada. Consideraremos un caso especial interesante a continuación, el paseo aleatorio simétrico\( \Z^k \).

    Rereversibilidad

    Esencialmente, todas las cadenas reversibles de Markov pueden interpretarse como caminatas aleatorias en gráficas. Este hecho es una de las razones para estudiar este tipo de paseos.

    Si\( \bs{X} \) es una caminata aleatoria sobre una gráfica conectada\( G \), entonces\( \bs{X} \) es reversible con respecto a\( C \).

    Prueba

    Dado que la gráfica está conectada,\( \bs{X} \) es irreducible. La observación crucial es que\[ C(x) P(x, y) = C(y) P(y, x), \quad (x, y) \in S^2 \] Si\( (x, y) \in E \) el lado izquierdo es\( c(x, y) \) y el lado derecho es\( c(y, x) \). Si\( (x, y) \notin E \), ambos lados son 0. Se desprende entonces de la teoría general que\( C \) es invariante para\( \bs{X} \) y que\( \bs{X} \) es reversible con respecto a\( C \).

    Por supuesto, si\( \bs{X} \) es recurrente, entonces\( C \) es la única función invariante positiva, hasta la multiplicación por constantes positivas, y así\( \bs{X} \) es simplemente reversible.

    Por el contrario, supongamos que\( \bs{X} \) es una cadena de Markov irreducible\( S \) con matriz de transición\( P \) y función invariante positiva\( g \). Si\( \bs{X} \) es reversible con respecto a\( g \) entonces\( \bs{X} \) es la caminata aleatoria en la gráfica de estado con la función de conductancia\( c \) dada por\( c(x, y) = g(x) P(x, y) \) for\( (x, y) \in S^2 \).

    Prueba

    Ya que\( \bs{X} \) es reversible con respecto a\( g \),\( g \) y\( P \) satisfacer\( g(x) P(x, y) = g(y) P(y, x) \) para cada\( (x, y) \in S^2 \). Obsérvese que la gráfica\( G \) de estado de\( \bs{X} \) es bi-dirigida ya que\( P(x, y) \gt 0 \) si y solo si\( P(y, x) \gt 0 \), y que la función\( c \) dada en el teorema es simétrica, de manera que\( c(x, y) = c(y, x) \) para todos\( (x, y) \in S^2 \). Por último, señalar\[ C(x) = \sum_{y \in S} c(x, y) = \sum_{y \in S} g(x) P(x, y) = g(x), \quad x \in S \] que\( P(x, y) = c(x, y) \big/ C(x) \) para que para\( (x, y) \in S^2 \), según se requiera.

    Nuevamente, en el importante caso especial que\( \bs{X} \) es recurrente, existe una función invariante positiva\( g \) que es única hasta la multiplicación por constantes positivas. En este caso el teorema afirma que una cadena irreducible, recurrente, reversible es una caminata aleatoria sobre la gráfica estatal.

    Ejemplos y Aplicaciones

    Gráfico del puente de Wheatstone

    La gráfica a continuación se llama el puente Wheatstone en honor a Charles Wheatstone.

    Red de puentes de Wheatstone
    Figura\(\PageIndex{1}\): La red de puentes de Wheatstone, con valores de conductancia en rojo

    En esta subsección, deja\( \bs{X} \) ser el paseo aleatorio sobre el puente de Wheatstone arriba, con los valores de conductancia dados.

    Para la caminata aleatoria\( \bs{X} \),

    1. Dar explícitamente la matriz de probabilidad de transición\( P \).
    2. Dado\( X_0 = a \), encontrar la función de densidad de probabilidad de\( X_2 \).
    Responder

    Para la matriz y el vector a continuación, utilizamos el espacio de estado ordenado\( S = (a, b, c, d) \).

    1. \( P = \left[ \begin{matrix} 0 & \frac{1}{2} & 0 & \frac{1}{2} \\ \frac{1}{4} & 0 & \frac{1}{4} & \frac{1}{2} \\ 0 & \frac{1}{3} & 0 & \frac{2}{3} \\ \frac{1}{5} & \frac{2}{5} & \frac{2}{5} & 0 \end{matrix} \right] \)
    2. \( f_2 = \left( \frac{9}{40}, \frac{1}{5}, \frac{13}{40}, \frac{1}{4} \right) \)

    Para la caminata aleatoria\( \bs{X} \),

    1. Demostrar que\( \bs{X} \) es aperiódico.
    2. Encuentra la función de densidad de probabilidad invariante.
    3. Encuentra el tiempo medio de retorno a cada estado.
    4. Encontrar\( \lim_{n \to \infty} P^n \).
    Responder

    Para la matriz y los vectores a continuación, utilizamos el espacio de estado ordenado\( (a, b, c, d) \).

    1. La cadena es aperiódica ya que la gráfica no es bipartita. (Tenga en cuenta que la gráfica tiene triángulos.)
    2. \( f = \left(\frac{1}{7}, \frac{2}{7}, \frac{3}{14}, \frac{5}{14} \right) \)
    3. \( \mu = \left(7, \frac{7}{2}, \frac{14}{3}, \frac{14}{5} \right) \)
    4. \( P^n \to \left[ \begin{matrix} \frac{1}{7} & \frac{2}{7} & \frac{3}{14} & \frac{5}{14} \\ \frac{1}{7} & \frac{2}{7} & \frac{3}{14} & \frac{5}{14} \\ \frac{1}{7} & \frac{2}{7} & \frac{3}{14} & \frac{5}{14} \\ \frac{1}{7} & \frac{2}{7} & \frac{3}{14} & \frac{5}{14} \\ \end{matrix} \right] \)como\( n \to \infty \)

    El Cube Graph

    La gráfica a continuación es la gráfica de cubo tridimensional. Los vértices son cadenas de bits de longitud 3, y dos vértices están conectados por un borde si y solo si las cadenas de bits difieren en un solo bit.

    Imagen del gráfico de cubos
    Figura\(\PageIndex{2}\): El gráfico de cubos con valores de conductancia en rojo

    En esta subsección, vamos a\( \bs{X} \) denotar el paseo aleatorio sobre el gráfico de cubo anterior, con los valores de conductancia dados.

    Para la caminata aleatoria\( \bs{X} \),

    1. Dar explícitamente la matriz de probabilidad de transición\( P \).
    2. Supongamos que la distribución inicial es la distribución uniforme en\( \{000, 001, 101, 100\} \). Encuentra la función de densidad de probabilidad de\( X_2 \).
    Responder

    Para la matriz y el vector a continuación, utilizamos el espacio de estado ordenado\( S = (000, 001, 101, 110, 010, 011, 111, 101 ) \).

    1. \( P = \left[ \begin{matrix} 0 & \frac{1}{4} & 0 & \frac{1}{4} & \frac{1}{2} & 0 & 0 & 0 \\ \frac{1}{4} & 0 & \frac{1}{4} & 0 & 0 & \frac{1}{2} & 0 & 0 \\ 0 & \frac{1}{4} & 0 & \frac{1}{4} & 0 & 0 & \frac{1}{2} & 0 \\ \frac{1}{4} & 0 & \frac{1}{4} & 0 & 0 & 0 & 0 & \frac{1}{2} \\ \frac{1}{4} & 0 & 0 & 0 & 0 & \frac{3}{9} & 0 & \frac{3}{8} \\ 0 & \frac{1}{4} & 0 & 0 & \frac{3}{8} & 0 & \frac{3}{8} & 0 \\ 0 & 0 & \frac{1}{4} & 0 & 0 & \frac{3}{8} & 0 & \frac{3}{8} \\ 0 & 0 & 0 & \frac{1}{4} & \frac{3}{8} & 0 & \frac{3}{8} & 0 \end{matrix} \right] \)
    2. \( f_2 = \left(\frac{3}{32}, \frac{3}{32}, \frac{3}{32}, \frac{3}{32}, \frac{5}{32}, \frac{5}{32}, \frac{5}{32}, \frac{5}{32}\right) \)

    Para la caminata aleatoria\( \bs{X} \),

    1. Demostrar que la cadena tiene periodo 2 y encontrar las clases cíclicas.
    2. Encuentra la función de densidad de probabilidad invariante.
    3. Encuentra el tiempo medio de retorno a cada estado.
    4. Encontrar\( \lim_{n \to \infty} P^{2 n} \).
    5. Encontrar\( \lim_{n \to \infty} P^{2 n + 1} \).
    Responder

    Para la matriz y el vector a continuación, utilizamos el espacio de estado ordenado\( S = (000, 001, 101, 110, 010, 011, 111, 101) \).

    1. La cadena tiene periodo 2 ya que la gráfica es bipartita. Las clases cíclicas son\( \{000, 011, 110, 101\} \) (cadenas de bits con un número par de 1's) y\( \{010, 001, 100, 111\} \) (cadenas de bits con un número impar de 1's).
    2. \( f = \left(\frac{1}{12}, \frac{1}{12}, \frac{1}{12}, \frac{1}{12}, \frac{1}{6}, \frac{1}{6}, \frac{1}{6}, \frac{1}{6}\right) \)
    3. \( \mu = (12, 12, 12, 12, 6, 6, 6, 6) \)
    4. \( P^{2 n} \to \left[ \begin{matrix} \frac{1}{6} & 0 & \frac{1}{6} & 0 & 0 & \frac{1}{3} & 0 & \frac{1}{3} \\ 0 & \frac{1}{6} & 0 & \frac{1}{6} & \frac{1}{3} & 0 & \frac{1}{3} & 0 \\ \frac{1}{6} & 0 & \frac{1}{6} & 0 & 0 & \frac{1}{3} & 0 & \frac{1}{3} \\ 0 & \frac{1}{6} & 0 & \frac{1}{6} & \frac{1}{3} & 0 & \frac{1}{3} & 0 \\ 0 & \frac{1}{6} & 0 & \frac{1}{6} & \frac{1}{3} & 0 & \frac{1}{3} & 0 \\ \frac{1}{6} & 0 & \frac{1}{6} & 0 & 0 & \frac{1}{3} & 0 & \frac{1}{3} \\ 0 & \frac{1}{6} & 0 & \frac{1}{6} & \frac{1}{3} & 0 & \frac{1}{3} & 0 \\ \frac{1}{6} & 0 & \frac{1}{6} & 0 & 0 & \frac{1}{3} & 0 & \frac{1}{3} \end{matrix} \right] \)como\( n \to \infty \)
    5. \( P^{2 n + 1} \to \left[ \begin{matrix} 0 & \frac{1}{6} & 0 & \frac{1}{6} & \frac{1}{3} & 0 & \frac{1}{3} & 0 \\ \frac{1}{6} & 0 & \frac{1}{6} & 0 & 0 & \frac{1}{3} & 0 & \frac{1}{3} \\ 0 & \frac{1}{6} & 0 & \frac{1}{6} & \frac{1}{3} & 0 & \frac{1}{3} & 0 \\ \frac{1}{6} & 0 & \frac{1}{6} & 0 & 0 & \frac{1}{3} & 0 & \frac{1}{3} \\ \frac{1}{6} & 0 & \frac{1}{6} & 0 & 0 & \frac{1}{3} & 0 & \frac{1}{3} \\ 0 & \frac{1}{6} & 0 & \frac{1}{6} & \frac{1}{3} & 0 & \frac{1}{3} & 0 \\ \frac{1}{6} & 0 & \frac{1}{6} & 0 & 0 & \frac{1}{3} & 0 & \frac{1}{3} \\ 0 & \frac{1}{6} & 0 & \frac{1}{6} & \frac{1}{3} & 0 & \frac{1}{3} & 0 \end{matrix} \right] \)como\( n \to \infty \)

    Modelos Especiales

    Recordemos que la cadena básica de Ehrenfest con\( m \in \N_+ \) bolas es reversible. Interpretar la cadena como una caminata aleatoria sobre una gráfica, esbozar la gráfica y encontrar una función de conductancia.

    Responder

    La gráfica estatal\( G \) de la cadena básica de Ehrenfest con\( m \) bolas es el camino de 0 a\( m \) sin bucles. Una función de conductancia\( c \) es\( c(x, x + 1) = \binom{m - 1}{x} \) para\( x \in \{0, 1, \ldots, m - 1\} \).

    Recordemos que la cadena Ehrenfest modificada con\( m \in \N_+ \) bolas es reversible. Interpretar la cadena como una caminata aleatoria sobre una gráfica, esbozar la gráfica y encontrar una función de conductancia.

    Responder

    La gráfica estatal\( G \) de la cadena Ehrenfest modificada con\( m \) bolas es el camino de 0 a\( m \) con bucles. Una función de conductancia\( c \) es\( c(x, x + 1) = \frac{1}{2}\binom{m - 1}{x} \) para\( x \in \{0, 1, \ldots, m - 1\} \) y\( c(x, x) = \frac{1}{2} \binom{m}{x} \) para\( x \in \{0, 1, \ldots, m\} \).

    Recordemos que la cadena Bernoulli-Laplace con\( j \in \N_+ \) bolas en urna 0,\( k \in \N_+\) bolas en urna 1, y con\( r \in \{0, \ldots, j + k\} \) de las bolas rojas, es reversible. Interpretar la cadena como una caminata aleatoria sobre una gráfica, esbozar la gráfica y encontrar una función de conductancia. Simplificar la función de conductancia en el caso especial que\( j = k = r \).

    Responder

    El gráfico estatal\( G \) de la cadena Bernoulli-Lapace con\( j \) bolas en urna 0,\( k \) bolas en urna 1, y con\( r \) de las bolas rojas, es el camino de\( \max\{0, r - j\} \) a\( \min\{k, r\} \) con bucles. Una función de conductancia\( c \) viene dada por\ begin {align*} c (x, x + 1) & =\ binom {r} {x}\ binom {j + k - r} {k - x} (r - x) (k - x),\ quad x\ in\ {\ max\ {0, r - j\},\ ldots,\ min\ {k, r\} - 1\}\\ c (x, x) & =\ binom {r} {x}\ binom {j + k - r} {k - x} [(r - x) x + (j - r + x) (k - x)],\ cuádruple x\ in\ {\ max\ {0, r - j \},\ ldots,\ min\ {k, r\}\}\ end {align*} En el caso especial que\( j = k = r \), una función de conductancia es\ begin {align*} c (x, x + 1) & =\ binom {k} {x}\ binom {k} {k - x} (k - x) ^2,\ quad x\ in\ {0,\ ldots, k - 1\}\ c (x, x) & =\ binom {k} {x}\ binom {k} {k - x} 2 x (k - x),\ quad x\ in\ {0,\ ldots, k\}\ end {align *}

    Caminatas aleatorias en\( \Z \)

    Las caminatas aleatorias en celosías enteras son particularmente interesantes debido a su clasificación como transitoria o recurrente. Consideramos el caso unidimensional en esta subsección, y el caso dimensional superior en la siguiente subsección.

    Dejar\( \bs{X} = (X_0, X_1, X_2, \ldots) \) ser la cadena de Markov de tiempo discreto con espacio de estado\( \Z \) y matriz de probabilidad de transición\( P \) dada por\[ P(x, x + 1) = p, \; P(x, x - 1) = 1 - p, \quad x \in \Z \] donde\( p \in (0, 1) \). La cadena\( \bs{X} \) se llama el simple paseo aleatorio\( \Z \) con parámetro\( p \).

    Se utiliza el término simple porque las probabilidades de transición que comienzan en estado\( x \in \Z \) no dependen de ellas\( x \). Así, la cadena es espacial así como temporalmente homogénea. En el caso especial\( p = \frac{1}{2} \), la cadena\( \bs{X} \) es el simple paseo aleatorio simétrico\( \Z \). Las propiedades básicas de la simple caminata aleatoria y\( \Z \), en particular, la simple caminata aleatoria simétrica, se estudiaron en el capítulo sobre los ensayos de Bernoulli. Por supuesto, la gráfica estatal\( G \) de\( \bs{X} \) tiene vértice establecido\( \Z \), y los vecinos de\( x \in \Z \) son\( x + 1 \) y\( x - 1 \). No queda claro de inmediato que\( \bs{X} \) se trate de un paseo aleatorio\( G \) asociado a una función de conductancia, que después de todo, es el tema de esta sección. Pero ese hecho y más se derivan del siguiente resultado.

    Dejar\( g \) ser la función en\( \Z \) definida por\[ g(x) = \left(\frac{p}{1 - p}\right)^x, \quad x \in \Z \] Entonces

    1. \(g(x) P(x, y) = g(y) P(y, x)\)para todos\( (x, y) \in \Z^2 \)
    2. \( g \)es invariante para\( \bs{X} \)
    3. \( \bs{X} \)es reversible con respecto a\( g \)
    4. \( \bs{X} \)es el paseo aleatorio\( \Z \) con la función de conductancia\( c \) dada por\( c(x, x + 1) = p^{x+1} \big/ (1 - p)^x \) for\(x \in \Z \).
    Prueba
    1. Para\( x \in \Z \), sólo tenemos que considerar\( y = x \pm 1 \). \ begin {alinear*} g (x) P (x, x - 1) & =\ frac {p^x} {(1 - p) ^ {x-1}} = g (x - 1) P (x - 1, x)\ g (x) P (x, x + 1) & =\ frac {p^ {x+1}} {(1 - p) ^x} = g (x + 1) P (x + 1, x)\ final {alinear*}
    2. Esto se desprende de (a) y la teoría general.
    3. Esto se desprende de (a) y (b) y la teoría general.
    4. Del resultado anterior,\( \bs{X} \) es el paseo aleatorio\( G \) asociado con la función de conductancia\( c \) dada por\( c(x, y) = g(x) P(x, y) \). Por simetría, basta con considerar el borde\( (x, x + 1) \), y en este caso,\( c \) se da en la segunda ecuación mostrada arriba.

    En particular, la simple caminata aleatoria simétrica es la caminata aleatoria simétrica\( G \).

    La cadena\( \bs{X} \) es irreducible y periódica con el periodo 2. Además\[ P^{2 n}(0, 0) = \binom{2 n}{n} p^n (1 - p)^n, \quad n \in \N \]

    Prueba

    La cadena es irreducible ya que\( G \) está conectada. La cadena es periódica ya que no\( G \) tiene bucles y es bipartita, siendo las partes los enteros impares y pares. Por último, tenga en cuenta que comenzando en el estado 0, la cadena vuelve a 0 en el momento\( 2 n \) si y solo si hay\( n \) pasos a la derecha y\( n \) pasos a la izquierda.

    Clasificación de la simple caminata aleatoria sobre\( \Z \).

    1. Si\( p \ne \frac{1}{2} \) entonces\( \bs{X} \) es transitorio.
    2. Si\( p = \frac{1}{2} \) entonces\( \bs{X} \) es nulo recurrente.
    Prueba

    Del resultado anterior y la aproximación de Stirling,\[ P^{2 n}(0, 0) \approx \frac{[4 p (1 - p)]^n}{\sqrt{\pi \, n}} \text{ as } n \to \infty \] Let\( R(x, y) = \sum_{n=0}^\infty P^n(x, y) \) for\( (x, y) \in \Z^2 \), así que esa\(R\) es la matriz potencial. Recordemos que\( R(x, y) \) es el número esperado de visitas para\( y \) comenzar en\( x \) para\( (x, y) \in \Z^2 \). Si\( p \ne \frac{1}{2} \) entonces\( R(0, 0) \lt \infty \) y por lo tanto\( \bs{X} \) es transitorio. Si\( p = \frac{1}{2} \) entonces\( R(0, 0) = \infty \) y por lo tanto\( \bs{X} \) es recurrente. En este caso\( \bs{X} \) debe ser nulo recurrente a partir de nuestros resultados generales anteriores, ya que el conjunto de vértices es infinito.

    Entonces, para la celosía unidimensional\( \Z \), la caminata aleatoria\( \bs{X} \) es transitoria en el caso no simétrico, y nulo recurrente en el caso simétrico. Volvamos a las funciones invariantes de\( \bs{X} \)

    Considera de nuevo el andar\( \bs{X} \) al azar\( \Z \) con parámetro\( p \in (0, 1) \). La función constante\(\bs{1} \) on\( \Z \) y la función\( g\) dada por\[ g(x) = \left(\frac{p}{1 - p}\right)^x, \quad x \in \Z \] son invariantes para\( \bs{X} \). Todas las demás funciones invariantes son combinaciones lineales de estas dos funciones.

    Prueba

    La condición\( h \) para ser invariante,\( h P = h \), conduce a la siguiente ecuación lineal de diferencia de segundo orden:\[(1 - p) h(y + 1) - h(y) + (1 + p) h(y - 1), \quad y \in \Z\] La ecuación característica es la\( (1 - p) r^2 - r + (1 + p) = 0 \) que tiene raíces\( r = 1 \) y\( r = p \big/ (1 - p) \). Las soluciones correspondientes a las raíces son\( \bs{1} \) y\( g \), respectivamente. De ahí que el resultado se deduce de la teoría general de las ecuaciones de diferencia lineal.

    Tenga en cuenta que cuando\( p = \frac{1}{2} \), la función constante\( \bs{1} \) es la única función invariante positiva, hasta la multiplicación por constantes positivas. Pero sabemos que este tiene que ser así ya que la cadena es recurrente cuando\( p = \frac{1}{2} \). Además, la cadena es reversible. En el caso no simétrico, cuando\( p \ne \frac{1}{2} \), tenemos un ejemplo de una cadena transitoria que, sin embargo, tiene funciones invariantes no triviales, de hecho, un espacio bidimensional de tales funciones. También,\( \bs{X} \) es reversible con respecto a\( g \), como se mostró anteriormente, pero la inversión de\( \bs{X} \) con respecto a\( \bs{1} \) es la cadena con matriz de transición\( Q \) dada por\( Q(x, y) = P(y, x) \) for\( (x, y) \in \Z^2 \). Esta cadena es solo el simple paseo aleatorio\( Z \) con parámetro\( 1 - p \). Entonces, la caminata aleatoria simple no simétrica es un ejemplo de una cadena transitoria que es reversible con respecto a una medida invariante pero no con respecto a otra medida invariante.

    Caminatas aleatorias en\( \Z^k \)

    De manera más general, ahora consideramos\( \Z^k \), dónde\( k \in \N_+ \). Para\( i \in \{1, 2, \ldots, k\} \), vamos a\( \bs{u}_i \in \Z^k \) denotar el vector unitario con 1 en posición\( i \) y 0 en otra parte. La celosía entera\( k \) -dimensional\( G \) tiene un vértice establecido\( Z^k \), y los vecinos de\( \bs{x} \in \Z^k \) son\( \bs{x} \pm \bs{u}_i \) para\( i \in \{1, 2, \ldots, k\} \). Entonces, en particular, cada vértice tiene\( 2 k \) vecinos.

    \( \mathscr{X} = (\bs{X}_1, \bs{X_2}, \ldots) \)Sea la cadena de Markov encendida\( \Z^k \) con la matriz de probabilidad de transición\( P \) dada por\[ P(\bs{x},\bs{x} + \bs{u}_i) = p_i, \; P(\bs{x}, \bs{x} - \bs{u}_i) = q_i; \quad \bs{x} \in \Z^k, \; i \in \{1, 2, \ldots, k\} \] dónde\( p_i \gt 0 \),\( q_i \gt 0 \) para\( i \in \{1, 2, \ldots, k\} \) y\( \sum_{i=1}^k (p_i + q_i) = 1 \). La cadena\( \mathscr{X} \) es el simple paseo aleatorio\( \Z^k \) con parámetros\( \bs{p} = (p_1, p_2, \ldots, p_k) \) y\( \bs{q} = (q_1, q_2, \ldots, q_k) \).

    Nuevamente, el término simple significa que las probabilidades de transición a partir de las\( \bs{x} \in \Z^k \) no dependen\( \bs{x} \), de manera que la cadena es espacialmente homogénea así como temporalmente homogénea. En el caso especial que\( p_i = q_i = \frac{1}{2 k} \) para\( i \in \{1, 2, \ldots, k\} \),\( \mathscr{X} \) es el simple paseo aleatorio simétrico sobre\( Z^k \). El siguiente teorema es la generalización natural del resultado abpve para el caso unidimensional.

    Definir la función\( g: \Z^k \to (0, \infty) \) por\[ g(x_1, x_2, \ldots, x_k) = \prod_{i=1}^k \left(\frac{p_i}{q_i}\right)^{x_i}, \quad (x_1, x_2, \ldots, x_k) \in \Z^k \] Entonces

    1. \( g(\bs{x}) P(\bs{x}, \bs{y}) = g(\bs{y}) P(\bs{y}, \bs{x}) \)para todos\( \bs{x}, \, \bs{y} \in \Z^k \)
    2. \( g \)es invariante para\( \mathscr{X} \).
    3. \( \mathscr{X} \)es reversible con respecto a\( g \).
    4. \( \mathscr{X} \)es el paseo aleatorio\( G \) con la función de conductancia\( c \) dada por\( c(\bs{x}, \bs{y}) = g(\bs{x}) P(\bs{x}, \bs{y}) \) for\( \bs{x}, \, \bs{y} \in \Z^k \).
    Prueba
    1. Para\( \bs{x} = (x_1, x_2, \ldots, x_k) \in Z^k \), los únicos casos de interés son\( \bs{y} = \bs{x} \pm \bs{u}_i \) para\( i \in \{1, 2, \ldots, k\} \), ya que en todos los demás casos, los lados izquierdo y derecho son 0. Pero\ begin {alinear*} g (\ bs {x}) P (\ bs {x},\ bs {x} +\ bs {u} _i) & =\ prod_ {j\ ne i}\ left (\ frac {p_j} {q_j}\ right) ^ {x_j}\ cdot\ frac {p_i^ {x_i + 1}} {q_i _i^ {x_i}} = g (\ bs {x} +\ bs {u} _i) P (\ bs {x} +\ bs {u} _i,\ bs {x})\\ g (\ bs {x}) P (\ bs {x},\ bs {x} -\ bs {u} _i) & =\ prod_ {j\ ne i} izquierda\ (\ frac {p_j} {q_j}\ derecha) ^ {x_j}\ cdot \ frac {p_i^ {x_i}} {q_i^ {x_i - 1}} = g (\ bs {x} -\ bs {u} _i) P (\ bs {x} +\ bs {u} _i,\ bs {x})\ end {align*}
    2. Esto se desprende de (a).
    3. Esto se desprende de los apartados a) y b).
    4. Esto también se desprende del resultado general anterior.

    En términos de recurrencia y fugacidad, sin duda parecería que cuanto mayor sea la dimensión\( k \), menos probable es que la cadena sea recurrente. Eso es generalmente cierto:

    Clasificación de la simple caminata aleatoria sobre\( \Z^k \).

    1. For\(k \in \{1, 2\} \),\( \mathscr{X} \) es nulo recurrente en el caso simétrico y transitorio para todos los demás valores de los parámetros.
    2. For\( k \in \{3, 4, \ldots\} \),\( \mathscr{X} \) es transitorio para todos los valores de los parámetros.
    Croquis de prueba

    Para algunos de los casos no simétricos, podemos usar el resultado para la dimensión 1. Supongamos\( i \in \{1, 2, \ldots, k\} \) con\( p_i \ne q_i \). Si consideramos los tiempos en los que\( \mathscr{X} \) cambia la coordenada\( i \) de la caminata aleatoria, tenemos una caminata aleatoria unidimensional incrustada con parámetro\( p = p_i \big/ (p_i + q_i) \) (la probabilidad de un paso en la dirección positiva). Ya que\( p \ne \frac{1}{2} \), esta caminata aleatoria incrustada es transitoria y por lo tanto fallará al volver a 0, comenzando en 0, con probabilidad positiva. Pero si esta caminata aleatoria incrustada no logra regresar a 0, comenzando en 0, entonces la caminata aleatoria padre\( \mathscr{X} \) no regresa a\( \bs{0} \) comenzar en\( \bs{0} \). De ahí\( \mathscr{X} \) que sea transitorio.

    Para el caso simétrico, la prueba general es similar en la prueba para la dimensión 1, pero los detalles son considerablemente más complejos. Un retorno a\( 0 \) puede ocurrir sólo en momentos pares y\[ P^{2 n}(\bs{0}, \bs{0}) \approx \frac{C_k}{n^{k/2}} \text{ as } n \to \infty \text{ where } C_k = \frac{k^{k/2}}{\pi^{k/2} 2^{k-1}}\] así para la matriz potencial que\( R \) tenemos\( R(\bs{0}, \bs{0}) = \infty \) y la cadena es recurrente si\( k \in \{1, 2\} \) while\( R(\bs{0}, \bs{0}) \lt \infty \) y la cadena es transitoria si\( k \in \{3, 4, \ldots\} \).

    Entonces, para el paseo aleatorio simple y simétrico sobre la celosía entera\( \Z^k \), tenemos el siguiente interesante desplazamiento de fase dimensional: la cadena es nula recurrente en las dimensiones 1 y 2 y transitoria en dimensiones 3 o más.

    Volvamos a las funciones invariantes positivas para\( \mathscr{X} \). Nuevamente, los resultados generalizan los del caso unidimensional.

    Para\( J \subseteq \{1, 2 \ldots, k\} \), define\( g_J \) on\( \Z^k \) por\[ g_J(x_1, x_2, \ldots, x_k) = \prod_{j \in J} \left(\frac{p_j}{q_j}\right)^{x_j}, \quad (x_1, x_2, \ldots, x_k) \in \Z^k \] Let\( \mathscr{X}_J \) denotar el simple paseo aleatorio\( \Z^k \) con matriz de transición\( P_J \), correspondiente a los vectores de parámetros\( \bs{p}^J \) y\( \bs{q^J} \), wherre\(p^J_j = p_j \),\(q^J_j = q_j \) for\( j \in J \), y\( p^J_j = q_j \),\(q^J_j = p_j \) para\( j \notin J \). Entonces

    1. \( g_J(\bs{x}) P(\bs{x}, \bs{y}) = g_J(\bs{y}) P_J(\bs{y}, \bs{x}) \)para todos\( \bs{x}, \, \bs{y} \in \Z^k \)
    2. \( g_J \)es invariante para\( \mathscr{X} \).
    3. \( \mathscr{X}_J \)es inversión de\( \mathscr{X} \) con respecto a\( g_J \).
    Prueba

    La parte (a) se desprende de la simple sustitución. Las partes (b) y (c) se derivan de (a) y la teoría general.

    Obsérvese que cuando\( J = \emptyset \)\( J = \{1, 2, \ldots, k\} \),\( g_J = \bs{1} \) y cuando\( g_J = g \), la función invariante introducida anteriormente. Entonces, en el caso completamente no simétrico donde\( p_i \ne q_i \) para cada uno\( i \in \{1, 2, \ldots, k\} \), la caminata aleatoria\( \mathscr{X} \) tiene funciones invariantes\( 2^k \) positivas que son linealmente independientes, y\( \mathscr{X} \) es reversible con respecto a una de ellas.


    This page titled 16.14: Caminatas Aleatorias en Gráficas is shared under a CC BY 2.0 license and was authored, remixed, and/or curated by Kyle Siegrist (Random Services) via source content that was edited to the style and standards of the LibreTexts platform; a detailed edit history is available upon request.