# 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 = CDC^{-1}$. Then $T^m=(CDC^{-1})(CDC^{-1})\cdots(CDC^{-1})$ (you're multiplying $CDC^{-1}$ by itself m times. Observing the left side we see be associativity $CD(C^{-1}C)D(C^{-1}C)\cdots(C^{-1}C)DC^{-1}$ Therefore we have the Identity matrix in every parenthesis and we have $T^m = CD^mC^{-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