Convergence of a markov matrix - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T22:40:57Z http://mathoverflow.net/feeds/question/38191 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/38191/convergence-of-a-markov-matrix Convergence of a markov matrix Gerardo 2010-09-09T16:12:49Z 2010-09-09T18:48:08Z <p>Consider a markov chain matrix P of size n x n (n states).</p> <p>P is known to be:</p> <p>1- Not irreducible (i.e. there exist at least a pair of states i, j such that we cannot go from i to j)</p> <p>2- Not all states are recurrent.</p> <p>3- Aperiodic (the return to some states can occur at irregular times).</p> <p>4- there are at least two absorbent states i,j (P_i,i = P_j,j = 1) </p> <p>It is true that limit when n goes to infinity of P^n converges? Is this result well known or is the proof simple?</p> <p>Thanks.</p> http://mathoverflow.net/questions/38191/convergence-of-a-markov-matrix/38192#38192 Answer by rpotrie for Convergence of a markov matrix rpotrie 2010-09-09T16:26:50Z 2010-09-09T16:26:50Z <p>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. </p> <p>The proof follows from the well known <a href="http://en.wikipedia.org/wiki/Borel%25E2%2580%2593Cantelli_lemma" rel="nofollow">Borel-Cantelli Lemma</a>. 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. </p> http://mathoverflow.net/questions/38191/convergence-of-a-markov-matrix/38194#38194 Answer by Bjørn Kjos-Hanssen for Convergence of a markov matrix Bjørn Kjos-Hanssen 2010-09-09T16:34:26Z 2010-09-09T17:17:08Z <p>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.</p> http://mathoverflow.net/questions/38191/convergence-of-a-markov-matrix/38216#38216 Answer by Yaroslav Bulatov for Convergence of a markov matrix Yaroslav Bulatov 2010-09-09T18:48:08Z 2010-09-09T18:48:08Z <p>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.</p> <p>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}$$ </p> <p>Columns of this matrix (assuming column stochastic transition matrix) give fraction of time that Markov chain spends in each state eventually</p> <p>Ch.8 of "Matrix Analysis &amp; Applied Linear Algebra" by Carl Meyer gives more details on these conditions</p>