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.
 A: 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.
A: 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?
