5
$\begingroup$

"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

Improve this question
$\endgroup$
8
  • $\begingroup$ $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? $\endgroup$
    – jerad
    Commented Dec 14, 2012 at 15:50
  • 1
    $\begingroup$ 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? $\endgroup$
    – Kaish
    Commented Dec 14, 2012 at 16:28
  • $\begingroup$ $P(A,B) = P(A)P(B)$ $\endgroup$
    – jerad
    Commented Dec 14, 2012 at 18:11
  • 1
    $\begingroup$ 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. $\endgroup$
    – Macro
    Commented Dec 14, 2012 at 18:27
  • $\begingroup$ 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. $\endgroup$
    – jerad
    Commented Dec 14, 2012 at 18:30

2 Answers 2

Reset to default
5
$\begingroup$

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

figure 1

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

figure 2

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

figure 3

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

figure 4

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

Improve this answer
$\endgroup$
6
  • $\begingroup$ 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? $\endgroup$
    – jerad
    Commented Dec 14, 2012 at 22:26
  • 1
    $\begingroup$ @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? $\endgroup$
    – whuber ♦
    Commented Dec 14, 2012 at 22:28
  • $\begingroup$ @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? $\endgroup$
    – Kaish
    Commented Dec 15, 2012 at 18:45
  • $\begingroup$ 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$. $\endgroup$
    – whuber ♦
    Commented Dec 15, 2012 at 20:58
  • 1
    $\begingroup$ You've got it. It looks like you're becoming comfortable moving back and forth between the graphical and algebraic representations of the chain. $\endgroup$
    – whuber ♦
    Commented Dec 15, 2012 at 21:16
0
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – whuber ♦
    Commented Dec 14, 2012 at 22:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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