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!


1 Answer 1


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$.

  • $\begingroup$ 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? $\endgroup$
    – lucacerone
    Sep 24, 2012 at 10:39
  • $\begingroup$ Doesn't matter, you can have 0 as an eigenvalue for a matrix T and it is still diagonalizable $\endgroup$ Sep 24, 2012 at 11:07
  • $\begingroup$ Do you honestly believe an upper triangular matrix may be diagonalized? $\endgroup$
    – Did
    Sep 24, 2012 at 11:41
  • $\begingroup$ Yes I do, do you not? $\endgroup$ Sep 24, 2012 at 12:17
  • 2
    $\begingroup$ 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 $\endgroup$ Sep 24, 2012 at 12:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.