# Calculating probabilities of an nth step transition matrix for discrete time markov chains

"Let $\{X_n, n \geq 0\}$ be a DTMC with state space $S = \{1, 2, 3, 4, 5\}$ and the following transition probability matrix:

$$P = \begin{pmatrix} 0.1 & 0.0 & 0.2 & 0.3 & 0.4 \\ 0.0 & 0.6 & 0.0 & 0.4 & 0.0 \\ 0.2 & 0.0 & 0.0 & 0.4 & 0.4 \\ 0.0 & 0.4 & 0.0 & 0.5 & 0.1 \\ 0.6 & 0.0 & 0.3 & 0.1 & 0.0 \end{pmatrix}$$

with the initial distribution as:

$$a = \begin{pmatrix} 0.5 & 0 & 0 & 0 & 0.5 \end{pmatrix}.$$

Compute $P(X_2 = 2, X_4 = 5)$"

Also, how do I do this? I'm not even sure what it means. Is this asking me to work out the probability of $X_4 = 5$ given that I have $X_2 = 2$?

EDIT: The matrix is correct. From the previous part of the question (that I didn't post), $P(X_2 = 2) = 0.08$. In the answers, my lecturer uses the Chapman Kolmogorov equations. Does this make the answer any clearer?

EDIT 2: Edited to bump to the top as I have commented on whuber's post with a couple of questions

-
$P(X_2=2,X_4=5)$ is the joint probability of $X_4=5$ and $X_2=2$ not the conditional probability. Also, is this homework? –  jerad Dec 14 '12 at 15:50
It's old homework, so I have the answers, but I don't understand why. The answer to that question is 0.0032. How do you calculate joint probability? –  Kaish Dec 14 '12 at 16:28
$P(A,B) = P(A)P(B)$ –  jerad Dec 14 '12 at 18:11
Using the definition of conditional probability, you'll find that $$P(X_4 = 5, X_2 = 2) = P(X_4 = 5 | X_2 = 2) \cdot P(X_2 = 2)$$ You can get a handle on $P(X_4 = 5 | X_2 = 2)$ using the transition matrix (hint: use $P^2 = P P$) and, since you don't know $X_1$, you have to calculate $P(X_2 = 2)$ using the law of total probability. –  Macro Dec 14 '12 at 18:27
It looks to me like $P(X_2=2)=0$ right? You can only get to state 2 from state 2 or 4 and the probability of being in those states on step 1 is both 0. You should make sure you transcribed your matrix correctly,@Kaish, otherwise I dont see how the answer is 0.0032. –  jerad Dec 14 '12 at 18:30

Here is a graphical representation of the chain, with the vertices $2$ and $5$ highlighted:

The initial state $a$ can be indicated by labeling the vertices with their values, highlighting the nonzero values:

Two transitions from $a$, as computed by the matrix product $a\mathbb{P}\mathbb{P} = a\mathbb{P}^2$, is this distribution:

The weight on vertex $2$ is precisely the chance of reaching $2$ after two steps; that is, it is $\Pr(X_2=2)$. To represent this event, we now zero out all other weights, leaving the distribution $b = (0, 2/25, 0, 0, 0)$. The question asks us to take two more steps, beginning at $b$, computing $b\mathbb{P}\mathbb{P} = b\mathbb{P}^2$:

The labels give the new distribution. All two-step paths from vertex $2$ to vertex $4$ are highlighted. (There is just one, making it easy to compute the new distribution: $2/25$ is multiplied by $p_{2,4}=2/5$, giving $4/125$ for the transition from $2$ to $4$, then that is multiplied by $p_{4,5}=1/10$, yielding $4/1250=2/625$ for the double transition $2\to 4\to 5$. In more complicated situations we would have to examine all possible paths from $2$ to $5$ and add their contributions.)

Evidently, the chance of reaching vertex $2$ at step $2$ and then arriving at vertex $5$ at step $4$ is the final value at vertex $5$, $2/625 = 0.0032$.

-
I'm still coming up with $P(X_2=2)=0$. Consider that $P(X_1) = a = (0.5, 0, 0, 0, 0.5)$. For the second step, we have $P(X_2) = aP$ which is simply the average of row 1 and 5 in $P$, which is $(0.35, 0, 0.25, 0.2, 0.2)$. Why is it that me and mimshot above both get this answer yet you end up with the answer that the OP provided? –  jerad Dec 14 '12 at 22:26
@Jerad you have to interpret $a$ as $X_0$ rather than as $X_1$, that's all. Did you notice the condition "$n\ge 0$" at the very beginning of the question? –  whuber Dec 14 '12 at 22:28
@whuber I have the right answer now. What I did was I had matrix $P$, squaring it gave me the 2nd step matrix and multiplying it with my initial distribution gave me $P(X_2 = 2)$. Then, I said my new "initial distribution" was $b = \begin{pmatrix} 0 & 0.08 &0 &0 &0 \end{pmatrix}$ (like you said) and then I multiplied this by $P^2$ and it gave me the right answer as 0.0032. A few questions, why do I multiply b with $P^2$ and not $P^4$? Let's say I had to work out $P(X_2 = 2, X_3 = 3)$, then how would I do the $X_3$ bit, would I multiply b with just P? –  Kaish Dec 15 '12 at 18:45
That's right. If you multiply $b$ (the state after two transitions) by $\mathbb{P}^4$, you are making four transitions and therefore are computing the distribution reached from $b$ after four transitions: this would be relevant to comparing events at step $2$ and step $6$. –  whuber Dec 15 '12 at 20:58
You've got it. It looks like you're becoming comfortable moving back and forth between the graphical and algebraic representations of the chain. –  whuber Dec 15 '12 at 21:16

It's asking you to work out the probability that $X_2=2$ and $X_4 = 5$.

In general if you know the probability distribution of states at time $t$ is $a_t$ then the distribution at time $t+1$ (i.e., $a_{t+1}) is given by: $$a_{t+1}^T = P * a_t^T$$ Note that having$a$be a column vector would have been simpler since you wouldn't have needed the transpose, but I'm keeping your notation. To find$a$more than one step in advance we keep multiplying by$P$. $$a_{t+2}^T = P^2 * a_t^T$$ $$a_{t+3}^T = P^3 * a_t^T$$ Since we know: $$P(X_4 = 5, X_2 = 2) = P(X_4 = 5 | X_2 = 2) \cdot P(X_2 = 2)$$ We could calculate each of those two probabilities with some matrix multiplication. But note that$P(X_2 = 2) = 0$because$X_1$can only be 1 or 5 and$P_{1,2}=0$and$P_{5,2}=0$Thus the answer is zero. - This is incorrect because you are following a different convention for subscripting the$X$'s: they start at$0$, not$1$. Bear in mind, too, that the convention with Markov chains is to right multiply by the transition matrix. You can always tell which convention is in use by checking the sum-to-unity condition. By multiplying on the left by this$P\$, whose rows sum to unity, you are not computing correctly. –  whuber Dec 14 '12 at 22:31