Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 have a Markov chain with state space $E = \{1,2,3,4,5\}$ and transition matrix below:

$$ \begin{bmatrix} 1/2 & 0 & 1/2 & 0 & 0 \\\ 1/3 & 2/3 & 0 & 0 & 0 \\\ 0 & 1/4 & 1/4 & 1/4 & 1/4 \\\ 0 & 0 & 0 & 3/4 & 1/4 \\\ 0 & 0 & 0 & 1/5 & 4/5\ \end{bmatrix} $$

How would I find the conditional probabilities of $\mathbb{P}(X_2 = 5 | X_0 =1)$ and $\mathbb{P}(X_3 = 1 | X_0 =1)$?

I am trying to use the formula (or any other formula, if anyone knows of any) $p_{ij}^{(n)} = \mathbb{P}(X_n = j | X_0 =i)$, the probability of going from state $i$ to state $j$ in $n$ steps.

So $\mathbb{P}(X_2 = 5 | X_0 =1) = p_{15}^2$, so I read the entry in $p_{15}$, and get the answer is $0^2$, but the answer in my notes say it is $1/8$?

Also, I get for $\mathbb{P}(X_3 = 1 | X_0 =1) = p_{11}^3 = (\frac{1}{2})^3 = 1/8$, but the answer says it is $1/6$?

share|cite|improve this question
up vote 0 down vote accepted

The notation $p^{(2)}_{15}$ is not to be confused with the square of $p_{15}$ since it stands for the $(1,5)$ entry of the square of the transition matrix. Thus, $$ p^{(2)}_{15}=\sum_{i=1}^5p_{1i}p_{i5}. $$ Likewise for $p^{(3)}_{11}$, which is the $(1,1)$ entry of the cube of the transition matrix, that is, $$ p^{(3)}_{11}=\sum_{i=1}^5\sum_{j=1}^5p_{1i}p_{ij}p_{j1}. $$ In the present case, there are only two ways to start from $1$ and to be back at $1$ after three steps, either the path $1\to1\to1\to1$, or the path $1\to3\to2\to1$. The first path has probability $\left(\frac12\right)^3=\frac18$ and the second path has probability $\frac12\frac14\frac13=\frac1{24}$, hence $p^{(3)}_{11}=\frac18+\frac1{24}=\frac16$.

share|cite|improve this answer
Thanks Didier! I can get that $p_{15}^{(2)} = 1/6$, but for $p_{11}^{(3)}$ (and for calculations that involve more than 3 steps etc.), is there an easier way to calculate it? – Henry Apr 10 '12 at 23:26
Thanks @Didier, just a quick question, how did you see that there are only 2 ways to start from 1 and be back at 1? Did you use the method as what Julius described? – Henry Apr 10 '12 at 23:53
One looks for the paths $1\to u\to v\to 1$ with positive probability. The first column of the matrix shows that $v=1$ or $v=2$. If $v=1$, one cannot leave $1$ and be back on time (smallest loop of length $3$) hence $u=1$. If $v=2$, one must leave $1$ right away, hence $u=3$. Done. – Did Apr 10 '12 at 23:59
Thanks, understood and most appreciated. :) – Henry Apr 11 '12 at 0:10

I will give not really formal solution, but maybe this will help you too. $P(X_2=5|X_0=1)$ means getting from the state 1, at the moment 0, to the state 5, at the moment 2. So we are allowed to make to make two steps. Final destination - state 5, is column 5, so nonzero probabilities to get there are from states 3,4,5. So the first step must be getting to one of these. Lets check first row - from state 1 we can get only to states 1,3, which leaves us only one way $1\rightarrow 3\rightarrow 5$, with probability $1/2\cdot1/4=1/8$. A bit longer different situation is $P(X_3=1|X_0=1)$, here we have three steps. Thinking in the same way as before there are two ways with probabilities $(1/2)^3$ and $1/3\cdot1/4\cdot1/2$ (sums to $1/6$). Of course Didier's solution is more formal, and it may be worth doing it in this my way only when we have lots of zeros, like in this case (to eliminate possible combinations). This should help you understanding why $p_{15}^2$ doesn't work here - that would mean $1\rightarrow 1\rightarrow 1$, staying in state 1.

share|cite|improve this answer
Thanks Julius, yes your method is also a nice way to see it. Because maybe with many steps, calculating the probabilities using the summation formula Didier provided might take a bit long (still very useful). – Henry Apr 10 '12 at 23:33

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.