How fast does this Markov chain converge?

Question

Observe the above a Markov chain and limiting matrix of it. Finding the limiting matrix if it exists is easy but I am curious as to how fast this given matrix converges to its limiting matrix. Is there a way to find the number of transitions that would give a matrix that is very close to the limiting matrix for an accepted amount of error? I hope someone could suggest me some methods or references that would help me determine this. Thanks in advance

Answer 1

The trace and the determinant of $M$ are $0$ and $\frac29$ respectively. Since $M$ is a transition matrix, $1$ is an eigenvalue, hence the sum and product of the two other eigenvalues are $-1$ and $\frac29$ respectively. This implies that these eigenvalues are $-\frac23$ and $-\frac13$.

Thus, the difference $M^k-\Pi$ is of order $\left(\frac23\right)^k$ when $k\to\infty$, where $\Pi=\lim\limits_{n\to\infty}M^n$ is given in the question. Here one can define the size of a matrix of any size as the sum of the absolute values of its entries.

In particular, for every vector $V$, the difference $M^kV-\Pi V$ is of order at most $\left(\frac23\right)^k$ when $k\to\infty$.

Answer 2

When you found $M^k$ for this matrix, you likely used a diagonalization argument; you have $M = U \Lambda U^{-1}$ where $\Lambda$ is diagonal. In this case $M^k = U \Lambda^k U^{-1}$ and if $$\Lambda = \begin{pmatrix} \lambda_1 & 0 & 0 \\ 0 & \lambda_2 & 0 \\ 0 & 0 & \lambda_3 \end{pmatrix}$$ then $$\Lambda = \begin{pmatrix} \lambda_1^k & 0 & 0 \\ 0 & \lambda_2^k & 0 \\ 0 & 0 & \lambda_3^k \end{pmatrix}.$$ So, $$ M^k = U \begin{pmatrix} \lambda_1^k & 0 & 0 \\ 0 & \lambda_2^k & 0 \\ 0 & 0 & \lambda_3^k \end{pmatrix} U^{-1}. $$ This shows that, in a certain sense, the "speed" of convergence of $M^k$ can be explored by considering the "speed" of convergence of $\lambda_1^k, \lambda_2^k,$ and $\lambda_3^k$.

Answer 3

For simplicity, assume that $M$ is diagonalisable and hence there exists a nonsingular matrix $X$ such that $$ M=X\begin{bmatrix}\Lambda&0\\0&I\end{bmatrix}X^{-1}, $$ where $\Lambda=\mathrm{diag}(\lambda_1,\ldots,\lambda_r)$ such that $|\lambda_i|<1$ and $I$ is the identity matrix. Let $\|\cdot\|$ be a sub-multiplicative matrix norm such that the norm of a diagonal matrix is equal to the maximal absolute value of its diagonal entries (this is satisfied, e.g., by any $p$-norm such as the spectral norm). Then $$ M^k=X\begin{bmatrix}\Lambda^k&0\\0&I\end{bmatrix}X^{-1}, \quad M^{\infty}\equiv\lim_{k\rightarrow\infty}M^k=X\begin{bmatrix}0&0\\0&I\end{bmatrix}X^{-1}. $$ Then $$ M^{k}-M^{\infty}=X\begin{bmatrix}\Lambda^k&0\\0&0\end{bmatrix}X^{-1} $$ and hence $$ \|M^{k}-M^{\infty}\|\leq\|X\|\|X^{-1}\|\left\|\begin{bmatrix}\Lambda^k&0\\0&0\end{bmatrix}\right\| =\kappa(X)\rho^k, $$ where $\kappa(X)\equiv\|X\|\|X^{-1}\|$ is the condition number of the eigenvector basis $X$ and $\rho\equiv\max\{|\lambda_i|:\;i=1,\ldots,r\}$. Hence a sufficient condition for having $\|M^k-M^{\infty}\|\leq\epsilon<1$ is to have $\kappa(X)\rho^k\leq\epsilon$ and thus $$ k\geq\frac{\log[\epsilon/\kappa(X)]}{\log\rho}. $$