2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Consider the identity matrix and $$\begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}$$ $\endgroup$ – Bob Krueger Apr 17 '15 at 17:55
  • $\begingroup$ What makes the matrix you gave me to not to have a steady-state vector? $\endgroup$ – amundi12 Apr 17 '15 at 18:01
  • $\begingroup$ Uhh... nevermind. There will always be a steady-state vector I think. There just may be infinitely many steady state vectors. $\endgroup$ – Bob Krueger Apr 17 '15 at 18:09
  • 1
    $\begingroup$ Well you did mention the identity matrix, which would make the steady state vector a zero vector. Not sure if that counts as a steady-state vector. So you may be right on that one $\endgroup$ – amundi12 Apr 17 '15 at 18:11
  • 2
    $\begingroup$ The identity matrix has infinitely many steady-state vectors, because for any vector $v$, $Iv = v$. $\endgroup$ – Bob Krueger Apr 17 '15 at 18:14
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ As far as I know, a steady state is a vector X such that PX = X. I can assure this equation holds using the X that I have found. And as far as I know, a stochastic matrix do not take a negative entries on its matrix. $\endgroup$ – amundi12 Apr 17 '15 at 18:54
  • $\begingroup$ @amundi12 The negative entries part is for the entries of the eigenvector, not the entries of the matrix. Notice that in my 4 state example, $\begin{bmatrix} 1/2 \\ 1/2 \\ -1/2 \\ -1/2 \end{bmatrix}$ is indeed an eigenvector with eigenvalue $1$. There is no way to normalize this eigenvector into a distribution. This is why the answer to the question I posed is only "basically no" rather than just "no". $\endgroup$ – Ian Apr 17 '15 at 19:00
  • $\begingroup$ Oh I understand! So whenever there are both signs in an eigenvector with eigenvalue 1, is it safe to say that the steady state vector does not exist? $\endgroup$ – amundi12 Apr 17 '15 at 19:05
  • $\begingroup$ @amundi12 No, you misunderstand somewhat. There will always be an eigenvector with eigenvalue 1. Some of these can be normalized, and if there is only one linearly independent eigenvector with eigenvalue 1 then all of them can be normalized. But if there are two linearly independent eigenvectors, then you can normalize them both and then subtract one from the other, obtaining an eigenvector which cannot be normalized. This is trivial to see for the trivial chain whose Markov matrix is the identity, where $\begin{bmatrix} 1 \\ -1 \end{bmatrix}$ is an eigenvector with eigenvalue 1. $\endgroup$ – Ian Apr 17 '15 at 19:07
  • $\begingroup$ @amundi12 In short, the answer to your original questions are: there is always a stationary distribution; there can be infinitely many stationary distributions. For instance in my example $\begin{bmatrix} p/2 \\ p/2 \\ (1-p)/2 \\ (1-p)/2 \end{bmatrix}$ is a stationary distribution for every $p \in [0,1]$. The rest of my answer is examples, caveats, and side remarks. $\endgroup$ – Ian Apr 17 '15 at 19:10
0
$\begingroup$

A (non-zero) steady state vector under a matrix transformation is an eigenvector of the matrix corresponding to an eigenvalue of 1. Any matrix without a unit eigenvalue will not posses a ( non-zero) steady state vector .

an easy example is ...

$ \begin{pmatrix} 2 & 0 \\ 0 & 3 \end{pmatrix} $

which has eigenvalues of 2 and 3.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ This is a little bit misleading in this context, because actually any matrix which is left-stochastic or right-stochastic has a unit eigenvalue. $\endgroup$ – Ian Apr 17 '15 at 18:29
  • $\begingroup$ What matrix does not have an eigenvalue? Or do you mean without any real eigenvalues? $\endgroup$ – amundi12 Apr 17 '15 at 18:35

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.