11.4: Teorema de Límite Fundamental para Cadenas Regulares

El teorema del límite fundamental para las cadenas regulares de Markov establece que si\(\mat{P}\) es una matriz de transición regular entonces\[\lim_{n \to \infty} \mat {P}^n = \mat {W}\ ,\] donde\(\mat{W}\) es una matriz con cada fila igual al vector de fila de probabilidad fija única\(\mat{w}\) para\(\mat{P}\). En esta sección daremos dos pruebas muy distintas de este teorema.

Nuestra primera prueba se lleva a cabo mostrando que, para cualquier vector de columna\(\mat{y}\),\(\mat{P}^n \mat {y}\) tiende a un vector constante. Como se indica en la Sección 1.3, ésta mostrará que\(\mat{P}^n\) converge a una matriz con columnas constantes o, de manera equivalente, a una matriz con todas las filas iguales.

El siguiente lema dice que si una matriz de\(r\) transición\(r\) -by- no tiene entradas cero, y\(\mat {y}\) es cualquier vector de columna con\(r\) entradas, entonces el vector\(\mat {P}\mat{y}\) tiene entradas que están “más juntas” de lo que están las entradas\(\mat {y}\).

Let\(\mat{P}\) Ser una matriz de\(r\) transición\(r\) -by- sin entradas cero. Dejar\(d\) ser la entrada más pequeña de la matriz. Let\(\mat{y}\) Ser un vector de columna con\(r\) componentes, el más grande de los cuales es\(M_0\) y el más pequeño\(m_0\). Let\(M_1\) y\(m_1\) ser el componente más grande y más pequeño, respectivamente, del vector\(\mat {P} \mat {y}\). Entonces\[M_1 - m_1 \leq (1 - 2d)(M_0 - m_0)\ .\]

En la discusión siguiente Teorema [thm 11.3.6], se observó que cada entrada en el vector\(\mat {P}\mat{y}\) es un promedio ponderado de las entradas en\(\mat {y}\). El promedio ponderado más grande que podría obtenerse en el presente caso ocurriría si todas menos una de las entradas de\(\mat {y}\) tienen valor\(M_0\) y una entrada tiene valor\(m_0\), y esta una entrada pequeña se pondera por el menor peso posible, a saber\(d\). En este caso, el promedio ponderado sería igual\[dm_0 + (1-d)M_0\ .\] De manera similar, el promedio ponderado más pequeño posible es igual\[dM_0 + (1-d)m_0\ .\] Así,\[\begin{aligned} M_1 - m_1 &\le& \Bigl(dm_0 + (1-d)M_0\Bigr) - \Bigl(dM_0 + (1-d)m_0\Bigr) \\ &=& (1 - 2d)(M_0 - m_0)\ .\end{aligned}\] Esto completa la prueba del lema.

Pasamos ahora a la prueba del teorema del límite fundamental para las cadenas regulares de Markov.

(Teorema de Límite Fundamental para Cadenas Regulares) Si\(\mat{P}\) es la matriz de transición para una cadena regular de Markov, entonces\[\lim_{n \to \infty} \mat {P}^n = \mat {W}\ ,\] donde\(\mat {W}\) es la matriz con todas las filas iguales. Además, todas las entradas en\(\mat{W}\) son estrictamente positivas.

Demostramos este teorema para el caso especial que no\(\mat{P}\) tiene 0 entradas. La extensión al caso general se indica en Ejercicio [exer 11.4.6]. Dejar ser cualquier vector de columna\(r\) -componente, donde\(r\) está el número de estados de la cadena. Suponemos que\(r > 1\), ya que de lo contrario el teorema es trivial. Dejar\(M_n\) y\(m_n\) ser, respectivamente, los componentes máximo y mínimo del vector\(\mat {P}^n \mat { y}\). El vector\(\mat {P}^n \mat {y}\) se obtiene del vector\(\mat {P}^{n - 1} \mat {y}\) multiplicando a la izquierda por la matriz\(\mat{P}\). De ahí que cada componente de\(\mat {P}^n \mat {y}\) sea un promedio de los componentes de\(\mat {P}^{n - 1} \mat {y}\). Así\[M_0 \geq M_1 \geq M_2 \geq\cdots\] y\[m_0 \leq m_1 \leq m_2 \leq\cdots\ .\] Cada secuencia es monótona y acotada:\[m_0 \leq m_n \leq M_n \leq M_0\ .\] De ahí que cada una de estas secuencias tendrá un límite como\(n\) tiende al infinito.

