How to show it? In other words, I want to show that if $ \{X_n\}$ is a Markov chain then for every $ n\in\mathbb{N} $ and $ 1\le i_1<\dots<i_k\le n $ such that $P(X_{i_1}=x_1,\dots ,X_{i_k}=x_k)>0 $ it holds that $ P(X_{n+1}=x |X_{i_1}=x_1,\dots ,X_{i_k}=x_k)=P(X_{n+1}=x |X_{i_k}=x_k) $

I have tried to prove it by induction on $n$ and by using the formula $ P(X_{n+1}=x|A)= \sum_{a} P(X_n=a|A)P(X_{n+1}=x|A,X_n=a)$ where $A=\{X_{i_1}=x_1,\dots ,X_{i_k}=x_k\}$, but the expression $P(X_{n+1}=x|A,X_n=a)$ isn't any better. Another attempt was to "fill the holes": let $\{j_1,\dots,j_{m}\}=\{1,\dots,n\}\setminus\{i_1,\dots i_k\}$ so $\\ P(X_{n+1}=x|A)=\sum_{b_1,\dots , b_m}P(X_{n+1}=x|A,X_{j_1}=b_1, \dots ,X_{j_m}=b_m)P(X_{j_1}=b_1, \dots ,X_{j_m}=b_m|A) $ but again I didn't know how to deal with the second expression.

  • $\begingroup$ What have you tried? See How to ask a good question. $\endgroup$
    – Ѕааԁ
    Apr 29, 2020 at 13:53
  • $\begingroup$ I added it to the question @Saad $\endgroup$
    – MCL
    Apr 29, 2020 at 16:22

1 Answer 1


Interesting problem. Here are some thoughts.

The usual Markov criterion is that each item depends only on the one before it. That is, its probability distribution is the same regardless of the prior elements:

A series of dots, the last two X_n and X_n+1, with a dotted line walling off the prior dots

Your problem is slightly different. You have deleted some elements from the sequence, and you want to prove that the next element depends only on the last element not deleted:

Similar, but some dots have been grayed out

One case to consider is where $i_k = n$:

Similar, but last not-grayed-out dot is second-to-last dot

See if you can prove it for that case first. Once you have proven it for $i_k = n$, consider a case where $n$ is a little ahead of $i_k$, that is, where $i_k + m = n$ for some $m$:

Similar, but now the last not-grayed-out dot is some steps away from the last dot

  • $\begingroup$ I still can't see how to use the assumption $i_k = n$ $\endgroup$
    – MCL
    Apr 30, 2020 at 6:09
  • $\begingroup$ @MCL Try the simplest case of $k = 2$, $i_k = n = 3$, and "fill the holes" as you suggest in your question. $\endgroup$
    – Owen
    May 2, 2020 at 16:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.