Saltar al contenido principal
LibreTexts Español

3.2: Clasificación de Estados

  • Page ID
    86162
  • \( \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}}\)

    Esta sección, salvo que se indique lo contrario, se aplica a las cadenas de Markov con espacios estatales tanto finitos como contables. Comenzamos con varias definiciones.

    Definición: 3.2.1

    Un paseo (n-paso) es una cadena ordenada de nodos, (i0, i1,. .in), n ≥ 1, en la que hay un arco dirigido de\(i_{m−1}\) a\(i_m\) para cada m, 1 ≤ m ≤ n. Un camino es un paseo en el que no se repiten nodos. Un ciclo es un paseo en el que los nodos primero y último son iguales y no se repite ningún otro nodo.

    Tenga en cuenta que una caminata puede comenzar y terminar en el mismo nodo, mientras que una ruta no puede. También el número de pasos en una caminata puede ser arbitrariamente grande, mientras que un camino puede tener como máximo M − 1 pasos y un ciclo como máximo M pasos para una cadena de Markov de estado finito con |S| = M.

    Definición 3.2.2

    Un estado\(j\) es accesible desde\(i\) (abreviado como\(i_j\)) si hay un paseo en la gráfica de\(i\) a\(j\).

    Por ejemplo, en la Figura 3.1 (a), hay una caminata desde el nodo 1 al nodo 3 (pasando por el nodo 2), por lo que el estado 3 es accesible desde 1. No hay paseo del nodo 5 al 3, por lo que el estado 3 no es accesible desde el 5. El Estado 2 es accesible desde sí mismo, pero el estado 6 no es accesible desde sí mismo. Para ver el significado probabilístico de la accesibilidad, supongamos que\(i_{0}, i_{1}, \ldots i_{n}\) existe un paseo de nodo\(i_{0}\) a\(i_{n}\). Entonces, condicional\(X_{0}=i_{0}\), hay una probabilidad positiva,, eso\(P_{i_{0} i_{1}}\)\(X_{1}=i_{1}\), y consecuentemente (desde\(P_{i_{1} i_{2}}>0\)), hay una probabilidad positiva de que\(X_{2}=i_{2}\). Continuando con este argumento, hay una probabilidad positiva de que\(X_{n}=i_{n}\), así que eso\(\operatorname{Pr}\left\{X_{n}=i_{n} \mid X_{0}=i_{0}\right\}>0\). Del mismo modo\(\operatorname{Pr}\left\{X_{n}=i_{n} \mid X_{0}=i_{0}\right\}>0\), si, entonces\({i}_{n}\) debe existir un\(n\) -paso\(i_{0}\) a pie de a. Resumiendo,\(i \rightarrow j\) si y solo si (iff)\(\operatorname{Pr}\left\{X_{n}=j \mid X_{0}=i\right\}>0\) para algunos\(n \geq 1\). Denotamos\(\operatorname{Pr}\left\{X_{n}=j \mid X_{0}=i\right\}\) por\(P_{i j}^{n}\). Así, por\(n \geq 1, P_{i j}^{n}>0\) si y sólo si la gráfica tiene un\(n\) paso caminando de\(i\) a\(j\) (quizás visitando el mismo nodo más de una vez). Para el ejemplo en la Figura 3.1 (a),\(P_{13}^{2}=P_{12} P_{23}>0\). Por otro lado,\(P_{53}^{n}=0\) para todos\(n \geq 1\). Una relación importante que usamos a menudo en lo que sigue es que si hay una caminata\(n\) -paso de estado\(i\) a\(j\) y una caminata de\(m\) -paso de estado\(j\) a\(k\), entonces hay una caminata de\(m + n\) pasos de\(i\) a\(k\). Así

    \[P_{i j}^{n}>0 \text { and } P_{j k}^{m}>0 \quad \text { imply } \quad P_{i k}^{n+m}>0\label{3.5} \]

    Esto también demuestra que

    \[i \rightarrow j \text { and } \mathrm{j} \rightarrow \mathrm{k} \quad\text { imply } \quad\mathrm{i} \rightarrow \mathrm{k}\label{3.6} \]

    Definición 3.2.3

    Dos estados distintos\(i\) y\(j\) comunicarse (abreviado\(i \leftrightarrow j\)) si\(i\) es accesible desde\(j\) y\(j\) es accesible desde\(i\).

    Un dato importante sobre la comunicación de estados es que si\(i \leftrightarrow j\) y\(m \leftrightarrow j\) entonces\(i \leftrightarrow m\). Para ver esto, anotar eso\(i \leftrightarrow j\) e\(m \leftrightarrow j\) implicar eso\(i \rightarrow j\) y j\(\rightarrow m\), así que eso\(i \rightarrow m\). De igual manera\(m \rightarrow i\),, entonces\(i \leftrightarrow m\).

    Definición 3.2.4

    \(A\)clase\(C\) de estados es un conjunto no vacío de estados de tal manera que cada uno\(i \in \mathcal{C}\) se comunica con cada otro estado\(j \in \mathcal{C}\) y se comunica con no\(j \notin \mathcal{C}\).

    Para el ejemplo de la Figura 3.1 (a), {2, 3} es una clase de estados, {1}, {4}, {5} y {6} son las otras clases. Tenga en cuenta que el estado 6 no se comunica con ningún otro estado, y ni siquiera es accesible desde sí mismo, pero el conjunto que consiste en {6} por sí solo sigue siendo una clase. Todo el conjunto de estados en una determinada cadena de Markov se divide en una o más clases disjuntas de esta manera.

    Definición 3.2.5

    Para las cadenas de Markov de estado finito, un estado recurrente es un estado\(i\) que es accesible desde todos los estados que son accesibles desde\(i\) (\(i\)es recurrente si\(i \rightarrow j\) implica eso\(j \rightarrow i\). Un estado transitorio es un estado que no es recurrente.

    Los estados recurrentes y transitorios para las cadenas de Markov con un espacio de estado contable-infinito se definirán en el Capítulo 5.

    Según la definición, un estado\(i\) en una cadena de Markov de estado finito es recurrente si no hay posibilidad de ir a un estado\(j\) del que no pueda haber retorno. Como veremos más adelante, si una cadena de Markov entra alguna vez en un estado recurrente, regresa a ese estado eventualmente con probabilidad 1, y así sigue regresando infinitamente a menudo (de hecho, esta propiedad sirve como definición de recurrencia para las cadenas de Markov sin la restricción de estado finito). Un estado\(i\) es transitorio si hay alguna j que es accesible desde i pero desde la cual no hay retorno posible. Cada vez que el sistema vuelve a\(i\), existe la posibilidad de ir a\(j\); eventualmente esta posibilidad ocurrirá sin más retornos a\(i\).

    Teorema 3.2.1

    Para las cadenas de Markov de estado finito, o todos los estados de una clase son transitorios o todos son recurrentes. 2

    Prueba

    Supongamos que el estado\(i\) es transitorio (es decir, para algunos\(j\),\(i \rightarrow j\) pero\(j \not \rightarrow i\)) y supongamos que\(i\) y\(m\) están en la misma clase (i.e.,\(i \leftrightarrow m\)). Entonces\(m \rightarrow i\) y\(i \rightarrow j\), entonces\(m \rightarrow j\). Ahora bien\(j \rightarrow m\), si, entonces la caminata de\(j\) a m podría extenderse a\(i\); esto es una contradicción, y por lo tanto no hay caminar de\(j\) a\(m\), y\(m\) es transitorio. Como acabamos de demostrar que todos los nodos de una clase son transitorios si los hay, se deduce que los estados en una clase son todos recurrentes o todos transitorios.

    Para el ejemplo de la Figura 3.1 (a), {2, 3} y {5} son clases recurrentes y las otras clases son transitorias. En términos de la gráfica de una cadena de Markov, una clase es transitoria si hay arcos dirigidos que van de un nodo en la clase a un nodo fuera de la clase. Toda cadena de Markov de estado finito debe tener al menos una clase recurrente de estados (ver Ejercicio 3.2), y puede tener arbitrariamente muchas clases adicionales de estados recurrentes y estados transitorios.

    Los estados también pueden clasificarse según sus periodos (ver Figura 3.2). Para\(X_{0}=2 \) en la Figura 3.2 (a),\(X_{n}\) debe ser 2 o 4 para\(n\) par y 1 o 3 para n impar. Por otro lado, si\(X_{0}\) es 1 o 3, entonces\(X_{n}\) es 2 o 4 para\(n\) impar y 1 o 3 para\(n\) par. De esta manera el efecto del estado de partida nunca se desplomará. La Figura 3.2 (b) ilustra otro ejemplo en el que la memoria del estado inicial nunca se descompone. Se dice que los estados en ambas cadenas de Markov son periódicos con el periodo 2. Otro ejemplo de estados periódicos son los estados 2 y 3 de la Figura 3.1 (a).

    Definición 3.2.6: Mayor Divisor Común

    El periodo de un estado\(i\), denotado\(d(i)\), es el mayor divisor común (gcd) de aquellos valores de\(n\) los cuales\(P_{i i}^{n}>0\). Si el periodo es 1, el estado es aperiódico, y si el periodo es 2 o más, el estado es periódico.

    Screen Shot 2021-08-27 a las 5.38.58 PM.pngFigura 3.2: Cadenas periódicas de Markov

    Por ejemplo, en la Figura 3.2 (a),\(P_{11}^{n}>0\) para\(n=2,4,6, \ldots\) Así\(d(1)\), el periodo del estado 1, es dos. De igual manera,\(d(i)=2\) para los demás estados de la Figura 3.2 (a). Para la Figura 3.2 (b), tenemos\(P_{11}^{n}>0\) para\(n=4,8,10,12, \ldots\); así\(d(1)=2\), y se puede ver que\(d(i)=2\) para todos los estados. Estos ejemplos sugieren el siguiente teorema.

    Teorema 3.2.2

    Para cualquier cadena de Markov (con un número finito o contablemente infinito de estados), todos los estados de la misma clase tienen el mismo periodo.

    Prueba

    Dejar\(i\) y\(j\) ser cualquier par distinto de estados en una clase\(\mathcal{C}\). Entonces\(i \leftrightarrow j\) y hay algunos\(r\) tales que\(P_{i j}^{r}>0\) y otros\(s\) tales que\(P_{j i}^{s}>0\). Ya que hay un paseo de longitud\(r+s\) que va de\(i\) ida\(j\) y vuelta a\(i\),\(r+s\) debe ser divisible por\(d(i)\). Dejar\(t\) ser cualquier entero tal que\(P_{j j}^{t}>0\). Ya que hay un paseo de longitud\(r+t+s\) de\(i\) a\(j\), luego de vuelta a\(j\), y luego a\(i\),\(r+t+s\) es divisible por\(d(i)\), y así\(t\) es divisible por\(d(i)\). Ya que esto es cierto para cualquier\(t\) tal que\(P_{j j}^{t}>0\),\(d(j)\) es divisible por\(d(i)\). Revertir los roles de\(i\) y\(j\),\(d(i)\) es divisible por\(d(j)\), entonces\(d(i)=d(j)\).

    Dado que los estados de una clase tienen\(\mathcal{C}\) todos el mismo periodo y son todos recurrentes o todos transitorios, nos referimos a\(\mathcal{C}\) sí mismo como teniendo el periodo de sus estados y como recurrente o transitorio. De igual manera si una cadena de Markov tiene una sola clase de estados, nos referimos a la cadena como que tiene el periodo correspondiente.

    Teorema 3.2.3

    Si una clase recurrente\(\mathcal{C}\) en una cadena de Markov de estado finito tiene punto\(d\), entonces los estados en\(\mathcal{C}\) pueden dividirse en\(d\) subconjuntos\(\mathcal{S}_{1}, \mathcal{S}_{2}, \ldots, \mathcal{S}_{d}\),, de tal manera que todas las transiciones de\(\mathcal{S}_{1}\) ir a\(\mathcal{S}_{2}\), todas de\(\mathcal{S}_{2}\) ir a\(\mathcal{S}_{3}\), y así sucesivamente hasta \(\mathcal{S}_{m-1}\)a\(\mathcal{S}_{m}\). Por último, todas las transiciones de\(\mathcal{S}_{m}\) ir a\(\mathcal{S}_{1}\).

    Prueba

    Ver Figura 3.3 para una ilustración del teorema. Para un estado dado en\(\mathcal{C}\), digamos estado 1, defina los conjuntos\(\mathcal{S}_{1}, \ldots, \mathcal{S}_{d}\) por

    \[\mathcal{S}_{m}=\left\{j: P_{1 j}^{n d+m}>0 \text { for some } n \geq 0\right\} ; \quad 1 \leq m \leq d\label{3.7} \]

    Para cada uno\(j \in \mathcal{C}\), primero demostramos que hay uno y sólo un valor de\(m\) tal que\(j \in \mathcal{S}_{m}\). Ya que\(1 \leftrightarrow j\), hay algunos\(r\) para los cuales\(P_{1 j}^{r}>0\) y otros\(s\) para los cuales\(P_{j 1}^{s}>0\). Así hay un paseo de 1 a 1 (a través\(j\)) de longitud\(r+s\), así\(r+s\) es divisible por\(d\). Para lo dado\(r\), let\(m\),\(1 \leq m \leq d\), satisfy\(r=m+n d\), donde\(n\) es un entero. De (3.7),\(j \in \mathcal{S}_{m}\). Ahora vamos a\(r^{\prime}\) ser cualquier otro entero tal que\(P_{1 j}^{r^{\prime}}>0\). Entonces también\(r^{\prime}+s\) es divisible por\(d\), así que eso\(r^{\prime}-r\) es divisible por\(d\). Así\(r^{\prime}=m+n^{\prime} d\) para algún entero\(n^{\prime}\) y ese mismo\(m\). Dado que\(r^{\prime}\) es cualquier entero tal que\(P_{1 j}^{r^{\prime}}>0, j\) está en\(\mathcal{S}_{m}\) para sólo ese valor de\(m\). Dado que\(j\) es arbitrario, esto demuestra que los conjuntos\(\mathcal{S}_{m}\) son disjuntos y partición\(\mathcal{C}\).

    Por último, supongamos\(j \in \mathcal{S}_{m}\) y\(P_{j k}>0\). Dado un paseo de longitud\(r=n d+m\) desde el estado 1 hasta\(j\), hay un paseo de longitud\(n d+m+1\) desde el estado 1 hasta\(k\). De ello se deduce que si\(m<d\), entonces\(k \in \mathcal{S}_{m+1}\) y si\(m=d\), entonces\(k \in \mathcal{S}_{1}\), completando la prueba.

    Screen Shot 2021-08-27 a las 9.47.49 PM.png
    Figura 3.3: Estructura de una cadena periódica de Markov con\(d=3\). Tenga en cuenta que las transiciones solo van de un subconjunto\(\mathcal{S}_{m}\) al siguiente subconjunto\(\mathcal{S}_{m+1}\) (o de\(\mathcal{S}_{d}\) a\(\mathcal{S}_{1}\)).

    Hemos visto que cada clase de estados (para una cadena de estados finitos) puede clasificarse tanto en términos de su periodo como en términos de si es recurrente o no. El caso más importante es aquel en el que una clase es tanto recurrente como aperiódica.

    Definición 3.2.7

    Para una cadena de Markov de estado finito, una clase ergódica de estados es una clase que es a la vez recurrente y aperiódica 3. Una cadena de Markov que consta completamente de una clase ergódica se llama cadena ergódica.

    Veremos más adelante que estas cadenas tienen la propiedad deseable que\(P_{i j}^{n}\) se vuelve independiente del estado de partida\(i\) como\(n \rightarrow \infty\). El siguiente teorema establece la primera parte de esto al mostrar que\(P_{i j}^{n}>0\) para todos\(i\) y\(j\) cuando\(n\) es suficientemente grande. Se da una prueba guiada en el Ejercicio 3.5.

    Teorema 3.2.4

    Por un\(M\) estado ergódico cadena de Markov,\(P_{i j}^{m}>0\) para todos\(i\),\(j\), y para todos\(m \geq (M-1)^2+1\).

    Prueba

    La figura 3.4 ilustra una situación en la que el encuadernado\((\mathrm{M}-1)^{2}+1\) se cumple con igualdad. Tenga en cuenta que hay un ciclo de longitud\(\mathrm{M}-1\) y el nodo único que no está en este ciclo, el nodo 1, es el nodo de inicio único en el que el límite se encuentra con igualdad.

    Screen Shot 2021-08-27 a las 10.08.20 PM.png
    Figura 3.4: Una cadena ergódica con\(\mathrm{M}=6\) estados en los que\(P_{i j}^{m}>0\) para todos\(m>(\mathrm{M}-1)^{2}\) y para todos\(i\),\(j\) pero\(P_{11}^{(\mathrm{M}-1)^{2}}=0\) La figura también ilustra que una cadena de Markov de estado M debe tener un ciclo con M − 1 o menos nodos. Para ver esto, tenga en cuenta que una cadena ergódica debe tener ciclos, ya que cada nodo debe tener un paseo hacia sí mismo, y los subciclos de nodos repetidos pueden omitirse de ese paseo, convirtiéndolo en un ciclo. Tal ciclo podría tener M nodos, pero una cadena con solo un ciclo de M nodos sería periódica. Así, algunos nodos deben estar en ciclos más pequeños, como el ciclo de longitud 5 en la figura.

    Referencia

    2 Como se muestra en el Capítulo 5, este teorema también es cierto para las cadenas de Markov con un espacio estatal contablemente infinito, pero la prueba que aquí se da es inadecuada. También las clases recurrentes con un espacio de estado contablemente infinito se clasifican además en positivo-recurrente o nulo recurrente, distinción que no aparece en el caso de estado finito.

    3 Para las cadenas de Markov con un espacio estatal contablemente infinito, ergódica significa que los estados son positivosurrentes y aperiódicos (ver Capítulo 5, Sección 5.1).


    This page titled 3.2: Clasificación de Estados 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; a detailed edit history is available upon request.