Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Does the limit of a Markov transition matrix $M$: $$\lim_{n\to\infty}M^n$$ always exist? And if yes, how to prove it?

share|improve this question
add comment

3 Answers

up vote 1 down vote accepted

The limit does not always exist. The simplest counterexample is $M=\begin{pmatrix}0&1\\1&0\end{pmatrix}$, where $M^{2n}=I$ and $M^{2n+1}=M$ for every natural number $n$. However, the limit exists if all entries of $M$ are positive. This is a consequence of the Perron-Frobenius Theorem, whose proof is no trivial matter.

share|improve this answer
add comment

The limit does not always exist. You can see it just by consider an example, say take $M$ to be the $2\times 2$ matrix with $0$ on the main diagonal and $1$ off the diagonal. In the context of Markov chains it is instructive to understand why you can't expect convergence always. When convergence occurs, it means there is a stationary distribution, and thus that the stochastic behaviour in the long run becomes stable. So now, imagine there are two states and the probability of passing from one state to the other is $1$. Clearly, no stability can ever be achieved. Intuitively, this is because the system is not connected enough or does not mix states well enough, in some sense. This can be made precise, as if all entries of the Markov transition matrix are positive, then it can be shown that the limit does indeed exist.

share|improve this answer
add comment

If all entries are positive, the limit does exist and the rows of the limiting matrix are identical. One way to prove this is to show the difference between the maximum and minimum value of the column entries goes to 0 exponentially as the matrix is raised to higher powers. This is done, I believe, in Kemeny's book on Markov chains

share|improve this answer
add comment

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.