Calculating $\mathbb{P}(X_{12} = 1, X_{13} = 2 \mid X_{10} = 4, X_7 = 3)$ for Markov chain

Question

Let $(X_n)_{n \ge 0}$ being a time-homogeneous discrete time Markov chain with state space $S = \{1, 2, 3, 4, 5\} $ and one step transition matrix $P$ give by

$$ P = \begin{bmatrix} 0 & \frac{3}{8} & \frac{3}{8} & 0 & \frac{1}{4} \\ 0 & \frac{1}{2} & 0 & \frac{1}{2} & 0 \\ \frac{2}{3} & 0 & 0 & 0 & \frac{1}{3} \\ 0 & \frac{1}{4} & \frac{1}{4} & 0 & \frac{1}{2} \\ \frac{1}{2} & \frac{1}{2} & 0 & 0 & 0 \end{bmatrix} $$

My question is how do you calculate $\mathbb{P}(X_{12} = 1, X_{13} = 2 \mid X_{10} = 4, X_7 = 3)$?

I know how to calculate probabilities like $\mathbb{P}(X_2 = 1 \mid X_0 = 4)$ but unsure what to do when $X_0$ isn't specified. I have attempted to expand the conditional probability using $$ \mathbb{P}(A \cap B \mid C) = \mathbb{P}(A \mid B \cap C)\mathbb{P}(B \mid C) $$ then applying the Markov property. However, I'm unsure if I can even use the Markov property here. The definition of the Markov property that we have been given is

$$ \mathbb{P}(X_{n+1} = x_{n+1}|X_n = x_n,...X_2 = x_2,X_1 = x_1,X_0 = x_0) = \mathbb{P}(X_{n+1} = x_{n+1}|X_n = x_n) $$ for any $n \in \mathbb{N}$ and any $x_0,x_1,x_2,...x_n,x_{n+1} \in S$

which doesn't fit my problem since my conditional doesn't start at $X_0 = x_0$. Any help with this question would be greatly appreciated.

Answer 1

Yes! That's a way to proceed. In general, an event's probability will depend only in its present state, even if you are not conditioning by the entire sequence of states the chain went through before attaining your present state.

You will be able to prove a stronger Markov property, that states that $(X_{n+m})_n$ conditioned on $X_m=x_m$ will be a Markov Chain with transition probability matrix $P$ (just as $(X_n)_{n\in\mathbb{N}}$) starting on $X_m=x_m$ which is independent of $X_0,\dots,X_{m-1}$, given $\{X_m=x_m\}$. This lets you formalize the above intuition.

This property is proven in Chapter $1$ of Norris' book titled "Markov Chains" where he defines the usual Markov property as stated in the question and then proves as a theorem this stronger version (see theorem 1.2).

Indeed, we will have that $X_7$ is not relevant, as we know $X_{10}$ so the stronger Markov property tells us that $X_7=x_7$ is independent of the chain from time step $10$ wheb conditioning to the event $X_{10}=4$: $$ \mathbb{P}(\{X_{12}=1, X_{13}=2\}|\{X_{10}=4, X_{7}=3\}) \\ = \frac{\mathbb{P}(\{X_{12}=1, X_{13}=2, X_{10}=4, X_{7}=3\})}{\mathbb{P}(\{X_{10}=4, X_{7}=3\})} \\ = \frac{\mathbb{P}(\{X_{12}=1, X_{13}=2, X_{7}=3\}|\{X_{10}=4\})\mathbb{P}(\{X_{10}=4\})}{\mathbb{P}(\{X_{10}=4, X_{7}=3\})} \\ = \frac{\mathbb{P}(\{X_{12}=1, X_{13}=2\}|\{X_{10}=4\})\mathbb{P}(\{X_{7}=3\}|\{X_{10}=4\})\mathbb{P}(\{X_{10}=4\})}{\mathbb{P}(\{X_{10}=4, X_{7}=3\})} \\ = \mathbb{P}(\{X_{12}=1, X_{13}=2\}|\{X_{10}=4\}). $$

