3.4: Los valores propios y los vectores propios de las matrices estocásticas
- Page ID
- 86175
Para las unichaínas ergódicas, la sección anterior mostró que la dependencia de un estado del pasado distante desaparece con el aumento\(n, \text { i.e., } P_{i j}^{n} \rightarrow \pi_{j}\). En esta sección analizamos con más atención los valores propios y vectores propios de\([P]\) para agudizar nuestra comprensión de qué tan rápido\(\left[P^{n}\right]\) converge para las unichaínas ergódicas y lo que sucede con otras cadenas de Markov de estado finito.
El vector fila 6\(\boldsymbol{\pi}\) es un vector propio izquierdo de\([P]\) de valor propio\(\lambda\) si\(\boldsymbol{\pi \neq 0}\) y\(\boldsymbol{\pi[P]}=\boldsymbol{\lambda \pi}\), es decir,\(\sum_{i} \pi_{i} P_{i j}=\lambda \pi_{j}\) para todos\(\text { j }\). El vector de columna\(\boldsymbol{\nu}\) es un vector propio derecho de valor propio\(\lambda\) si\(\boldsymbol{\nu \neq 0}\) y\(\boldsymbol{[P] \nu}=\boldsymbol{\lambda \nu}\), es decir,\(\sum_{j} P_{i j} \nu_{j}=\lambda \nu_{i}\) para todos\(i\).
Demostramos que una matriz estocástica siempre tiene un valor propio\(\lambda=1\), y que para una unicadena ergódica, existe un vector de estado estacionario único\(\boldsymbol{\pi}\) que es un vector propio izquierdo con\(\lambda=1\) y (dentro de un factor de escala) un vector propio derecho único\(\boldsymbol{e}=(1, \ldots, 1)^{\top}\). En esta sección observamos los otros valores propios y vectores propios y también observamos las cadenas de Markov distintas de las unichainas ergódicas. Comenzamos limitando el número de estados a M = 2. Esto proporciona una visión sin requerir mucho álgebra lineal. Después de eso, se analiza el caso general con arbitrarios\(\mathrm{M}<\infty\).
Valores propios y vectores propios para M = 2 estados
Los valores propios y vectores propios se pueden encontrar por álgebra elemental (pero ligeramente tediosa). Las ecuaciones de vector propio izquierdo y derecho pueden escribirse como
\ [{\ begin {alineado}
&\ pi_ {1} P_ {11} +\ pi_ {2} P_ {21} =\ lambda\ pi_ {1}\
&\ pi_ {1} P_ {12} +\ pi_ {2} P_ {22} =\ lambda\ pi_ {2}
\ end {alineado}}\ quad (\ texto {izquierda})\ quad\ quad\ quad {\ begin {alineado}
P_ {11}\ nu_ {1} +P_ {12}\ nu_ {2} &=\ lambda\ nu_ {1}\\
P_ {21}\ nu_ {1} +P_ {22}\ nu_ {2} &=\ lambda\ nu_ {2}
\ end {alineado}}\ quad\ texto {derecha}\ etiqueta {3.27}\]
Cada conjunto de ecuaciones tiene una solución distinta de cero si y solo si la matriz\([P-\lambda I]\), donde\([I]\) está la matriz de identidad, es singular (es decir, debe haber un distinto de cero\(\boldsymbol{\nu}\) para el cual\([P-\lambda I] \boldsymbol{\nu}=\boldsymbol{0})\). Así\(\lambda\) debe ser tal que el determinante de\([P-\lambda I]\), es decir\(\left(P_{11}-\lambda\right)\left(P_{22}-\lambda\right)-P_{12} P_{21}\), sea igual a 0. Resolviendo esta ecuación cuadrática en\(\lambda\), encontramos que\(\lambda\) tiene dos soluciones,
\(\lambda_{1}=1 \quad\quad \lambda_{2}=1-P_{12}-P_{21}\)
Suponiendo inicialmente que\(P_{12}\) y no\(P_{21}\) son ambos 0, la solución para los vectores propios izquierdo y derecho,\(\boldsymbol{\pi}^{(1)}\) y\(\boldsymbol{\nu}^{(1)}\), de\(\lambda_{1}\) y\(\boldsymbol{\pi}^{(2)}\) y\(\boldsymbol{\nu}^{(2)}\) de\(\lambda_{2}\), están dadas por
\ (\ begin {alineado}
\ pi_ {1} ^ {(1)} &=\ frac {P_ {21}} {P_ {12} +P_ {21}} &\ pi_ {2} ^ {(1)} &=\ frac {P_ {12}} {P_ {12} +P_ {21}} &\ nu_ {1} ^ {(1)} &= 1 &\ nu_ {2} ^ {(1)} &=\ quad 1\
\ pi_ {1} ^ {(2)} &= 1\ quad&\ pi_ {2} ^ {(2)} &=-1\ quad &\ nu_ {1} ^ {(2)} &=\ frac {P_ {12}} { P_ {12} +P_ {21}}\ quad &\ nu_ {2} ^ {(2)} &=\ frac {-P_ {21}} {P_ {12} +P_ {21}}
\ final {alineado}\)
Estas soluciones contienen factores de normalización arbitrarios. Eso para se\(\boldsymbol{\pi}^{(1)}=\left(\pi_{1}^{(1)}, \pi_{2}^{(1)}\right)\) ha elegido de manera que\(\boldsymbol{\pi}^{(1)}\) sea un vector de estado estacionario (es decir, los componentes suman a 1). Las soluciones también se han normalizado para que\(\boldsymbol{\pi}_{i} \boldsymbol{\nu}_{i}=1\) para\(i=1,2\). Ahora define
\ ([\ Lambda] =\ left [\ begin {array} {cc}
\ lambda_ {1} &
0\\ 0 &\ lambda_ {2}
\ end {array}\ right]\ quad\ text {y}\ quad [U] =\ left [\ begin {array} {cc}
\ nu_ {1} ^ {(1)} &\ nu_ {1} ^ {(2)}\\
\ nu_ {2} ^ {(1)} &\ nu_ {2} ^ {(2)}
\ fin {matriz}\ derecha]\)
es decir,\([U]\) es una matriz cuyas columnas son los vectores propios\(\boldsymbol{\nu}^{(1)}\) y\(\boldsymbol{\nu}^{(2)}\). Entonces las dos ecuaciones de vector propio derecho en\ ref {3.27} se pueden combinar de forma compacta como\([P][U]=[U][\Lambda]\). Resulta (para la normalización dada de los vectores propios) que la inversa de\([U]\) es solo la matriz cuyas filas son los vectores propios izquierdos de\([P]\) (esto se puede verificar señalando eso\(\boldsymbol{\pi}_{1} \boldsymbol{\nu}_{2}=\boldsymbol{\pi}_{2} \boldsymbol{\nu}_{1}=0\). Entonces vemos eso\([P]=[U][\Lambda][U]^{-1}\) y consecuentemente\(\left[P^{n}\right]=[U][\Lambda]^{n}[U]^{-1}\). Multiplicando esto, obtenemos
\ [\ left [P^ {n}\ right] =\ left [\ begin {array} {ll}
\ pi_ {1} +\ pi_ {2}\ lambda_ {2} ^ {n} &\ pi_ {2} -\ pi_ {2}\ lambda_ {2} ^ {n}\
\ pi_ {1} -\ pi_ {1}\ lambda_ {2} ^ {n} &\ pi_ {2} +\ pi_ {1}\ lambda_ {2} ^ {n}
\ end {array}\ derecha]\ label {3.28}\]
donde\(\boldsymbol{\pi}=\left(\pi_{1}, \pi_{2}\right)\) está el vector de estado estacionario\(\boldsymbol{\pi}^{(1)}\). Al\(\lambda_{2}=1-P_{12}-P_{21}\) recordarlo, vemos eso\(\left|\lambda_{2}\right| \leq 1\). Hay 2 casos triviales donde\(\left|\lambda_{2}\right|=1\). En la primera,\(P_{12}=P_{21}=0\), así que esa\([P]\) es sólo la matriz de identidad. La cadena Markov tiene entonces 2 estados recurrentes y se queda para siempre donde empieza. En el otro caso trivial,\(P_{12}=P_{21}=1\). \(\lambda_{2}=-1\)Entonces así eso\(\left[P^{n}\right]\) alterna entre la matriz de identidad para\(n\) par y\([P]\) para\(n\) impar. En todos los demás casos,\(\left|\lambda_{2}\right|<1\) y\(\left[P^{n}\right]\) se aproxima a la matriz de estado estacionario\(\lim _{n \rightarrow \infty}\left[P^{n}\right]=\boldsymbol{e} \boldsymbol{\pi}\).
Lo que hemos aprendido de esto es la manera exacta en que se\(\left[P^{n}\right]\) aproxima\(\boldsymbol{e \pi}\). Cada término en\(\left[P^{n}\right]\) se acerca al valor de estado estacionario exponencialmente en\(n\) as\(\lambda_{2}^{n}\). Así, en lugar del límite superior en (3.21), tenemos una expresión exacta, que en este caso es más simple que el encuadernado. Como vemos en breve, este resultado es representativo del caso general, pero se pierde la simplicidad.
Valores propios y vectores propios para M > 2 estados
Para el caso general de una matriz estocástica, comenzamos con el hecho de que el conjunto de valores propios viene dado por el conjunto de valores (posiblemente complejos) de\(\lambda\) que satisfacen la ecuación determinante\(\operatorname{det}[P-\lambda I]=0\). Dado que\(\operatorname{det}[P-\lambda I]\) es un polinomio de grado M en\(\lambda\), esta ecuación tiene M raíces (es decir, M valores propios), no todos los cuales necesitan ser distintos. 7
Caso con M valores propios distintos: Comenzamos con el caso más simple en el que los M valores propios, digamos\(\lambda_{1}, \ldots, \lambda_{\mathrm{M}}\), son todos distintos. La matriz\(\left[P-\lambda_{i} I\right]\) es singular para cada uno\(i\), por lo que debe haber un vector propio derecho\(\boldsymbol{\nu}^{(i)}\) y un vector propio izquierdo\(\boldsymbol{\pi}^{(i)}\) para cada autovalor\(\lambda_{i}\). Los vectores propios derechos abarcan el espacio dimensional M y, por lo tanto, la matriz\(U\) con columnas\(\left(\boldsymbol{\nu}^{(1)}, \ldots, \boldsymbol{\nu}^{(\mathrm{M})}\right)\) es no singular. Los vectores propios izquierdos, si se normalizan\(\boldsymbol{\pi}^{(i)} \boldsymbol{\nu}^{(i)}=1\) para satisfacer para cada uno\(i\), entonces resultan ser las filas de\(\left[U^{-1}\right]\) (ver Ejercicio 3.11). Como en el caso de los dos estados, entonces podemos expresarnos\(\left[P^{n}\right]\) como
\[\left[P^{n}\right]=\left[U^{-1}\right)\left[\Lambda^{n}\right][U]\label{3.29} \]
donde\(\Lambda\) está la matriz diagonal con términos\(\lambda_{1}, \ldots, \lambda_{\mathrm{M}}\).
Si\(\Lambda\) se divide en la suma de M matrices diagonales, 8 cada una con un solo elemento distinto de cero, entonces (ver Ejercicio 3.11) se\(\left[P^{n}\right]\) puede expresar como
\[\left[P^{n}\right]=\sum_{i=1}^{M} \lambda_{i}^{n} \boldsymbol{\nu}^{(i)} \boldsymbol{\pi}^{(i)}\label{3.30} \]
Tenga en cuenta que esta es la misma forma que (3.28), donde en (3.28), el valor propio\(\lambda_{1}=1\) simplemente aparece como el valor 1. Hemos visto que siempre hay un valor propio que es 1, con un vector de estado estacionario adjunto\(\boldsymbol{\pi}\) como vector propio izquierdo y el vector unitario\(\boldsymbol{e}=(1, \ldots, 1)^\boldsymbol{\top}\) como vector propio derecho. Los otros valores propios y vectores propios pueden ser complejos, pero es casi evidente por el hecho de que\(\left[P^{n}\right]\) es una matriz estocástica que\(\left|\lambda_{i}\right| \leq 1\). Una simple prueba guiada de ello se da en el Ejercicio 3.12.
Eso lo hemos visto\(\lim _{n \rightarrow \infty}\left[P^{n}\right]=\boldsymbol{e} \boldsymbol{\pi}\) para las unichaínas ergódicas. Esto implica que todos los términos excepto\(i=1\) en\ ref {3.30} se extinguen con\(n\), lo que implica además que\(\left|\lambda_{i}\right|<1\) para todos los valores propios excepto\(\lambda=1\). En este caso, vemos que la velocidad a la que se\(\left[P^{n}\right]\) aproxima al estado estacionario viene dada por el segundo valor propio más grande en magnitud, es decir,\(\max _{i:\left|\lambda_{i}\right|<1}\left|\lambda_{i}\right|\).
Si una cadena recurrente es periódica con punto\(d\), resulta que hay\(d\) valores propios de magnitud 1, y estos están uniformemente espaciados alrededor del círculo unitario en el plano complejo. El ejercicio 3.19 contiene una prueba guiada de ello.
Caso con valores propios repetidos y M vectores propios linealmente independientes: Si algunos de los M autovalores de no\([P]\) son distintos, surge la pregunta de cuántos vectores propios linealmente independientes existen para un valor propio\(\lambda_{i}\) de multiplicidad m, es decir, a\(\lambda_{i}\) que es una raíz de orden m de\(\operatorname{det}[P-\lambda I]\). Quizás la parte más fea del álgebra lineal es el hecho de que un valor propio de multiplicidad m no necesita tener m vectores propios linealmente independientes.
Un ejemplo de una cadena de Markov muy simple con M = 3 pero solo dos autovectores linealmente independientes se da en el Ejercicio 3.14. Estos vectores propios no abarcan el espacio M y, por lo tanto, no se puede usar la expansión en\ ref {3.30}.
Antes de mirar este feo caso, miramos el caso en el que los vectores propios correctos, digamos, abarcan el espacio, es decir, donde cada valor propio distinto tiene un número de vectores propios linealmente independientes igual a su multiplicidad. Podemos volver a formar una matriz\([U]\) cuyas columnas son los M vectores propios derechos linealmente independientes, y nuevamente\(\left[U^{-1}\right]\) es una matriz cuyas filas son los vectores propios izquierdos correspondientes de\([P]\). Entonces obtenemos\ ref {3.30} otra vez. Así, siempre que los vectores propios abarquen el espacio, la expresión asintótica para las probabilidades de transición limitantes se puede encontrar de la misma manera.
La situación más importante en la que estos valores propios repetidos marcan una diferencia importante es para las cadenas de Markov con clases\(\kappa>1\) recurrentes. En este caso,\(k\) es la multiplicidad del valor propio 1. Es fácil ver que existen\(\kappa\) diferentes vectores de estado estacionario. El vector de estado estacionario para la clase recurrente\(\ell, 1 \leq \ell \leq \kappa\), es estrictamente positivo para cada estado de la `ésima clase recurrente y es cero para todos los demás estados.
Los valores propios para\([P]\) en este caso se pueden encontrar encontrando los valores propios por separado para cada clase recurrente. Si la clase\(j\) contiene\(r_{j}\) estados, entonces\(r_{j}\) de los valores propios (contando repeticiones) de\([P]\) son los valores propios de la\(r_{j}\) matriz\({r}_{j}\) by para los estados en esa clase recurrente. Así, la tasa de convergencia\(\left[P^{n}\right]\) dentro de esa submatriz está determinada por el segundo valor propio más grande (en magnitud) en esa clase.
Lo que esto significa es que esta teoría general que utiliza valores propios dice exactamente lo que dice el sentido común: si hay\(k\). clases recurrentes, miren cada una por separado, ya que no tienen nada que ver entre sí. Esto también nos permite ver que para cualquier clase recurrente que sea aperiódica, todos los demás valores propios para esa clase son estrictamente menores que 1 en magnitud.
La situación es menos obvia si hay clases\(k\) recurrentes más un conjunto de estados\(t\) transitorios. Todos menos\(t\) los valores propios (contando repeticiones) están asociados con las clases recurrentes, y los\(t\) valores propios restantes son los valores propios de la\(t\) matriz\(t\) by, digamos\(\left[P_{t}\right]\), entre los estados transitorios. Cada uno de estos\(t\) autovalores es estrictamente inferior a 1 (como se ve en la Sección 3.3.4) y ni estos valores propios ni sus vectores propios dependen de las probabilidades de transición del estado transitorio al recurrente. Los vectores propios izquierdos para las clases recurrentes tampoco dependen de estos estados transitorios a recurrentes. Sin embargo, el vector propio correcto\(\lambda=1\) para cada clase recurrente\(\mathcal{R}_{\ell}\) es muy interesante. Su valor es 1 para cada estado en\(\mathcal{R}_{\ell}\), es 0 para cada estado en las otras clases recurrentes, y es igual a\(\lim _{n \rightarrow \infty} \operatorname{Pr}\left\{X_{n} \in \mathcal{R}_{\ell} \mid X_{0}=i\right\}\) para cada estado transitorio i (ver Ejercicio 3.13).
El caso de la forma Jordan: Como se mencionó anteriormente, hay casos en los que uno o más valores propios de\([P]\) se repiten (como raíces de\(\operatorname{det}[P-\lambda I]\)) pero donde el número de vectores propios derechos linealmente independientes para un valor propio dado es menor que la multiplicidad de ese autovalor. En este caso, no hay suficientes vectores propios para cubrir el espacio, por lo que no hay una matriz M por M cuyas columnas sean autovectores linealmente independientes. Por lo tanto, no se\([P]\) puede expresar como\(\left[U^{-1}\right][\Lambda][U]\) donde\(\Lambda\) está la matriz diagonal de los valores propios, repetidos según su multiplicidad.
La forma Jordan es la cura para esta lamentable situación. La forma Jordan para un dado\([P]\) es la siguiente modificación de la matriz diagonal de valores propios: comenzamos con la matriz diagonal de valores propios, con los valores propios repetidos como elementos vecinos. Luego, por cada autovector faltante para un valor propio dado, se coloca un 1 inmediatamente a la derecha y por encima de un par vecino de apariencias de ese valor propio, como se ve en el ejemplo 9 a continuación:
\ ([J] =\ left [\ begin {array} {ccccc}
\ lambda_ {1} & 1 & 0 & 0 &
0\\ 0 &\ lambda_ {1} & 0 & 0 &
0 & 0 &\ lambda_ {2} & 1 & 0 &
0 & 0 &\ lambda_ {2} & 1\\
0 & 0 & 0 & 0 &\ lambda_ {2}
\ end {array}\ derecha]\)
Hay un teorema en álgebra lineal que dice que existe una matriz invertible y\([U]\) existe una forma Jordan tal que\([P]=\left[U^{-1}\right][J][U]\). El mayor valor para nosotros de este resultado es que hace que sea relativamente fácil de calcular\([J]^{n}\) para grandes\(n\) (ver Ejercicio 3.15). Este ejercicio también muestra que para todas las matrices estocásticas, cada valor propio de magnitud 1 tiene precisamente un vector propio asociado. Esto generalmente se expresa por la afirmación de que todos los valores propios de magnitud 1 son simples, lo que significa que su multiplicidad es igual a su número de vectores propios linealmente independientes. Finalmente el ejercicio muestra que\(\left[P^{n}\right]\) para una cadena recurrente aperiódica converge como polinomio 10 en\(n\) tiempos\(\lambda_{s}^{n}\) donde\(\lambda_{s}\) está el valor propio de mayor magnitud menor que 1.
Los resultados más importantes de esta sección sobre valores propios y vectores propios se pueden resumir en el siguiente teorema.
La matriz de transición de una unichaína de estado finito tiene un único valor propio\(\lambda=1\) con un vector propio izquierdo acompañante que\(\boldsymbol{\pi}\) satisface\ ref {3.9} y un vector propio izquierdo\(\boldsymbol{e}=(1,1, \ldots, 1)^\mathrm{T}\). Los otros valores propios satisfacen\(\lambda_{i}\) todos\(\left|\lambda_{i}\right| \leq 1\). La desigualdad es estricta a menos que la unicaína sea periódica, digamos con punto\(d\), y luego haya\(d\) valores propios de magnitud 1 espaciados por igual alrededor del círculo unitario. Si la unicaína es ergódica, entonces\(\left[P^{n}\right]\) converge al estado estacionario\(\boldsymbol{e\pi}\) con un error en cada término delimitado por un polinomio fijo en\(n\) tiempos\(\left|\lambda_{s}\right|^{n}\), donde\(\lambda_{s}\) está el eignevalor de mayor magnitud menor que 1.
Las cadenas arbitrarias de Markov se pueden dividir en sus clases recurrentes, y este teorema se puede aplicar por separado a cada clase.
Referencia
6 Los estudiantes de álgebra lineal suelen trabajar principalmente con vectores propios derechos (y en el álgebra lineal abstracta a menudo ignoran matrices y M-tuplas concretas por completo). Aquí es deseable una visión más concreta debido a la conexión directa de\(\left[P^{n}\right]\) las probabilidades de transición. Además, aunque los vectores propios izquierdos podrían convertirse en vectores propios derechos tomando la transposición de\([P]\), esto sería incómodo cuando se consideran las cadenas de Markov con recompensas y tanto los vectores de fila como de columna juegan papeles importantes.
7 Los lectores con poca exposición al álgebra lineal pueden aceptar los resultados del álgebra lineal en esta sección (sin perder mucho conocimiento) o pueden encontrarlos en Strang [19] o en muchos otros textos de álgebra lineal.
8 Si 0 es uno de los M valores propios, entonces solo se requieren M − 1 de tales matrices.