# Looking for an example of a Markov Chain

I am looking for an example of a Markov Chain characterized by, say, 3 by 3 matrix that has more than one eigenvector (say a population distribution of birds, or something). I remember solving a problem where instead of applying a matrix to a given vector $n$ times in a direct way, I would instead break that vector down into a linear combination of the eigenvectors and have the matrix act on them, and just raise the respective eigenvalues to the nth power. This of course requires that the matrix is diagonalizable. Is this compatible with markov chains, or am I mixing the things I did in linear algebra up? I would be glad if you can show me an example of what I am describing.

-
The formulation of your question is dangerously ambiguous: are you interested in stationary distributions or in eigenvectors? If the latter, with the eigenvalue 1 or for any eigenvalue? To the right or to the left? If you are interested in transition matrices with several stationary distributions (aka eigenvectors to the left with nonnegative coordinates and for the eigenvalue 1), any reducible Markov chain will do, for example [[-,-,-]|[0,1,0]|[0,0,1]] where the - are any positive parameters summing to 1. – Did Nov 12 '11 at 9:55

Here is a simple example - consider a square with vertices (0,0),(0,1),(1,0) and (1,1). A fly starts at the origin and hops to one of the two adjacent vertices with probability 1/2. It stays at (1,1) when it reaches that vertex. Lets say we want to find the probability that we are at (1,1) after n hops.

The transition matrix for this Markov chain is

$M = \left[ \begin{array}{ccc} 0 & 1 & 0 \\ 0.5 & 0 & 0.5 \\ 0 & 0 & 1 \end{array} \right]$

where the vertices (0,1) and (1,0) are collapsed into one state by symmetry. The transition matrix after $n$ hops is $M^n$ and our desired probability is the (1,3)rd element of $M^n$. We can decompose $M$ as $M = Q \Lambda Q^{-1}$ where

$Q = \left[ \begin{array}{ccc} \sqrt{\frac{2}{3}} & -\sqrt{\frac{2}{3}} & \sqrt{\frac{1}{3}} \\ \sqrt{\frac{1}{3}} & \sqrt{\frac{1}{3}} & \sqrt{\frac{1}{3}} \\ 0 & 0 & \sqrt{\frac{1}{3}} \end{array} \right]$

and

$\Lambda = \left[ \begin{array}{ccc} \sqrt{\frac{1}{2}} & 0 & 0 \\ 0 & -\sqrt{\frac{1}{2}} & 0 \\ 0 & 0 & 1 \end{array} \right]$

As you describe, $M^n$ can now be computed as $M^n = Q \Lambda^n Q^{-1}$ and the (1,3)rd element of this matrix will give us the answer we want.

-
This Markov chain has a unique stationary distribution. – Did Nov 12 '11 at 9:55

If $A$ is a $3\times3$ matrix with eigenvectors $x,y,z$ belonging to distinct eigenvalues $a,b,c$, respectively, and $v$ is any 3-vector, then

$$A^nv=ra^nx+sb^ny+tc^nz$$

where $r,s,t$ are the coordinates of $v$ with respect to the basis $x,y,z$, that is, where

$$v=rx+sy+tz$$

This is fully compatible with Markov chains, that is, it is quite possible for a stochastic $3\times3$ matrix to have distinct eigenvalues, etc., etc.

Indeed, even if the eigenvectors are not distinct, it may still work; the important condition is that there be a basis consisting of eigenvectors (which is the same thing as the matrix being diagonalizable).

So, is that OK? Do you want an example of a diagonalizable stochastic matrix?

-