# How can I find the initial state vector of a Markov process, given a stochastic matrix, using eigenvectors? And when there are negative eigenvalues?

Given a stochastic matrix, M, and the knowledge that a steady state exists in the process, can I find the initial state vector as a linear combination of the eigenvectors associated with that matrix? If so, which theorem or rule allows me to do that?

What happens if said matrix has a negative eigenvalue? Apparently, I can't use the eigenvector associated with an eigenvalue of -1 to find the initial state vector (why?), but is this a general rule for every negative eigenvalue or only -1?

I can't find this anywhere!

For example, given the matrix:

$\begin{bmatrix} \frac{1}{4} & \frac{1}{2} & \frac{1}{2} & \frac{1}{2} \\ \frac{1}{4} & \frac{1}{2} & 0 & 0 \\ \frac{1}{4} & 0 & \frac{1}{2} & 0 \\ \frac{1}{4} & 0 & 0 & \frac{1}{2} \end{bmatrix}$

The eigenvalues (represented by $\lambda$) are:

$\lambda_{1}=1, \lambda_{2}=\frac{1}{2}, \lambda_{3}=\frac{1}{2}; \lambda_{4}=-\frac{1}{4}.$

And the eigenvectors (represented by $v_{\lambda }$) for the positive eigenvalues:

$v_{1}=(2, 1,1,1); v_{\frac{1}{2}}= {(0,-1,0,1), (0,-1,1,0)}$

So, is it correct to write the initial state vector $X_{0}$ as a linear combination of the eigenvectors of the non-negative eigenvalues?:

$X_{0}=\alpha (2,1,1,1)+ \beta (0,−1,0,1) + \gamma (0,−1,1,0)$

• The whole point of the Markov property is that it’s memoryless. – amd Jul 11 '18 at 19:16

A steady state is represented by a vector $v$ with $Mv=v$. That's the same as an eigenvector with eigenvalue $\lambda=1$. (So in that example the steady state vectors are exactly the scalar multiples of $v_1$.)

The question of how you "find" the initial state doesn't make much sense - the initial state can be anything. Yes, if M is diagonalizable then you can write the initial state as a linear combination of eigenvectors. This is more or less by definition: An $n\times n$ matrix is diagonalizatble if and only if the eigenvectors span $\Bbb R^n$. Whether the eigenvalues are all positive is irrelevant to this.

A second ago I said I thought $-1$ could not be an eigenvalue. That was wrong; $M=\begin{bmatrix}0&1\\1&0\end{bmatrix}$ is a counterexample.

If you have a process $v_k=M^kv_0$, if $M$ is diagonalizable and if $v_k\to v$ then yes, the initial vector must be a linear combination of eigenvectors for eigenvalues $\lambda\ne1$. This is clear, because if $$v_0=\sum_ja_jw_j$$where $w_j$ is an eigenvector with eigenvalue $\lambda_j$ then $$v_o^k=\sum_j a_j\lambda_j^kw_j,$$and $(-1)^k$ does not converge as $k\to\infty$. (Other negative eigenvales of modulus less than $1$ are no problem; if $-1<\lambda<0$ then $\lambda^k\to0$.)

• I meant the initial state, not the steady state. I edited it now, thanks. – Mai Len Jul 11 '18 at 16:53
• Thank you for answering. What if I have a situation where I know the stochastic matrix, and I know a steady state exists, but I don't know the initial state and I want to know how it looks like. Would the sign of the eigenvalues still be irrelevant in this case? – Mai Len Jul 11 '18 at 17:41
• @MaiLen I already answered this! If you don't know the initial state you don't know the initial state, period. You cannot "find" the initial state, or determine how it looks like, because the initial state can be anything. (That is, you cannot determine anything about the initial state given $M$; if you have other information about the process that may be different.) – David C. Ullrich Jul 11 '18 at 17:49
• Your new edit is very helpful, thank you very much for taking the time to answer. I still think it makes sense to "find" an initial state (since it can't be anything in some cases), but the rest of your reply answered my question perfectly. – Mai Len Jul 11 '18 at 18:48
• @MaiLen I was confused. We know that $\lambda=1$ must be an eigenvalue of $M$: I was stupidly concluding that the process must have a stationary state, so that "if a steady state exists" change nothing. – David C. Ullrich Jul 11 '18 at 18:52