Saltar al contenido principal
LibreTexts Español

5.3: Cadenas Markov Reversibles

  • Page ID
    86197
  • \( \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{\vectorA}[1]{\vec{#1}}      % arrow\)

    \( \newcommand{\vectorAt}[1]{\vec{\text{#1}}}      % arrow\)

    \( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

    \( \newcommand{\vectorC}[1]{\textbf{#1}} \)

    \( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)

    \( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)

    \( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)

    \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

    \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

    \(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)

    Muchas cadenas importantes de Markov tienen la propiedad de que, en estado estacionario, la secuencia de estados miraba hacia atrás en el tiempo, es decir,. \(X_{n+1}, X_{n}, X_{n-1}, \ldots\), tiene la misma estructura probabilística que la secuencia de estados que avanza en el tiempo. Esta equivalencia entre la cadena delantera y la cadena hacia atrás conduce a una serie de resultados que son intuitivamente bastante sorprendentes y que son bastante dicultos de derivar sin usar esta equivalencia. Estudiaremos estos resultados aquí y luego los extenderemos en el Capítulo 6 a los procesos de Markov con un espacio de estado discreto. Este conjunto de ideas, y su uso en las redes de colas y colas, ha sido un área activa de investigación de colas a lo largo de muchos años. Conduce a muchos resultados simples para sistemas que inicialmente se ven muy complejos. Aquí solo rascamos la superficie y remitimos al lector interesado a [13] para un tratamiento más integral. Antes de entrar en reversibilidad, describimos la cadena atrasada para una cadena arbitraria de Markov.

    La característica definitoria de una cadena de Markov\(\left\{X_{n} ; n \geq 0\right\}\) es que para todos\(n \geq 0\),

    \[\operatorname{Pr}\left\{X_{n+1} \mid X_{n}, X_{n-1}, \ldots, X_{0}\right\}=\operatorname{Pr}\left\{X_{n+1} \mid X_{n}\right\}\label{5.29} \]

    Para cadenas homogéneas, que hemos ido asumiendo a lo largo\(\operatorname{Pr}\left\{X_{n+1}=j \mid X_{n}=i\right\}=P_{ij}\),, independiente de\(n\). Para cualquier\(k>1\), podemos extender\ ref {5.29} para obtener

    \ [\ begin {aligned}
    \ operatorname {Pr} &\ left\ {X_ {n+k}, X_ {n+k-1},\ ldots, X_ {n+1}\ mid X_ {n}, X_ {n-1},\ ldots, X_ {0}\ derecha\}\\
    &=\ nombreoperador {Pr}\ izquierda\ {X_ {n++k}\ mediados X_ {n+k-1}\ derecha\}\ nombreoperador {Pr}\ izquierda\ {X_ {n+k-1}\ mediados X_ {n+k-2}\ derecha\}\ lpuntos\ nombreoperador {Pr}\ izquierda\ {X_ {n+ 1}\ mediados X_ {n}\ derecha\}\\
    &=\ nombreoperador {Pr}\ izquierda\ {X_ {n+k}, X_ {n+k-1},\ ldots, X_ {n+1}\ mediados X_ {n}\ derecha\}
    \ final {alineada}\ etiqueta {5.30}\]

    Al dejar que\(A^{+}\) se defina cualquier evento en los estados\(X_{n+1}\) a\(X_{n+k}\) y dejar que\(A^{-}\) se defina cualquier evento en\(X_{0}\)\(X_{n-1}\), esto se puede escribir de manera más sucinta como

    \[\operatorname{Pr}\left\{A^{+} \mid X_{n}, A^{-}=\operatorname{Pr}\left\{A^{+} \mid X_{n}\right.\right.\label{5.31} \]

    Esto dice que, dado estado\(X_{n}\), cualquier evento futuro\(A^{+}\) es estadísticamente independiente de cualquier evento pasado\(A^{-}\). Este resultado, a saber, que pasado y futuro son independientes dado el estado presente, equivale a\ ref {5.29} para definir una cadena de Markov, pero tiene la ventaja de mostrar la simetría entre pasado y futuro. Esta simetría se logra mejor multiplicando ambos lados de\ ref {5.31} por\(\operatorname{Pr}\left\{A^{-} \mid X_{n}\right\}\), obteniendo 2

    \[\operatorname{Pr}\left\{A^{+}, A^{-} \mid X_{n}=\operatorname{Pr}\left\{A^{+} \mid X_{n} \operatorname{Pr}\left\{A^{-} \mid X_{n}\right.\right.\right.\label{5.32} \]

    Esta forma simétrica dice que, condicionada al estado actual, los estados pasados y futuros son estadísticamente independientes. Dividiendo ambos lados por\(\operatorname{Pr}\left\{A^{+} \mid X_{n}\right\}\) luego rendimientos

    \[\operatorname{Pr}\left\{A^{-} \mid X_{n}, A^{+}=\operatorname{Pr}\left\{A^{-} \mid X_{n}\right.\right.\label{5.33} \]

    Al dejar\(A^{-}\) ser\(X_{n-1}\) y\(A^{+}\) ser\(X_{n+1}, X_{n+2}, \ldots, X_{n+k}\), esto se convierte

    \(\operatorname{Pr}\left\{X_{n-1} \mid X_{n}, X_{n+1}, \ldots, X_{n+k}\right\}=\operatorname{Pr}\left\{X_{n-1} \mid X_{n}\right\}\)

    Esta es la forma equivalente a\ ref {5.29} para la cadena hacia atrás, y dice que la cadena hacia atrás es también una cadena de Markov. Por ley de Bayes,\(\operatorname{Pr}\left\{X_{n-1} \mid X_{n}\right\}\) puede ser evaluado como

    \[\operatorname{Pr}\left\{X_{n-1} \mid X_{n}\right\}=\frac{\operatorname{Pr}\left\{X_{n} \mid X_{n-1}\right\} \operatorname{Pr}\left\{X_{n-1}\right\}}{\operatorname{Pr}\left\{X_{n}\right\}}\label{5.34} \]

    Ya que la distribución de\(X_{n}\) puede variar con\(n\), también\(\operatorname{Pr}\left\{X_{n-1} \mid X_{n}\right\}\) puede depender de\(n\). Por lo tanto, la cadena atrasada de Markov no es necesariamente homogénea. Esto no debería sorprender, ya que la cadena directa se definió con alguna distribución arbitraria para el estado inicial en el tiempo 0. Esta distribución inicial no fue relevante para las ecuaciones\ ref {5.29} a (5.31), pero tan pronto como\(\operatorname{Pr}\left\{A^{-} \mid X_{n}\right\}\) se introdujo, el estado inicial se convirtió implícitamente en parte de cada ecuación y destruyó la simetría entre pasado y futuro. Para una cadena en estado estacionario, sin embargo,\(\operatorname{Pr}\left\{X_{n}=j\right\}=\operatorname{Pr}\left\{X_{n-1}=j\right\}=\pi_{j}\) para todos\(j\), y tenemos

    \[\operatorname{Pr}\left\{X_{n-1}=j \mid X_{n}=i\right\}=P_{j i} \pi_{j} / \pi_{i}\label{5.35} \]

    Así, la cadena hacia atrás es homogénea si la cadena delantera está en estado estacionario. Para una cadena con probabilidades de estado estacionario\(\left\{\pi_{i} ; i \geq 0\right\}\), definimos las probabilidades de transición hacia atrás\(P_{i j}^{*}\) como

    \[\pi_{i} P_{i j}^{*}=\pi_{j} P_{j i}\label{5.36} \]

    A partir de (5.34), la probabilidad de transición hacia atrás\(P_{i j}^{*}\), para una cadena de Markov en estado estacionario, es entonces igual a\(\operatorname{Pr}\left\{X_{n-1}=j \mid X_{n}=i\right\}\), la probabilidad de que se\(j\) le dé al estado anterior que el estado actual es\(i\).

    Ahora considere una nueva cadena de Markov con probabilidades de transición\(\left\{P_{i j}^{*}\right\}\). A lo largo de algún segmento de tiempo para el que tanto esta nueva cadena como la cadena antigua están en estado estacionario, el conjunto de estados generados por la nueva cadena es estadísticamente indistinguible de la secuencia de estados que se ejecuta hacia atrás de la cadena original. Es algo más sencillo, al hablar de cadenas que corren hacia adelante y hacia atrás, sin embargo, visualizar las cadenas de Markov corriendo en estado estacionario de\(t=-\infty\) a\(t=+\infty\). Si uno se siente incómodo con esto, también se puede visualizar iniciando la cadena de Markov en algún momento muy negativo con la distribución inicial igual a la distribución en estado estacionario.

    Definición 5.3.1

    Una cadena de Markov que tiene probabilidades de estado estacionario\(\left\{\pi_{i} ; i \geq 0\right\}\) es reversible si\(P_{i j}=\pi_{j} P_{j i} / \pi_{i}\) para todos\(i, j\), es decir, si\(P_{i j}^{*}=P_{i j}\) para todos\(i\),\(j\).

    Así, la cadena es reversible si, en estado estacionario, la secuencia de estados que se ejecuta hacia atrás es estadísticamente indistinguible de la secuencia de avance. Comparando\ ref {5.36} con las ecuaciones de estado estacionario\ ref {5.25} que derivamos para las cadenas de nacimiento-muerte, tenemos el teorema importante:

    Teorema 5.3.1

    Toda cadena de nacimiento y muerte con distribución de probabilidad en estado estacionario es reversible.

    Vimos que para las cadenas de nacimiento-muerte, la ecuación\(\pi_{i} P_{i j}=\pi_{j} P_{j i}\) (que sólo había que considerar\(|i-j| \leq 1\)) proporcionaba una manera muy sencilla de calcular las probabilidades de estado estacionario. Desafortunadamente, parece que primero debemos calcular las probabilidades de estado estacionario para mostrar que una cadena es reversible. El siguiente teorema simple nos da un escape conveniente de este dilema.

    Teorema 5.3.2

    Supongamos que una cadena irreducible de Markov tiene probabilidades de transición\(\left\{P_{i j}\right\}\). Supongamos que\(\left\{\pi_{i}\right\}\) es un conjunto de números positivos que suman a 1 y que satisfacen

    \[\pi_{i} P_{i j}=\pi_{j} P_{j i} ; \quad \text { all } i, j\label{5.37} \]

    entonces, primero,\(\left\{\pi_{i} ; i \geq 0\right\}\) es la distribución en estado estacionario para la cadena, y, segundo, la cadena es reversible.

    Prueba

    Dada una solución a\ ref {5.37} para todos\(i\) y\(j\), podemos sumar esta ecuación\(i\) para cada uno\(j\).

    \[\left.\left.\sum_{i}\right\} \pi_{i} P_{i j}=\pi_{j} \sum_{i}\right\} P_{j i}=\pi_{j}\label{5.38} \]

    Así, la solución a (5.37), junto con las restricciones\(\pi_{i}>0\),\(\sum_{i} \pi_{i}=1\), satisface las ecuaciones de estado estacionario, (5.18), y, a partir del Teorema 5.1.4, esta es la distribución única en estado estacionario. Dado que\ ref {5.37} está satisfecha, la cadena también es reversible.

    A menudo es posible, a veces mediante el uso de una suposición educada, encontrar una solución a (5.37). Si esto tiene éxito, entonces se nos asegura tanto que la cadena es reversible como que se han encontrado las probabilidades reales de estado estacionario.

    Obsérvese que el teorema se aplica tanto a las cadenas periódicas como a las cadenas aperiódicas. Si la cadena es periódica, entonces las probabilidades de estado estacionario tienen que ser interpretadas como valores promedio a lo largo del periodo, pero del Teorema 5.1.4 muestra que\ ref {5.38} todavía tiene una solución única (asumiendo una cadena irreducible). Por otro lado, para una cadena con periodo\(d>1\), existen\(d\) subclases de estados y la secuencia\(\left\{X_{n}\right\}\) debe rotar entre estas clases en un orden fijo. Para que este mismo orden se siga en la cadena atrasada, la única posibilidad es\(d=2\). Así, las cadenas periódicas con periodos distintos a 2 no pueden ser reversibles.

    Existen varias pruebas simples que se pueden utilizar para demostrar que alguna cadena irreducible dada no es reversible. Primero, las probabilidades de estado estacionario deben satisfacer\(\pi_{i}>0\) para todos\(i\), y así, si\(P_{i j}>0\) pero\(P_{j i}=0\) para algunos\(i, j\), entonces\ ref {5.37} no se puede satisfacer y la cadena no es reversible. Segundo, considerar cualquier conjunto de tres estados,\(i, j, k\). Si\(P_{j i} P_{i k} P_{k j}\) es desigual\(P_{j k} P_{k i} P_{i j}\) entonces la cadena no puede ser reversible. Para ver esto, tenga en cuenta que\ ref {5.37} requiere que

    \(\pi_{i}=\pi_{j} P_{j i} / P_{i j}=\pi_{k} P_{k i} / P_{i k}\)

    Así,\(\pi_{j} P_{j i} P_{i k}=\pi_{k} P_{k i} P_{i j}\). La ecuación\ ref {5.37} también lo requiere\(\pi_{j} P_{j k}=\pi_{k} P_{k j}\). Tomando la proporción de estas ecuaciones, vemos eso\(P_{j i} P_{i k} P_{k j}=P_{j k} P_{k i} P_{i j}\). Por lo tanto, si esta ecuación no se satisface, la cadena no puede ser reversible. En retrospectiva, este resultado no es sorprendente. Lo que dice es que para cualquier ciclo de tres estados, la probabilidad de que tres transiciones vayan alrededor del ciclo en una dirección debe ser la misma que la probabilidad de dar la vuelta al ciclo en la dirección opuesta (y por lo tanto hacia atrás).

    También es cierto (ver [16] para una prueba), que una condición necesaria y suciente para que una cadena sea reversible es que el producto de las probabilidades de transición alrededor de cualquier ciclo de longitud arbitraria debe ser el mismo que el producto de las probabilidades de transición que van alrededor del ciclo en la dirección opuesta. Esta no parece ser una forma ampliamente útil de demostrar reversibilidad.

    Hay otro resultado, generalizar el Teorema 5.3.2, para encontrar las probabilidades de estado estacionario de una cadena arbitraria de Markov y al mismo tiempo encontrar las probabilidades de transición de la cadena hacia atrás.

    Teorema 5.3.3

    Supongamos que una cadena irreducible de Markov tiene probabilidades de transición\(\left\{P_{i j}\right\}\). Supongamos que\(\left\{\pi_{i}\right\}\) es un conjunto de números positivos que suman a 1 y que\(\left\{P_{i j}^{*}\right\}\) es un conjunto de probabilidades de transición satisfactorias

    \[\pi_{i} P_{i j}=\pi_{j} P_{j i}^{*} ; \quad \text { all } i, j\label{5.39} \]

    Entonces\(\left\{\pi_{i}\right\}\) es la distribución en estado estacionario y\(\left\{P_{i j}^{*}\right\}\) es el conjunto de probabilidades de transición para la cadena hacia atrás.

    Prueba

    Sumando\ ref {5.39} sobre\(i\), obtenemos las ecuaciones de estado estacionario para la cadena de Markov, por lo que el hecho de que lo dado\(\left\{\pi_{i}\right\}\) satisfaga estas ecuaciones afirma que son las probabilidades de estado estacionario. La ecuación\ ref {5.39} luego afirma que\(\left\{P_{i j}^{*}\right\}\) es el conjunto de probabilidades de transición para la cadena hacia atrás.

    Las dos secciones siguientes ilustran algunas aplicaciones importantes de la reversibilidad.


    2 Mucho más ampliamente, cualquier 3 eventos, digamos\(A^{-}, X_{0}, A^{+}\) se dice que son Markov si\(\operatorname{Pr}\{A^{+} \mid X_{0} A^{-}=\operatorname{Pr}\{A^+|X_0\), y esto implica la forma más simétrica\(\operatorname{Pr}\left\{A^{-} A^{+} \mid X_{0}\right)=\operatorname{Pr}\left\{A^{-} \mid X_{0} \operatorname{Pr}\left\{A^{+} \mid X_{0}\right.\right.\).


    This page titled 5.3: Cadenas Markov Reversibles is shared under a CC BY-NC-SA 4.0 license and was authored, remixed, and/or curated by Robert Gallager (MIT OpenCourseWare) via source content that was edited to the style and standards of the LibreTexts platform.