Markov chain convergence problem. - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T14:34:21Z http://mathoverflow.net/feeds/question/38205 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/38205/markov-chain-convergence-problem Markov chain convergence problem. Gerardo 2010-09-09T17:32:30Z 2010-09-09T21:56:35Z <p>Consider a markov chain matrix P of size n x n (n states).</p> <p>P is known to be:</p> <p>1- there are at least two absorbent states. one of them is denoted by null. (thus, we have that P_null,null = 1)</p> <p>2- For the set of states that are not absorbent (called set H) , we have that P_h,null > 0 for all h in H.</p> <p>3- Not all states are recurrent.</p> <p>4- Aperiodic (the return to some states can occur at irregular times).</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/38205/markov-chain-convergence-problem/38212#38212 Answer by Bjørn Kjos-Hanssen for Markov chain convergence problem. Bjørn Kjos-Hanssen 2010-09-09T18:04:58Z 2010-09-09T18:47:28Z <p>Yes. $P^n$ converges to a matrix $Q$ with </p> <p>(i) $Q_{i,i}=1$ for each $i\not\in H$ ($i$ is absorbent), and </p> <p>(ii) $\sum_{j\not\in H} Q_{i,j}=1$ for all $i\in H$.</p> <p>To see (ii) we need that $\sum_{j\not\in H}P^n_{i,j}\rightarrow 1$ for all $i\in H$. For this note that $\sum_{j\not\in H}P^n_{i,j}$ is the probability of going from $i$ to an absorbent state in $n$ steps, and so if $P_{i,\text{null}}\ge\lambda>0$ for all $i\in H$ then for all $j\not\in H$, $$P^n_{i,j}\le (1-\lambda)^n\rightarrow 0.$$ To get a unique such $Q$ we need to show for each absorbent state (say, for null) $$\lim_n \ P^n_{i,\text{null}}\quad\text{exists}$$ for each $i\in H$. But $P^n_{i,\text{null}}\le P^{n+1}_{i,\text{null}}$ since once we get to null we stay there.</p> http://mathoverflow.net/questions/38205/markov-chain-convergence-problem/38232#38232 Answer by Byron Schmuland for Markov chain convergence problem. Byron Schmuland 2010-09-09T21:42:57Z 2010-09-09T21:56:35Z <p>Yes, uniqueness holds.</p> <p>Condition 2 implies that every state $j$ is either absorbing $(j\not\in H)$ or transient $(j\in H)$. Define the absorption time to be $T=\inf (n\geq 0: X_n\not\in H)$. This $T$ is almost surely finite for any starting state $i$, that is, the chain is eventually absorbed. </p> <p>If $j\in H$, then $p^n_{ij}=P_i(X_n=j)\leq P_i(T>n)\to 0=:Q_{ij}$ as $n\to\infty$. </p> <p>If $j\not\in H$, then $p^n_{ij}=P_i(X_n=j)\uparrow P_i(X_T=j)=:Q_{ij}$ as $n\to\infty$. </p>