\(M\)Sea el límite de\(M_n\) y\(m\) el límite de\(m_n\). Eso lo sabemos\(m \leq M\). Eso lo demostraremos\(M - m = 0\). Este será el caso si\(M_n - m_n\) tiende a 0. Dejar\(d\) ser el elemento más pequeño de\(\mat{P}\). Ya que todas las entradas de\(\mat{P}\) son estrictamente positivas, tenemos\(d > 0\). Por nuestro lema\[M_n - m_n \leq (1 - 2d)(M_{n - 1} - m_{n - 1})\ .\] De esto vemos que\[M_n - m_n \leq (1 - 2d)^n(M_0 - m_0)\ .\] Desde\(r \ge 2\), debemos tener\(d \leq 1/2\), entonces\(0 \leq 1 - 2d < 1\), así la diferencia\(M_n - m_n\) tiende a 0 como\(n\) tiende al infinito. Dado que cada componente de\(\mat {P}^n \mat {y}\) se encuentra entre\(m_n\) y\(M_n\), cada componente debe acercarse al mismo número\(u = M = m\). Esto muestra que\[\lim_{n \to \infty} \mat {P}^n \mat {y} = \mat{u}\ , \label{eq 11.4.4}\] donde\(\mat{u}\) es un vector de columna todos cuyos componentes son iguales\(u\).

Ahora deja\(\mat{y}\) ser el vector con\(j\) th componente igual a 1 y todos los demás componentes iguales a 0. Entonces\(\mat {P}^n \mat {y}\) es la columna\(j\) th de\(\mat {P}^n\). Hacer esto para cada uno\(j\) demuestra que las columnas de\(\mat {P}^n\) aproximación a vectores de columna constante. Es decir, las filas de\(\mat {P}^n\) acercarse a un vector de fila común\(\mat{w}\), o,\[\lim_{n \to \infty} \mat {P}^n = \mat {W}\ . \label{eq 11.4.5}\]

Queda por demostrar que todas las entradas en\(\mat{W}\) son estrictamente positivas. Como antes, deja\(\mat{y}\) ser el vector con\(j\) th componente igual a 1 y todos los demás componentes iguales a 0. Entonces\(\mat{P}\mat{y}\) es la columna\(j\) th de\(\mat{P}\), y esta columna tiene todas las entradas estrictamente positivas. El componente mínimo del vector\(\mat{P}\mat{y}\) se definió para ser\(m_1\), de ahí\(m_1 > 0\). Ya que\(m_1 \le m\), tenemos\(m > 0\). Tenga en cuenta finalmente que este valor de\(m\) es solo el\(j\) th componente de\(\mat{w}\), por lo que todos los componentes de\(\mat{w}\) son estrictamente positivos.

Prueba de Doeblin

Damos ahora una prueba muy diferente de la parte principal del teorema del límite fundamental para las cadenas regulares de Markov. Esta prueba fue dada por primera vez por Doeblin, ¹⁷ un brillante joven matemático que fue asesinado a los veinte años en la Segunda Guerra Mundial.

[thm 11.4.1] Dejar\(\mat {P}\) ser la matriz de transición para una cadena regular de Markov con vector fijo\(\mat {w}\). Luego, para cualquier vector de probabilidad inicial\(\mat {u}\),\(\mat {uP}^n \rightarrow \mat {w}\) como\(n \rightarrow \infty.\)

Let\(X_0,\ X_1,\ \ldots\) Ser una cadena de Markov con matriz de transición\(\mat {P}\) iniciada en estado\(s_i\). Dejar\(Y_0,\ Y_1,\ \ldots\) ser una cadena de Markov con probabilidad de transición\(\mat {P}\) iniciada con probabilidades iniciales dadas por\(\mat {w}\). Los\(Y\) procesos\(X\) y se ejecutan independientemente unos de otros.

