Convergence of a markov matrix - MathOverflow

Convergence of a markov matrix

2010-09-09T16:12:49Z

Consider a markov chain matrix P of size n x n (n states).

P is known to be:

1- Not irreducible (i.e. there exist at least a pair of states i, j such that we cannot go from i to j)

2- Not all states are recurrent.

3- Aperiodic (the return to some states can occur at irregular times).

4- there are at least two absorbent states i,j (P_i,i = P_j,j = 1)

It is true that limit when n goes to infinity of P^n converges? Is this result well known or is the proof simple?

Thanks.

Answer by rpotrie for Convergence of a markov matrix

2010-09-09T16:26:50Z

I believe that it is not hard to show that $(P^n)_{i,null} \to 1$ as $n\to \infty$ which responds your question if I understand well.

The proof follows from the well known Borel-Cantelli Lemma. Notice that the probability of not arriving to the null state is in each step smaller than one (and far from one since there are finitely many states), so you get that the probability of not reaching the null state in a given step is smaller than $\lambda^n$ where $n$ is the number of steps. This implies that the probability of never reaching the null state is zero by the Lemma above.

Answer by Bjørn Kjos-Hanssen for Convergence of a markov matrix

2010-09-09T16:34:26Z

Suppose the answer is Yes. Then suppose we add two more states $i\ne j$ with $P_{i,j}=1$ and $P_{j,i}=1$, and no other state can go to states $i$ or $j$. Then for the new matrix the assumptions are still satisfied, but now the answer is No. Therefore the answer must be No.

Answer by Yaroslav Bulatov for Convergence of a markov matrix

2010-09-09T18:48:08Z

For irreducible Markov chain, necessary condition for convergence is primitivity (ie, all entries of $P^k$ are positive for some k). In a reducible Markov chain, your Markov walker eventually settles into one of $k$ ergodic classes where states inside each class can all reach each other. Hence, reducible Markov chain can be thought of a collection of irreducible Markov chains on a partitioning of the state space, and the limit exists if and only if Markov chain on each of those classes is primitive.

Even if $\lim_{n \to \infty} P^k$ doesn't exist, Cesaro sum always does, ie $$\lim_{n\to \infty} \frac{I+P^1+P^2+\ldots P^n}{n}$$

Columns of this matrix (assuming column stochastic transition matrix) give fraction of time that Markov chain spends in each state eventually

Ch.8 of "Matrix Analysis & Applied Linear Algebra" by Carl Meyer gives more details on these conditions