Checking whether a given formula is correct for a homogeneous Markov chain

Question

I am new to cross validated so I hope my question belongs here. I saw in a paper where I study someone claiming the following:

Given a $ \{ X_n \}_{n=0}^{\infty} $ be a homogeneous Markov chain (the transition probabilities are independent of the time) with a probability matrix P. We have a specific state $ j $ and we know $ P(X_0=j)=1 $. It is claimed the following holds:

$ P(X_{n+i}=j| X_{n+i-1} \neq j ... X_{n+1} \neq j , X_n=j) =\sum_{l \neq j} P(X_{n+i}=j| X_{n+i-1} = l \space , \space X_{n+i-2} \neq j \dots X_{n+1} \neq j \space , \space X_n=j) $

My thoughts were that this is generally not true as the conditional law of total probability each term has to be multiplied by $ P(X_{n+i-1}=l|X_{n+i-1} \neq j ,X_{n+i-2}\neq j ... X_n=j)$ but maybe due to Markov property it is different or I have a mistake? I just wanted to ask the community and I thank all kind helpers.

Answer 1

From my understanding of that probability, it is asking that given that you are in state $j$ at time $n$ ($X_n = j$), what is the probability that you will be in state $j$ at time $n+i$ ($X_{n+i} = j$) given that you do not go through state $j$ at any time in between.

If we were to have the probability: $P(X_{n+i} = j | X_{n+i-1} = x_{n+i-1}, ... , X_n = x_n $), then due to the Markov Property we would have the above equation equalizing to $P(X_{n+i} = j | X_{n+i-1} = x_{n+i-1})$.

But because of the fact that we are focusing on an initial start point at time $n$ and other conditions in between, you are certainly right in the sense that we have to multiply the probabilities.

But the equation you have mentioned is also correct and that is because there may be many different ways to from state $j$ at time $n$ to state $j$ at time $n+i$ while not going through state $j$ while you are in time $n+1$ to time $n+i-1$.

The best way to describe what I mean is through the Markov Chain below. Say you want to calculate the probability $P(X_2 = G | X_0 = A)$, then from the diagram you see that there several ways 4 different transitions that match that probability:

• ATG
• AGG
• ACG
• AAG

(where ATG means $P(X_2 = G | X_1 = T, X_0 = A)$, which can also be calculated by multiplying the transition probabilities $0.2*0.05 = 0.01$).

Adding all 4 probabilities gives you the answer to $P(X_2 = G | X_0 = A)$, and if you apply the same logic to your original question you will come to the same answer.

Hope that helped!