Take this matrix representing the Markov map for seeing a Heads followed by a Tails in a sequence of fair coin flips: $$M = \begin{pmatrix} \frac{1}{2} & \frac{1}{2} & 0 \\ \frac{1}{2} & 0 & \frac{1}{2} \\ 0 & 0 & 1 \end{pmatrix}$$ Since the final state is absorbing we can reason that $$\lim_{n\rightarrow \infty} M^n = L = \begin{pmatrix} 0 & 0 & 1 \\ 0 & 0 & 1 \\ 0 & 0 & 1 \end{pmatrix}$$
I am interested in the following limit of a sum for matrices like this. $$\lim_{n \rightarrow \infty } \left( n M^n - \sum_{i=0}^{n-1}M^i \right)$$ It would seem that I can easily replace $M^n$ with $L$ in the first term but what to do with the actual sum bit??
Ordinarily I'd look at that and think of the power series, except that the norm of $M$ is too big for that to work.
It seems (from empirical evidence) that in this case I get $$ \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}$$
This means that I can do the limit from above, indeed I get $$ \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}$$
But how can I do this in general (without a lot of numerical computation each time)? I've tried a few different such Markov maps and I always seem to get convergence even though my matrices always have a norm larger than one. I'd appreciate some help!
Thanks in advance.
UPDATE: See greg's post below. Basically if we assume there is a limit (say $S$ for the limit of the partial sums) we can do the following:
$$ n M^n - \sum_{i=0}^{n-1}M^i = \sum_{i=0}^{n-1} (M^n - M^i) $$ Then $$ S = \lim_{n\rightarrow \infty} \sum_{i=0}^{n-1} (M^n - M^i) $$ If you take that equation and multiply by $M$ and subtract $I$ you get
$$ S - L = M S - I \Rightarrow (M - I)S = I - L$$
which is the same as what greg had. The problem is that you can't always take the inverse of $(M-I)$; in the cases I considered it is singular.
At this point I noticed that I can always expect the last row of $S$ to be the zero vector as long as $M$ is indeed a right stochastic matrix (as is the case for what I'm doing). In fact the last row of $M$ in an absorbing Markov map is always going to be ${0,\ldots,0,1}$. So in some sense I'm really mostly interested in the upper rows of the matrix $M$.
Introduce $T$ where $T$ is the identity matrix with the last row zeroed out.
$$ T = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 0 \end{pmatrix} $$
Then $ S = T S $ and we can replace $M \rightarrow T M$ and $ L \rightarrow T L$ and follow the above logic to get $$ (T M - I) S = T - T L = I - L $$ Now we can invert $(T M - I)$ and solve for the limit $S$
$$ S = (T M - I)^{-1} (I - L) $$ I don't know why $(T M - I)$ should always be non-singular but it worked for me for many different choices of $M$ as right-stochastic matrices with the last row ending with one.
I feel like I've answered my own question, although greg's post contains most of this information (before I had a chance to write this all down).