Now, one can use the stronger Markov property again to let time $t=10$ be the initial time, if only to make the following less mysterious - this is just saying that $(Y_m=X_{10+m})_m$ is a Markov chain with the same transition probabilities as the original but starting at $Y_0=X_{10}=4$. I will not change the variables $X$ to $Y$ so as not to overcomplicate the notation: $$ \mathbb{P}(\{X_{12}=1, X_{13}=2\}|\{X_{10}=4\}) = \mathbb{P}(\{X_{2}=1, X_{3}=2\}|\{X_{0}=4\}) $$ Lastly, we can just restrict ourselves to measure the probability of all trajectories in the state space that at time step $2$ are at state $1$ and at time step $3$ are at state $2$. Those are: $$ 4\to x\to 1\to 2 $$ where $x$ is a state. Note that since $P_{4,x}>0$ only for $x\in \{2,3,5\}$ we can just restrict our attention to those paths.

Then $$ \mathbb{P}(\{X_{2}=1, X_{3}=2\}|\{X_{0}=4\}) = P_{4,2}P_{2,1}P_{1,2} + P_{4,3}P_{3,1}P_{1,2} + P_{4,5}P_{5,1}P_{1,2} \\ = \frac{1}{4}0\frac{3}{8} + \frac{1}{4}\frac{2}{3}\frac{3}{8} + \frac{1}{2}\frac{1}{2}\frac{3}{8} \\ = 0 + \frac{1}{16} + \frac{3}{32} \\ = \frac{5}{32}. $$

There is one key observation here, which is that the last probability is equal to the sum of each path's probability. This can be proven by the fact that $$ \mathbb{P}(\{X_n=x_n,\dots,X_1=x_1\}|\{X_0=x_0\}) = P_{x_0,x_1}\cdots P_{x_{n-1},x_n},$$ which can be proven by iteratively conditioning on the past and applying the Markov property stated in the question, and the following calculation: $$ \mathbb{P}(\{X_{2}=1, X_{3}=2\}|\{X_{0}=4\}) = \sum_{x} \mathbb{P}(\{X_{1}=x, X_{2}=1, X_{3}=2\}|\{X_{0}=4\}) \\ = P_{4,2}P_{2,1}P_{1,2} + P_{4,3}P_{3,1}P_{1,2} + P_{4,5}P_{5,1}P_{1,2}. $$

I hope this helps, or otherwise let me know!

Answer 2

I think I have the answer but would still appreciate if someone would check it over. As I stated in the question we can expand the conditional probability as follows

$$ \mathbb{P}(X_{12} = 1, X_{13} = 2 \mid X_{10} = 4, X_7 = 3) = \mathbb{P}(X_{13} = 2 \mid X_{12} = 1, X_{10} = 4, X_7 = 3)\times \mathbb{P}(X_{12} = 1 \mid X_{10} = 4, X_7 = 3) $$

Then by the Markov property it can be simplified

$$ \mathbb{P}(X_{13} = 2 \mid X_{12} = 1, X_{10} = 4, X_7 = 3) = \mathbb{P}(X_{13} = 2 \mid X_{12} = 1) \\ \mathbb{P}(X_{12} = 1 \mid X_{10} = 4, X_7 = 3) = \mathbb{P}(X_{12} = 1 \mid X_{10} = 4) \\ $$ $$ \mathbb{P}(X_{12} = 1, X_{13} = 2 \mid X_{10} = 4, X_7 = 3) = \mathbb{P}(X_{13} = 2 \mid X_{12} = 1) \times \mathbb{P}(X_{12} = 1 \mid X_{10} = 4) $$

and finally by time-homogeneity

$$ \mathbb{P}(X_{13} = 2 \mid X_{12} = 1) = \mathbb{P}(X_1 = 2 \mid X_0 = 1) = \frac{3}{8} \\ \mathbb{P}(X_{12} = 1 \mid X_{10} = 4) = \mathbb{P}(X_2 = 1 \mid X_0 = 4) = \frac{5}{12} $$

thus giving us $\mathbb{P}(X_{12} = 1, X_{13} = 2 \mid X_{10} = 4, X_7 = 3) = \frac{5}{32}$