Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question

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

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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