# Proving (or disproving) a property for Markov Chains

I have to prove or disprove the following: Let $$X_n$$ be a Markov Chain on state space $$S = \{1,2,3,4,5,6\}$$. Then $$P(X_2 = 6 | X_1 \in \{3,4\}, X_0 = 2) = P(X_2 = 6 | X_1 \in \{3,4\}).$$

This statement seems like it should be obviously true but I'm having some trouble actually proving it. My strategy has been to simply manipulate each side using basic properties of conditional probability, as well as the Markov property. I've written the LHS as follows: \begin{align*} & \quad \; P(X_2 = 6 | X_1 \in \{3,4\}, X_0 = 2 ) \\[5pt] &= \frac{P(X_2 = 6, X_1 \in \{3,4\}, X_0 = 2 )}{P(X_1 \in \{3,4\}, X_0 = 2)} \\[5pt] &= \frac{P(X_2 = 6, X_1 = 3, X_0 = 2) + P(X_2 = 6, X_1 = 4, X_0 = 2)}{P(X_1 = 3, X_0 = 2) + P(X_1 = 4, X_0 = 2)} \\[5pt] &= \frac{P(X_2 = 6 | X_1 = 3, X_0 = 2) P(X_1 = 3, X_0 = 2) + P(X_2 = 6 | X_1 = 4, X_0 = 2) P(X_1 = 4, X_0 = 2)}{P(X_1 = 3, X_0 = 2) + P(X_1 = 4, X_0 = 2)} \\[5pt] &= \frac{P(X_2 = 6 | X_1 = 3) P(X_1 = 3, X_0 = 2) + P(X_2 = 6 | X_1 = 4) P(X_1 = 4, X_0 = 2)}{P(X_1 = 3, X_0 = 2) + P(X_1 = 4, X_0 = 2)}. \end{align*}

And for the RHS: \begin{align*} P(X_2 = 6 | X_1 \in \{3,4\}) &= \frac{P(X_2 = 6, X_1 \in \{3,4\})}{P(X_1 \in \{3,4\})} \\[5pt] &= \frac{P(X_2 = 6, X_1 = 3) + P(X_2 = 6, X_1 = 4)}{P(X_1 = 3) + P(X_1 = 4)}. \end{align*}

But I still don't see how to show that the LHS and RHS are equal. Am I on the right track? Any help/hints would be appreciated.

Edit: The "Markov Property" to which I am referring is: $$P(X_{n+1} = i_{n+1} |X_n = i_n, X_{n-1} = i_{n-1}, \ldots, X_{1} = i_1) = P(X_{n+1} = i_{n+1} | X_n = i_n)$$

It turns out (rather surprisingly) that $$P(X_2 = 6 | X_1 \in \{3,4\}, X_0 = 2) \neq P(X_2 = 6| X_1 \in \{3,4\})$$. See my counter example below.

• According to many standard statements of the Markov property, such as on Wikipedia, there's nothing to prove: just apply the definition. Please edit your post, then, to include a clear statement of your definition of this property.
– whuber
Commented Mar 30, 2020 at 16:52
• @whuber Just added the definition I am using. Hope this clarifies things. Commented Mar 30, 2020 at 21:18
• Agree with @whuber. This is trivial under the Markov property, which you have provided to us. You shouldn't have to do that type of factorization to show it. In plain English, the Markov property essentially states "the configuration of your current state depends ONLY on the configuration of the previous state." Does this make sense? Commented Mar 30, 2020 at 23:07
• @tchainzzz I don’t see how this immediately follows from the definition I provided. The Markov property in my OP involves a probability conditioned on a particular state, whereas the LHS of the statement I’m trying to prove is a probability conditioned on a set of states. Commented Mar 30, 2020 at 23:50

The simplest proof here is just to combine states $$3$$ and $$4$$ to treat them as a single state. Combining these two states into a single state (called, say, $$3\text{-}4$$) does not remove the Markov property, so we have:
$$\mathbb{P}(X_2 = 6 | X_1 = 3\text{-}4, X_0 = 2) = \mathbb{P}(X_2 = 6 | X_1 = 3\text{-}4).$$
• Leonidas, there's merely a typo here: both sides of the equation should be conditioned on $X_0=2,$ not just the left side.