Cómo calcular series de potencia con una matriz de norma grande.

Question

Tomemos esta matriz que representa el mapa de Markov para ver una Cara seguida de una Cruz en una secuencia de lanzamientos de monedas justas: $$M = \begin{pmatrix} \frac{1}{2} & \frac{1}{2} & 0 \\ \frac{1}{2} & 0 & \frac{1}{2} \\ 0 & 0 & 1 \end{pmatrix}$$ Como el estado final es absorbente podemos razonar que $$\lim_{n\rightarrow \infty} M^n = L = \begin{pmatrix} 0 & 0 & 1 \\ 0 & 0 & 1 \\ 0 & 0 & 1 \end{pmatrix}$$

Me interesa el siguiente límite de una suma para matrices como ésta. $$\lim_{n \rightarrow \infty } \left( n M^n - \sum_{i=0}^{n-1}M^i \right)$$ Parece que puedo reemplazar fácilmente $M^n$ con $L$ en el primer término, pero ¿qué hacer con el bit de la suma real?

Normalmente miraría eso y pensaría en la serie de potencias, excepto que la norma de $M$ es demasiado grande para que eso funcione.

Parece (por la evidencia empírica) que en este caso obtengo $$ \lim_{n \rightarrow \infty} \sum_{i=0}^{n-1}M^i = \begin{pmatrix} 4 & 2 & n-6 \\ 2 & 2 & n-4 \\ 0 & 0 & n \end{pmatrix}$$

Esto significa que puedo hacer el límite de arriba, de hecho obtengo $$ \lim_{n \rightarrow \infty } \left( n M^n - \sum_{i=0}^{n-1}M^i \right) = \begin{pmatrix} -4 & -2 & 6 \\ -2 & -2 & 4 \\ 0 & 0 & 0 \end{pmatrix}$$

Pero, ¿cómo puedo hacer esto en general (sin un montón de cálculos numéricos cada vez)? He probado varios mapas de Markov de este tipo y parece que siempre consigo la convergencia, aunque mis matrices siempre tienen una norma mayor que uno. Te agradecería que me ayudaras.

Gracias de antemano.

ACTUALIZACIÓN: Ver el post de greg más abajo. Básicamente, si asumimos que hay un límite (digamos $S$ para el límite de las sumas parciales) podemos hacer lo siguiente:

$$ n M^n - \sum_{i=0}^{n-1}M^i = \sum_{i=0}^{n-1} (M^n - M^i) $$ Entonces $$ S = \lim_{n\rightarrow \infty} \sum_{i=0}^{n-1} (M^n - M^i) $$ Si se toma esa ecuación y se multiplica por $M$ y restar $I$ se obtiene

$$ S - L = M S - I \Rightarrow (M - I)S = I - L$$

que es lo mismo que tenía Greg. El problema es que no siempre se puede tomar la inversa de $(M-I)$ En los casos que he considerado es singular.

En este punto me he dado cuenta de que siempre puedo esperar la última fila de $S$ sea el vector cero siempre que $M$ es efectivamente una matriz estocástica derecha (como es el caso de lo que estoy haciendo). De hecho, la última fila de $M$ en un mapa de Markov absorbente siempre va a ser ${0,\ldots,0,1}$ . Así que, en cierto sentido, me interesan sobre todo las filas superiores de la matriz $M$ .

Introduzca $T$ donde $T$ es la matriz de identidad con la última fila a cero.

$$ T = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 0 \end{pmatrix} $$

Entonces $ S = T S $ y podemos sustituir $M \rightarrow T M$ y $ L \rightarrow T L$ y seguir la lógica anterior para obtener $$ (T M - I) S = T - T L = I - L $$ Ahora podemos invertir $(T M - I)$ y resolver el límite $S$

$$ S = (T M - I)^{-1} (I - L) $$ No sé por qué $(T M - I)$ debería ser siempre no singular, pero a mí me ha funcionado para muchas opciones diferentes de $M$ como matrices de derecha-estocástica con la última fila terminada en uno.

Siento que he respondido a mi propia pregunta, aunque el post de greg contiene la mayor parte de esta información (antes de que tuviera la oportunidad de escribir todo esto).

Answer 1

Siga adelante y sustituya $L$ y su suma se convierte en $$ \sum_{i=0}^{n-1} (L-M^i) $$ Hay algún índice finito $k$ para lo cual $M^k$ es indistinguible de $L$ . Por lo tanto, los términos más allá de ese índice no contribuirán a la suma. Una vez que se determina cuál es el valor de corte, se tiene una suma finita $$ \sum_{i=0}^{k} (L-M^i) $$

Actualización

Denota el $k^{th}$ suma parcial como $$ S_k = \sum_{i=0}^{k} (L-M^i) $$ Utilizando el hecho de que $ML=LM=L$ encontramos fácilmente que $LS_k=S_kL=0$ .

Con un poco más de esfuerzo podemos encontrar $$ \eqalign{ S_kM = MS_k &= M\sum_{i=0}^{k} (L-M^i) \cr &= \sum_{i=0}^{k} (LM-M^{i+1}) \cr &= \sum_{i=1}^{k+1} (L-M^{i}) \cr &= (L-M^{k+1}) - (L-I) + \sum_{i=0}^{k} (L-M^i) \cr &= (I-L) + S_k \cr }$$ donde $L=M^{k+1}$ para un tamaño lo suficientemente grande $k$ .

Finalmente podemos resolver para $S_k$ $$ \eqalign{ (M-I)S_k &= (I-L) \cr S_k &= (M-I)^{+}(I-L) \cr }$$ Esta debería ser la solución, pero la solución encontrada en el enunciado del problema resulta ser esta $$ \eqalign{ S_k &= (I-L)(M-I)^{+}(I-L) \cr }$$ Pero no veo por qué tengo que multiplicar por $(I-L)$ .