Consideramos también una tercera cadena de Markov\(\mat{P}^*\) que consiste en observar tanto\(X\) los\(Y\) procesos como. Los estados para\(\mat{P}^*\) son pares\((s_i, s_j)\). Las probabilidades de transición las dan\[\mat{P}^{*}[(i,j),(k,l)] = \mat{P}(i,k) \cdot \mat{P}(j,l)\ .\] Dado que\(\mat{P}\) es regular hay\(N\) tal que\(\mat{P}^{N}(i,j) > 0\) para todos\(i\) y\(j\). Así para la\(\mat{P}^*\) cadena también es posible pasar de cualquier estado\((s_i, s_j)\) a cualquier otro estado\((s_k,s_l)\) en la mayoría de los\(N\) pasos. Eso\(\mat{P}^*\) es también una cadena regular de Markov.

Sabemos que una cadena regular de Markov llegará a cualquier estado en un tiempo finito. \(T\)Sea la primera vez que la cadena\(\mat{P}^*\) se encuentre en un estado de la forma\((s_k,s_k)\). En otras palabras,\(T\) es la primera vez que el\(X\) y los\(Y\) procesos están en el mismo estado. Entonces hemos demostrado que\[P[T > n] \rightarrow 0 \;\;\mbox{as}\;\; n \rightarrow \infty\ .\] si observamos\(Y\) los procesos\(X\) y después de la primera vez que están en el mismo estado no predeciríamos ninguna diferencia en su comportamiento a largo plazo. Dado que esto sucederá sin importar cómo iniciamos estos dos procesos, parece claro que el comportamiento a largo plazo no debe depender del estado inicial. Ahora demostramos que esto es cierto.

Primero notamos que si\(n \ge T\), entonces desde\(X\) y\(Y\) están ambos en el mismo estado a la vez\(T\),\[P(X_n = j\ |\ n \ge T) = P(Y_n = j\ |\ n \ge T)\ .\] Si multiplicamos ambos lados de esta ecuación por\(P(n \ge T)\),\[P(X_n = j,\ n \ge T) = P(Y_n = j,\ n \ge T)\ . \label{eq 11.4.1}\] obtenemos Sabemos que para todos\(n\),\[P(Y_n = j) = w_j\ .\] Pero\[P(Y_n = j) = P(Y_n = j,\ n \ge T) + P(Y_n = j,\ n < T)\ ,\] y la segunda suma a la derecha- lado mano de esta ecuación va a 0 como\(n\) va a\(\infty\), ya que\(P(n < T)\) va a 0 como\(n\) va a\(\infty\). Entonces,\[P(Y_n = j,\ n \ge T) \rightarrow w_j\ ,\] como\(n\) va a\(\infty\). De la Ecuación [eq 11.4.1], vemos que\[P(X_n = j,\ n \ge T) \rightarrow w_j\ ,\] como\(n\) va a\(\infty\). Pero por razonamiento similar al utilizado anteriormente, la diferencia entre esta última expresión y\(P(X_n = j)\) va a 0 como\(n\) va a\(\infty\). Por lo tanto,\[P(X_n = j) \rightarrow w_j\ ,\] como\(n\) va a\(\infty\). Esto completa la prueba.

En la prueba anterior, no hemos dicho nada sobre la tasa a la que las distribuciones de los\(X_n\)'s se acercan a la distribución fija\(\mat {w}\). De hecho, se puede demostrar que ¹⁸\[\sum ^{r}_{j = 1} \mid P(X_{n} = j) - w_j \mid \leq 2 P(T > n)\ .\] El lado izquierdo de esta desigualdad puede verse como la distancia entre la distribución de la cadena de Markov después de\(n\) escalones, comenzando en estado\(s_i\), y la distribución limitante\(\mat {w}\).

i [exer 11.4.1] Definir\(\mat{P}\) y\(\mat{y}\) por\[\mat {P} = \pmatrix{ .5 & .5 \cr.25 & .75 }, \qquad \mat {y} = \pmatrix{ 1 \cr 0 }\ .\] Computación\(\mat {P}\mat{y}\)\(\mat {P}^2 \mat {y}\), y\(\mat {P}^4 \mat {y}\) y mostrar que los resultados se acercan a un vector constante. ¿Qué es este vector?

