-2
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – Louigi Addario-Berry
    Commented Sep 9, 2010 at 16:40
  • $\begingroup$ Sorry, i made a mistake. I changed the description of the problem. $\endgroup$
    – Gerardo
    Commented Sep 9, 2010 at 17:00
  • 2
    $\begingroup$ @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. $\endgroup$
    – user6096
    Commented Sep 9, 2010 at 17:00
  • $\begingroup$ Whoops, new question! $\endgroup$
    – user6096
    Commented Sep 9, 2010 at 17:01
  • $\begingroup$ There are a lot of good resources on Markov chains. May I suggest: dartmouth.edu/~chance/teaching_aids/books_articles/… It's undoubtedly tricky stuff, especially coming in from the modeling side. $\endgroup$
    – Thierry Zell
    Commented Sep 9, 2010 at 18:58

3 Answers 3

Reset to default
0
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Gerardo
    Commented Sep 9, 2010 at 17:31
  • 1
    $\begingroup$ 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? $\endgroup$
    – user6096
    Commented Sep 9, 2010 at 17:33
0
$\begingroup$

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

Improve this answer
$\endgroup$
0
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Gerardo
    Commented Sep 9, 2010 at 16:28
  • $\begingroup$ 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. $\endgroup$
    – rpotrie
    Commented Sep 9, 2010 at 16:32
  • $\begingroup$ Since the question asks about limits of matrices and not about almost sure behavior, I guess Borel-Cantelli is not relevant. $\endgroup$
    – Bjørn Kjos-Hanssen
    Commented Sep 9, 2010 at 18:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .