Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
This is really an exercise. Assumptions $1$ and $3$ are irrelevant, it is standard that each transient state is only visited finitely often with probability $1$, so we must have P^n_{ij} --> 0 for all pairs (i,j) not equal to (null, null). Since P^n is a stochastic matrix for all $n$, it follows that also P^n_{null,null} --> 1. –  Louigi Addario-Berry Sep 9 '10 at 16:40
    
Sorry, i made a mistake. I changed the description of the problem. –  Gerardo Sep 9 '10 at 17:00
2  
@louigi You mean $P^n_{ij}\to 0$ for all pairs $(i,j)$ with $j$ not equal to "null". In other words, the chain is eventually absorbed at "null" from every starting point $i$, so the limit matrix is a column of ones at "null", and zero elsewhere. rpotrie's solution is correct. –  Byron Schmuland Sep 9 '10 at 17:00
    
Whoops, new question! –  Byron Schmuland Sep 9 '10 at 17:01
    
Yes, thanks Byron. –  Louigi Addario-Berry Sep 9 '10 at 17:54

3 Answers 3

up vote 0 down vote accepted

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.

share|improve this answer
    
I will repost the question, because i made another mistake. This comes from a real world problem and i now trying to put the problem in mathematical terms. I am really sorry again. –  Gerardo Sep 9 '10 at 17:31
1  
These newly added states have period 2, so whether this solves the problem depends on what Gerardo means by condition 3. Does he want all or some of the states to be aperiodic? –  Byron Schmuland Sep 9 '10 at 17:33

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

share|improve this answer

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.

share|improve this answer
    
Actually, i made a mistake. It is not true that P_i,null >0 for all states i (only for some). I therefore modified the text and erased that property. I am sorry. –  Gerardo Sep 9 '10 at 16:28
    
If I am not wrong, the hypothesis you have imply that there exists $t$ such that the probability of reaching the null state in $t$ steps is positive. That would make the argument work. –  rpotrie Sep 9 '10 at 16:32
    
Since the question asks about limits of matrices and not about almost sure behavior, I guess Borel-Cantelli is not relevant. –  Bjørn Kjos-Hanssen Sep 9 '10 at 18:09

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.