For a Markov chain $\lbrace X_n, n\ge0\rbrace$ with transition probabilities $P_{i,j}$, consider the conditional probability that $X_n = m$ given that the chain started at time $0$ in state $i$ and has not entered state $r$ by time $n$, where $r$ is a specified state not equal to either $i$ or $m$. We are interested in whether this conditional probability is equal to the $n$ stage transition probability of a Markov Chain whose state space does not include state $r$ and whose transition probabilities are

$$Q_{i,j} = \frac{P_{i,j}}{1 - P_{i,r}}, i,j \neq r$$

We want to either prove the equality

$$P\lbrace X_n = m \mid X_0 = i, X_k \neq r, k = 1,\dots, n\rbrace = Q_{i,m}^n$$

or provide a counter example.

Initially I thought that the two quantities are equal, but later I was able to find a counterexample, but still is not able to get the intuition behind the two quantities not being equal.

  • 1
    $\begingroup$ That is the usual catch with conditioning. Imagine 3 states: i,r,m where the probability to go from i to r is 0, to stay at i 1/2, to move from i to m 1/2 and to move from m to r very high but to stay at m very low. Also, there is no chance to return to i from m. Then the dominating process that moves from i to m bypassing r in the original chain stays at i all the time and moves to m only at the very last step, which puts the conditional chance to end at m at the same level as to stay at i (near 1/2). However, in the chain with r removed, you end at m with probability very close to 1. $\endgroup$
    – fedja
    Commented Dec 25, 2012 at 5:11
  • $\begingroup$ To make it a layman example, imagine that you flip a coin at every moment and, depending on the result, either stay where you are, or go to the adjacent room. However, once you enter that room, at the next moment almost surely a big dinosaur enters and eats you. What is your chance to be in the next room at the moment n under the condition that you are still alive? I don't think it takes much intuition to believe that it's not very close to 1 no matter how large n is. Now, remove the dinosaur from the picture altogether. The process feels somewhat different now, doesn't it? $\endgroup$
    – fedja
    Commented Dec 25, 2012 at 5:30
  • $\begingroup$ @fedja: I am convinced with neither of your explanation. Can you elaborate in the form of an answer ? $\endgroup$
    – aaaaaa
    Commented Dec 25, 2012 at 12:16
  • $\begingroup$ @Prasenjit - the intuitive idea is that conditioning on not entering state $r$ makes the Markov chain less likely to move closer'' to $r$. Here closer'' should be understood metaphorically and not necessarily literally in terms of graph distance. $\endgroup$
    – user21162
    Commented Dec 25, 2012 at 23:00
  • $\begingroup$ @prasenijt Elaborate on what? The formal computation in my example is totally trivial and robinson1 made the intuition behind it as transparent as I could possibly do it myself... $\endgroup$
    – fedja
    Commented Dec 30, 2012 at 3:23


Your Answer

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

Browse other questions tagged or ask your own question.