# Solving Discrete Markov Chain with diagonal band matrix.

I am trying to model a certain process as a Discrete Markov Chain. My system has $N+1$ states: $X=0, \ldots N$, and I can assume that the $(N+1)\times (N+1)$ transition matrix $T$ has the general form

$$T=\left( \begin{matrix} 1 - p_0 & p_0 & 0 & \cdots & \cdots&\cdots & 0 \\ 0 & 1-p_1 & p_1 & 0 & \cdots & \cdots& 0 \\ 0 & 0 & \ddots & \ddots & 0 & \cdots&0 \\ 0 & 0 & 0 &1-p_n & p_n & 0 & 0 \\ 0 & \cdots & \cdots & 0 & \ddots & \ddots&0 \\ 0 & \cdots & \cdots & \cdots & 0 & 1-p_{N-1}&p_{N-1} \\ 0 & \cdots & \cdots & \cdots & \cdots & 0 &1 \\ \end{matrix} \right)$$

where the $p_n$ are estimated from experimental data, and in principle (though it is unlikely) for some $j$ it might be $p_j=0$ or $p_j = 1$.

What I am interested for my evaluation in is the expected value of the distribution at the $m-$th step, $m \le N$, assuming that my process start from state $X=0$.

I am new to the study of Markov chains, so I'd like some advices on how to proceed correctly. And possibly some smart trick to solve the chain.

As far as I have understood I have to evaluate $T^m$. The first row of $T^m$ is then the distribution of probability at m-th time step assuming that my process starts from the state $X=0$.

The particular structure of the matrix would help me in solving the calculations? How to treat the cases $p_j=0$ and $p_j=1$?

Thanks a lot for the advices and help!

-

Diagonalize T with the diagonal matrix D and change of basis matrix C. To find the diagonal matrix D, find the eigenvalues of T, then D is the diagonal matrix with its entries as its eigenvalues. Then matrix C has its columns as the eigenvectors of T.

Then you'll have T = C*D*C^-1. Then T^m=(C*D*C^-1)*(C*D*C^-1)...(C*D*C^-1) (you're multiplying C*D*C^-1 by itself m times. Observing the left side we see be associativity C*D*(C^-1*C)D(C^-1*C)*...(C^-1*C)*D*C^-1 Therefore we have the Identity matrix in every parenthesis and we have T^m = C*D^m*C^-1 which is a standard result for any diagonalizable matrix T.

-
thanks. If I remind correctly, for the particular matrix under consideration, the eigenvalues correspond to the entries on the main diagonal. If for some $j$, $p_j = 1$ I might have then a 0 eigenvalue, and the T matrix would not be diagonalizable. What should I do then? –  lucacerone Sep 24 '12 at 10:39
Doesn't matter, you can have 0 as an eigenvalue for a matrix T and it is still diagonalizable –  Jonathan Brown Sep 24 '12 at 11:07
Do you honestly believe an upper triangular matrix may be diagonalized? –  Did Sep 24 '12 at 11:41
Yes I do, do you not? –  Jonathan Brown Sep 24 '12 at 12:17
1 2, 0 2 (a 2X2 matrix reading row 1, row 2) is upper diagonal with eigenvalues 2 and 1 with eigenvectors <1,0> and <2,1>! now please unreject my comment –  Jonathan Brown Sep 24 '12 at 12:24