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

Let $\mathcal{X}=(X_n:n\in\mathbb{N}_0)$ denote a Markov chain with state space $E=\{1,\dots,5\}$ and transition matrix


Compute the probabilities $\mathbb{P}(X_2=5|X_0=1)$ and $\mathbb{P}(X_3=1|X_0=1)$.
Given an initial distribution $\pi=(1/2,0,0,1/2,0)$, compute $\mathbb{P}(X_2=4)$.

I've got the transient states as $1,2,3$. And the recurrent states as $4,5$, and the communication classes I think are $\{1,2,3\}$ and $\{4,5\}$.

1) To calculate $\mathbb{P}(X_2 = 5|X_0 = 1)$, is it just finding $P^2_{(1,5)}$? Which equals $1/8$?

2) For $\mathbb{P}(X_3 = 1|X_0=1)$, I tried finding $P^3_{(1,1)}$ which I got $1/24$. Is that correct?

3) For finding $\mathbb{P}(X_2=4)$, do I just take $π(P^2)$?

share|cite|improve this question
John, I copied the image into the post; please check that I didn’t make any typos in the process. – Brian M. Scott Nov 7 '11 at 7:39
Thanks, perfect! Cheers. – John Southall Nov 7 '11 at 13:48
up vote 2 down vote accepted

The theoretical formulas you suggest are correct. For sparse transition matrices like the one you consider, a simple method is to determine the paths leading to the events one is interested in.

For example, the event that $X_0=1$ and $X_2=5$ corresponds to the unique path $1\to3\to5$, which, conditionally on $X_0=1$, has probability $P(1,3)P(3,5)=\frac18$.

Likewise, the event that $X_0=1$ and $X_3=1$ corresponds to the two paths $1\to1\to1\to1$ and $1\to3\to2\to1$, which, conditionally on $X_0=1$, have respective probabilities $P(1,1)P(1,1)P(1,1)=\frac18$ and $P(1,3)P(3,2)P(2,1)=\frac1{24}$, hence the result is $\frac18+\frac1{24}=\frac16$.

Finally, to evaluate the probability that $X_2=4$, consider that $X_0=1$ or $X_0=4$ hence the three relevant paths are $1\to3\to4$, $4\to4\to4$ and $4\to5\to4$, with respective probabilities $\frac18$, $\frac9{16}$ and $\frac1{20}$, to be weighted by the probabilities that $X_0=1$ or $X_0=4$, hence the final result is $\frac12(\frac18+\frac9{16}+\frac1{20})=\frac{59}{160}$.

share|cite|improve this answer
Thanks Didier, I tried doing your way and I got the same answer! but i think im getting the wrong answer when I do it with this other example below? So I start from X2 and X3, and I get it from: 2->1->2 = 1/3, 2->3->2 = 1/8, 3->1->2 = 1/6. So I weighted it at X0 = 2 and X0 = 3 So I got: (1/3)*(1/3) + (1/3)*(1/8) + (1/6)*(1/6) = 13/72 ================================================== But the solution to this example (see above picture) is 5/16? i.e 0.3125. Am I doing something wrong? Cheers for your help. – John Southall Nov 7 '11 at 13:51
You forgot 1->1->2 and 3->3->2. – Did Nov 7 '11 at 16:35
Ahh okay, thanks so much! Just one quick question -- are my comunnications classes correct? {1,2,3} and {4,5}? or is it {1}, {2}, {3} and {4,5}? – John Southall Nov 7 '11 at 18:09
123 and 45 with 45 closed but not 123. – Did Nov 7 '11 at 20:34
Ahh okay, thanks for all your help. I really appreciate it. Cheers! – John Southall Nov 7 '11 at 21:26

There is also the algorithmic way of computing these probabilities. Using this way there is no need to think about different ways of probability; it is just matrix / vector multiplication and you get all results (and even some more):

$\mathbb{P}(X_2 = 5|X_0 = 1)$: start with a initial-distribution $p_0=(1,0,0,0,0)$, i.e. start at point of time $0$ in state $1$. Compute $p_0 * P^2$. Result vector is:

$$\pmatrix{{{1}\over{4}}&{{1}\over{8}}&{{3}\over{8}}&{{1}\over{8}}&{{ 1}\over{8}}\cr }$$

The result is in the fifth column.

$\mathbb{P}(X_3 = 1|X_0=1)$: same initial-distribution $p_0=(1,0,0,0,0)$, compute $p_0 * P^3$:

$$\pmatrix{{{1}\over{6}}&{{17}\over{96}}&{{7}\over{32}}&{{17}\over{80 }}&{{9}\over{40}}\cr }$$

The result is in the first colunm.

Initial distribution $\pi=(1/2,0,0,1/2,0)$, compute $\mathbb{P}(X_2=4)$: Now initial distribution $\pi$ is given. Compute $\pi * P^2$:

$$\pmatrix{{{1}\over{8}}&{{1}\over{16}}&{{3}\over{16}}&{{59}\over{160 }}&{{41}\over{160}}\cr }$$

The result is in the fourth column.

share|cite|improve this answer

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.