i [exer 11.4.2] Dejar\(\mat{P}\) ser una matriz de\(r \times r\) transición regular y\(\mat{y}\) cualquier vector de columna\(r\) -componente. Mostrar que el valor del vector constante limitante para\(\mat {P}^n \mat {y}\) es\(\mat{w}\mat{y}\).

i [exer 11.4.3] Dejar\[\mat {P} = \pmatrix{ 1 & 0 & 0 \cr .25 & 0 & .75 \cr 0 & 0 & 1 }\] ser una matriz de transición de una cadena de Markov. Encuentra dos vectores fijos de los\(\mat {P}\) que son linealmente independientes. ¿Esto demuestra que la cadena Markov no es regular?

i [exer 11.4.4] Describe el conjunto de todos los vectores de columna fijos para la cadena dada en Ejercicio [exer 11.4.3].

i [exer 11.4.6] El teorema que\(\mat {P}^n \to \mat {W}\) se probó sólo para el caso que no\(\mat{P}\) tiene entradas cero. Rellena los datos de la siguiente extensión al caso que\(\mat{P}\) sea regular. Ya que\(\mat{P}\) es regular, para algunos no\(N, \mat {P}^N\) tiene ceros. Así, la prueba dada muestra que se\(M_{nN} - m_{nN}\) acerca a 0 como\(n\) tiende al infinito. Sin embargo, la diferencia nunca\(M_n - m_n\) puede aumentar. (¿Por qué?) De ahí que si sabemos que las diferencias obtenidas al mirar cada vez\(N\) th tienden a 0, entonces toda la secuencia también debe tender a 0.

i [exer 11.4.7] Dejar\(\mat{P}\) ser una matriz de transición regular y dejar\(\mat{w}\) ser el único vector fijo distinto de cero de\(\mat{P}\). Demostrar que ninguna entrada de\(\mat{w}\) es 0.

i [exer 11.4.8] Aquí tienes un truco para probar con tus amigos. Baraja una baraja de cartas y reparte una a la vez. Cuente las cartas de cara cada una como diez. Pídele a tu amiga que mire una de las primeras diez cartas; si esta carta es un seis, ella es para mirar la carta que aparece seis cartas más tarde; si esta carta es un tres, es para mirar la carta que aparece tres cartas después, y así sucesivamente. Eventualmente llegará a un punto en el que está para mirar una carta que luego aparece\(x\) cartas pero no quedan\(x\) cartas. Entonces le dices la última carta que miró a pesar de que no conocías su punto de partida. Le dices que haces esto viéndola, y no puede disfrazar las veces que mira las cartas. De hecho simplemente haces el mismo procedimiento y, aunque no comiences en el mismo punto que ella, lo más probable es que termines en el mismo punto. ¿Por qué?

i [exer 11.4.9] Escribe un programa para jugar el juego en Ejercicio [exer 11.4.8].

i [exer 11.4.10] (Sugerido por Peter Doyle) En la prueba del Teorema [thm 11.4.1], asumimos la existencia de un vector fijo\(\mat{w}\). Para evitar esta suposición, refuerce el argumento de acoplamiento para mostrar (sin asumir la existencia de una distribución estacionaria\(\mat{w}\)) que para constantes apropiadas\(C\) y\(r<1\), la distancia entre\(\alpha P^n\) y\(\beta P^n\) es como máximo\(C r^n\) para cualquier distribución inicial\(\alpha\) y \(\beta\).Aplique esto en el caso donde\(\beta = \alpha P\) concluya que la secuencia\(\alpha P^n\) es una secuencia de Cauchy, y que su límite es una matriz\(W\) cuyas filas son todas iguales a un probabilityvector\(w\) con\(wP=w\). Tenga en cuenta que la distancia entre\(\alpha P^n\) y\(w\) es como\(C r^n\) mucho, por lo que al liberarnos de la suposición de tener un vector fijo, hemos demostrado que la convergencia al equilibrio tiene lugar exponencialmente rápido.