Does there exist a steady state vector of Markov Matrix
$$P=\begin{bmatrix} \frac{1}{2} & \frac{1}{3}\\ \frac{1}{2} & \frac{2}{3} \end{bmatrix}$$
Initially I was not sure whether to answer yes or no, but using $(I-P)X=0$, I've found the following
$$\begin{bmatrix} \frac{1}{2} & -\frac{1}{3} & 0\\ -\frac{1}{2} & \frac{1}{3} & 0 \end{bmatrix}$$
$$\begin{bmatrix} 1 & -\frac{-2}{3} & 0 \\ 0 & 0 & 0 \end{bmatrix}$$
So I found that,
$$X =\begin{bmatrix} \frac{2}{3} \\ 1 \end{bmatrix}$$
Normalizing it, the steady-state vector is
$$X =\begin{bmatrix} \frac{2}{5} \\ \frac{3}{5} \end{bmatrix}$$
So I guess the steady state vector exists, but this raises a question. What does it take so that the steady state vector does not exist? What happens if I have more than 1 vector? And can you have infinitely many steady state vectors?
Best Answer
First of all, any right-stochastic matrix $A$ has an eigenvalue of $1$. This is easiest to see because $A^T$ has $\begin{bmatrix} 1 \\ 1 \\ \vdots \\ 1 \end{bmatrix}$ as an eigenvector. So $A$ also has an eigenvalue of $1$. Provided all entries of the corresponding eigenvector have the same sign, the eigenvector can be normalized to obtain a stationary distribution.
There can be more than one such eigenvector. This trivially happens if the matrix for the chain is just the identity. But it can also happen in a nontrivial reducible chain. For instance consider a chain with matrix
$$\begin{bmatrix} 1/2 & 1/2 & 0 & 0 \\ 1/2 & 1/2 & 0 & 0 \\ 0 & 0 & 1/2 & 1/2 \\ 0 & 0 & 1/2 & 1/2 \end{bmatrix}.$$
This chain has an invariant distribution which is confined to $\{ 1,2 \}$ and another which is confined to $\{ 3,4 \}$.
The one interesting question is whether a right-stochastic matrix can have an eigenvector with eigenvalue $1$ which cannot be normalized into a distribution (because the entries take on both signs). The answer to this question is basically no. Specifically, the entries of an eigenvector with eigenvalue $1$ have only one sign on each component of the chain. So we can choose a basis of the eigenspace for the eigenvalue $1$ so that each member of the basis is a stationary distribution. In my example these would be $\begin{bmatrix} 1/2 \\ 1/2 \\ 0 \\ 0 \end{bmatrix}$ and $\begin{bmatrix} 0 \\ 0 \\ 1/2 \\ 1/2 \end{bmatrix}$.
A linear-algebraic proof of the previous statement uses the Gerschgorin circle theorem (to prove that all eigenvalues have magnitude at most $1$) and the Perron-Frobenius theorem (to prove the part about the sign of the entries of the eigenvector).
A note on conventions: your Markov matrix is right-stochastic, meaning that its column sums are $1$. Probabilists often write Markov matrices as left-stochastic, meaning that their row sums are $1$. In your case distributions are column vectors and applied from the right; in the other case distributions are row vectors and applied from the left. Either way is fine, just keep it in mind.