# A subsequence of a Markov chain is a Markov chain

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

• What have you tried? See How to ask a good question.
– Ѕааԁ
Apr 29, 2020 at 13:53
– MCL
Apr 29, 2020 at 16:22

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: 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: One case to consider is where $$i_k = n$$: 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$$: • I still can't see how to use the assumption $i_k = n$
– MCL
Apr 30, 2020 at 6:09
• @MCL Try the simplest case of $k = 2$, $i_k = n = 3$, and "fill the holes" as you suggest in your question.
– Owen
May 2, 2020 at 16:24