Calculating probabilities (Markov Chain)

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

$$P=\pmatrix{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}$$

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)$?

-
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

2 Answers

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

-
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? img839.imageshack.us/img839/4981/unled12345.jpg 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.

-