Computing the limiting distribution of a Markov chain with absorbing states It is well known that an irreducible Markov chain has a unique stationary distribution, and the limiting distribution of a Markov chain – if it exists – is stationary, so finding the limiting distribution is a straightforward matter of linear algebra.
However, I would like to ask about Markov chains that are not irreducible.
Consider a Markov chain on a finite state space, with at least one absorbing state, and from every non-absorbing state at least one absorbing state is reachable.
Let $P$ be the transition matrix.
Intuitively, such a Markov chain must have a limiting distribution (i.e. $\lim_{n \to \infty} P^n$ exists), but I do not know how to prove this.
In any case, assume $P^\infty = \lim_{n \to \infty} P^n$ exists.
Question 1.
How do I compute $P^\infty$?
If $P$ is diagonalisable then this is easy, though I am not sure this can be achieved using exact arithmetic.
If $P - I$ has a null space of dimension exactly $1$ – i.e. the Markov chain has a unique stationary distribution – then we can compute $P^\infty$ exactly... but under these hypotheses the only way this can happen is if there is exactly one absorbing state, and the limiting distribution is obviously the degenerate distribution supported on that absorbing state – not very interesting, I think.
Specifically, I would like to know whether $P^\infty$ can be computed using "only elementary arithmetic".
This is a bit vague but it is related to the following question:
Question 2. If the entries of $P$ are rational, are the entries of $P^\infty$ also rational?
The point being that if $P^\infty$ can have irrational entries even if $P$ only has rational entries, then there is no hope of computing $P^\infty$ using "only elementary arithmetic".
 A: Let $Q$ be the matrix with entries defined as follows:
$$Q_{i j} = \begin{cases}
P_{i j} & \text{if } j \text{ is not an absorbing state} \\
0 & \text{if } j \text{ is an absorbing state}
\end{cases}$$
Note that we also have $Q_{i j} = 0$ when $i$ is an absorbing state.
Let $R = P - Q$.
By construction, $R_{i j} = 0$ if $j$ is not an absorbing state, so $R Q = 0$.
Furthermore $R^2 = R$, because $R_{i j} = \delta_{i j}$ when $i$ and $j$ are absorbing states.
Hence, for $n \ge 1$:
$$P^n = (Q + R)^n = Q^n + Q^{n - 1} R + Q^{n - 2} R + \cdots + Q R + R$$
The entries of $Q$ and $R$ are non-negative, so the entries of $P^n - Q^n$ are non-decreasing in $n$.
Since $P$ is a stochastic matrix, the entries of $P^n - Q^n$ are $\le 1$, hence $\lim_{n \to \infty} (P^n - Q^n)$ exists.
It follows that $\lim_{n \to \infty} Q^n = 0$, by considering row sums.
Therefore:
$$\lim_{n \to \infty} P^n = \sum_{n = 0}^{\infty} Q^n R = (I - Q)^{-1} R$$
Conclusion.
To compute $P^\infty = \lim_{n \to \infty} P^n$, we may simply solve the linear equation $(I - Q) P^\infty = R$.
In particular, if the entries of $P$ are rational numbers, then so too are the entries of $P^\infty$.
