2
$\begingroup$

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.

counter-example

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – whuber
    Mar 30, 2020 at 16:52
  • $\begingroup$ @whuber Just added the definition I am using. Hope this clarifies things. $\endgroup$
    – Leonidas
    Mar 30, 2020 at 21:18
  • $\begingroup$ 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? $\endgroup$ Mar 30, 2020 at 23:07
  • $\begingroup$ @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. $\endgroup$
    – Leonidas
    Mar 30, 2020 at 23:50

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ If I'm not mistaken, the counter example I posted below disproves this. I believe the issue with your suggestion is that the new stochastic process defined by combining states 3 and 4 into one does not necessarily satisfy the Markov property. $\endgroup$
    – Leonidas
    Mar 31, 2020 at 16:51
  • $\begingroup$ Leonidas, there's merely a typo here: both sides of the equation should be conditioned on $X_0=2,$ not just the left side. $\endgroup$
    – whuber
    Mar 31, 2020 at 18:00

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.