2
$\begingroup$

I have encountered a Markov process with following transition matrix $P= \begin{bmatrix} 0.6 & 0.4 \\ 0.2 &0.8\end{bmatrix} $. This is an ergodic Markov matrix since all the elements are positive. So it has a stationary distribution, which is $\pi=(\frac{1}{3},\frac{2}{3}) $. I know that no matter what the initial distribution is, it will always converge to the stationary distribution. However, it there a way to quantify how fast the convergence will be? I'm interested in the convergence speed because I'm trying to calculate the number of occurrences in state 1 during a 1000000-steps walk.

$\endgroup$
3
$\begingroup$

Sure. You just need to compute the eigenvalues that are not $1$. In this case your eigenvalues are the solutions to $\lambda^2-1.4\lambda+0.4=0$, which are $1$ and $0.4$. This means that $p A^n$ = $\pi + 0.4^n v_p$ for some row vector distribution $v_p$ depending on $p$, and where $\pi$ is the equilibrium distribution. Specifically $v_p$ is the component of $p$ in the direction of the (left) eigenvector with eigenvalue $0.4$. Note that $v_p$ itself is not a distribution at all.

$\endgroup$
2
  • 1
    $\begingroup$ Thanks for the answer. Can you provide more details about why this decomposition $p A^n = \pi + 0.4^n v_p $ works? It doesn't seem so obvious to me. $\endgroup$
    – andy90
    Dec 6 '14 at 16:39
  • $\begingroup$ @andy90 It is just diagonalization. You have $A=V \begin{bmatrix} 1 & 0 \\ 0 & 0.4 \end{bmatrix} V^{-1}$ where $V$ is the eigenvector matrix. Now exponentiate $A$ and apply $p$ on the left. $\endgroup$
    – Ian
    Dec 6 '14 at 16:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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