4
$\begingroup$

I'm reading through my textbook, Introduction to Stochastic Processes (Lawler), before the semester begins in hopes of getting ahead, and I've run into something I just plain cannot figure out: How to compute the invariant probability vector for a transition matrix. I was hoping that one (or many) of you would be able to walk me through how you would do this for just a simple matrix:

$$\begin{bmatrix} .4&.2&.4 \\\\ .6&0&.4 \\\\ .2&.5&.3 \end{bmatrix}$$

I know that you can compute it by raising the matrix to a large power, but this practice problem says to "compute the invariant probability vector as a left eigenvector." How would one go about doing this?

Thanks for your help!

  • 0
    Invariant: matrix operation on $\mu$ still gives $\mu$.2012-08-12

3 Answers 3

8

If the transition matrix is $A$ and the probability vector is $\mu$, "invariant" means that $\mu A = \mu$. Another way of saying this is that $\mu$ is a left eigenvector of $A$ with eigenvalue 1.

$\mu A = \mu$ is really just a system of linear equations. If we write $\mu = [\mu_1, \mu_2, \mu_3]$ then we have $$[\mu_1, \mu_2, \mu_3] \begin{bmatrix} .4&.2&.4 \\\\ .6&0&.4 \\\\ .2&.5&.3 \end{bmatrix}= [\mu_1, \mu_2, \mu_3]$$ or in other words $$\begin{align*} .4 \mu_1 + .6 \mu_2 + .2 \mu_3 &= \mu_1 \\ .2 \mu_1 + 0 \mu_2 + .5 \mu_3 &= \mu_2 \\ .4 \mu_1 + .4 \mu_2 + .3 \mu_3 &= \mu_3. \end{align*} $$ Since $\mu$ is to be a probability vector we also have to have $$\mu_1 + \mu_2 + \mu_3 = 1.$$ So you have a system of 4 linear equations in 3 unknowns. Now you just have to solve this system.

  • 0
    Ahh this makes so much more sense now. Thank you!2012-08-12
  • 2
    Note that the first three equations are linearly dependent since the sum of each row of the matrix is $1$, so you can take any two of those three plus the fourth equation, and solve $3$ equations in $3$ unknowns.2012-08-13
1

It means, find a vector $v$ with the following properties: all entries between 0 and 1, entries add up to 1, and $vA=v$ (where $A$ is your transition matrix).

If you know how to find (left) eigenvectors, you just find one for the eigenvalue 1, and then normalize it so the sum of the entries is 1.

  • 0
    The first part of your response makes sense, but before reading this book I'd never heard the term *left* eigenvector. I took Linear Algebra a year ago so I can find the eigenvalue, but I couldn't tell you how to find the left eigenvector.2012-08-12
  • 1
    @JackRadcliffe: You probably know how to find *right* eigenvectors: a column vector $v$ such that $Av = \lambda v$ (here $\lambda = 1$). A left eigenvector is a row vector such that $vA = \lambda v$. And if you know how to find right eigenvectors (for instance, with your favorite software), then just note that the left eigenvectors of $A$ are just (the transposes of) the right eigenvectors of the transpose of $A$.2012-08-13
  • 0
    Yep, that's exactly what I know how to do. You've been very helpful; thanks again!2012-08-13
-1

If T is the transistion probability matrix the stationary (or invariant) distribution satisfies the matrix equation

P(X)= T P(X)

  • 0
    I think you mean $P(X) T$?2012-08-12
  • 0
    Whichever way the matrix multiplication works.2012-08-12
  • 0
    @NateEldredge I take the vector P(X) to be a 3x1 column vector whereas you take it to be a 1x3 row vector. I think mine is actually more conventional.2012-08-13
  • 1
    No, it's more than that. The left eigenvectors of $T$ are different from its right eigenvectors. (They are not just transposes of each other; compute them if you like. In particular, the right eigenvector of eigenvalue 1 isn't positive in this case.) The left eigenvectors of eigenvalue 1 correspond to invariant measures, and the right eigenvectors correspond to harmonic functions for the chain. It's essential to keep them straight.2012-08-13
  • 0
    So if you insist on taking $P(X)$ to be a column vector, then you have to replace $T$ by its transpose.2012-08-13
  • 0
    No 3x1 =3x3 times 3x12012-08-13
  • 1
    We're not understanding one another. I'm talking about a row vector $v$ (1x3) satisfying $vT = v$. These are **different** from the column vectors $w$ (3x1) which satisfy $Tw = w$. I really mean different; they have numerically different entries. And the former are what is needed to solve this problem, while the latter are what you are talking about.2012-08-13
  • 0
    Yes, so I am talking about w=Tw. But given the way the OP presents the transition probability matrix, how do you know that you are interpreting the rows and column's correctly? I can agree that to be consistent one of us needs to use the transpose of the transition matrix that the other is using.2012-08-13
  • 1
    The standard presentation is that the entry in row $i$ and column $j$ is the probability of transitioning from $i$ to $j$. This is consistent with the matrix in the question; note that its rows sum to 1 while its columns do not. (Indeed, because of this the right eigenvectors will all be of the form $(c,c,c)^T$, which doesn't contain much useful information.)2012-08-13
  • 1
    My experience is that mathematicians generally set up their stochastic processes with columns summing to 1 and $Av=v$ (like Michael), whereas statistics/economics people have rows summing to 1 and $vA=v$ (like OP). Causes some confusion when the two try to talk to each other.2012-08-13