Markov chains question?

Question

A country is divided into three geographic regions. It is found that each year 5% of the residents move from region I to region II and 5% move from region I to region III. In region II, 15% move to region I, and 10% move to region III. In region III, 10% move to region I, and 5% to region II. Find the steady-state population distribution.

This is one of the matrices I have

$$P = \begin{pmatrix} 0.9 & 0.05 &0.05\\ 0.15 &0.75& 0.1\\ 0.1 & 0.05 &0.85 \end{pmatrix}$$

write this as

$$ \begin{align} x+y+z &= 1\\ -.1x+.15y+.1z &= 0 \\ .05x-.25y+.05z &= 0\\ .05x+.10y-.15z &= 0 \end{align}$$

How can I get the steady state matrix for all three regions? Am I doing the problem correctly so far?

Answer 1

The stationary distribution is a row vector $\pi$ which satisfies $$ \pi P = \pi$$ so the system of equations you need to solve isn't $P x = 0$, but rather $ \pi P = \pi$ with the additional constraint that the elements of $\pi$ must sum to 1.

If we write $\pi = \begin{pmatrix} x & y & z \end{pmatrix}$ so $x$, $y$ and $z$ are the elements of the vector $\pi$ then you need to solve the system $$\begin{pmatrix} x & y & z \end{pmatrix} . \begin{pmatrix} 0.9 & 0.05 &0.05\\ 0.15 &0.75& 0.1\\ 0.1 & 0.05 &0.85 \end{pmatrix} = \begin{pmatrix} x & y & z \end{pmatrix} $$ with the additional constraint that $x+y+z=1$. We can solve this using Gaussian elimiation to find $$\pi = \begin{pmatrix} 0.541667 & 0.166667 & 0.291667 \end{pmatrix}.$$

Answer 2

There are at least three ways to answer this problem.

If you just want a numerical answer, the easiest is probably is just to keep squaring the matrix to approximate $P^{\infty}$. Because a transition matrix can be written as

$$V \begin{bmatrix} 1 & 0 & 0 \\ 0 & a & 0 \\ 0 & 0 & b \end{bmatrix} V^{-1}$$

with $a < 1$ and $b < 1$, you'll double the accuracy of the decimal places with each step.

$$\underbrace{P^{2^{2^{...}}}}_{\text{6 times}} = \begin{bmatrix}0.54166690206815 & 0.16666666664634 & 0.29166643128552\\ 0.54166658815207 & 0.16666666676831 & 0.29166674507961\\ 0.54166627435797 & 0.16666666664634 & 0.29166705899569\end{bmatrix}$$

Another way to solve it is to actually compute the eigenvalue decomposition. (I'll use the symbol $\infty$ loosely for simplicity sake.)

$$P^{\infty} = \left(\begin{bmatrix}1 & 1 & 1\\ 1 & -\frac{1}{3} & -5\\ 1 & -\frac{5}{3} & 1\end{bmatrix} \begin{bmatrix} 1 & 0 & 0 \\ 0 & 0.8 & 0 \\ 0 & 0 & 0.7 \end{bmatrix} \begin{bmatrix}1 & 1 & 1\\ 1 & -\frac{1}{3} & -5\\ 1 & -\frac{5}{3} & 1\end{bmatrix}^{-1}\right)^{\infty} $$ $$P^{\infty} = \begin{bmatrix}1 & 1 & 1\\ 1 & -\frac{1}{3} & -5\\ 1 & -\frac{5}{3} & 1\end{bmatrix} \begin{bmatrix} 1^{\infty} & 0 & 0 \\ 0 & 0.8^{\infty} & 0 \\ 0 & 0 & 0.7^{\infty} \end{bmatrix} \begin{bmatrix}1 & 1 & 1\\ 1 & -\frac{1}{3} & -5\\ 1 & -\frac{5}{3} & 1\end{bmatrix}^{-1} $$

$$P^{\infty} = \begin{bmatrix}1 & 1 & 1\\ 1 & -\frac{1}{3} & -5\\ 1 & -\frac{5}{3} & 1\end{bmatrix} \begin{bmatrix} 1 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix} \begin{bmatrix}1 & 1 & 1\\ 1 & -\frac{1}{3} & -5\\ 1 & -\frac{5}{3} & 1\end{bmatrix}^{-1} $$

$$P^{\infty} = \begin{pmatrix}\frac{13}{24} & \frac{1}{6} & \frac{7}{24}\\ \frac{13}{24} & \frac{1}{6} & \frac{7}{24}\\ \frac{13}{24} & \frac{1}{6} & \frac{7}{24}\end{pmatrix}$$

Another way to find the steady state is as Gareth suggested.

You are looking for $\pi P = \pi$. If you matrix has no sink states (a row will all zeroes and a single one), then this amounts to computing the left null space of $P - I$, then dividing through by a constant to maintain the stochastic property.

$$left-null-space(P - I) = \begin{bmatrix} 260 & 80 & 140\end{bmatrix}$$ $$steady-state = \frac {\begin{bmatrix} 260 & 80 & 140\end{bmatrix}} {260 + 80 + 140} = \begin{bmatrix}\frac{13}{24} & \frac{1}{6} & \frac{7}{24}\end{bmatrix}$$

If you do have sink states, then this amounts to computing a matrix inverse of a sub matrix without the sink rows and columns then doing a matrix multiplication which you can probably figure out if you need to.