Proving (or disproving) a property for Markov Chains

Question

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.

Answer 1

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

This follows directly from the Markov property. You are getting hung up here on your numbering, which is just splitting a single event into multiple disjoint events. Once you treat the larger event as the state of interest, the result you are trying to prove becomes a direct statement of the Markov property.