Given that $(X_n)_{n\geq 0}$ is a Markov Chain, prove that $(X_{kn})_{n\geq 0}$ is a Markov Chain

Question

Given that $(X_n)_{n\geq 0}$ is a Markov Chain, prove that $(X_{kn})_{n\geq 0}$ is a Markov Chain.

I don't know what this exercise has been so difficult for me, I've been playing around with the definition and its consequences for a while a now without being able to prove it:

By definition I know that $P(X_{n+1}\;|\;X_0,...,X_n)=P(X_{n+1}\;|\;X_n)$, and I want to show that $P(X_{k(n+1)}\;|\;X_0,...,X_{kn})=P(X_{k(n+1)}\;|\;X_{kn})$. Is there an elementary way just using this information and just basic knowledge of how to algebraically manipulate conditional probabilities, to prove what I want to prove? Or do I need more information about Markov chains to do this problem?

Answer 1

If $A$ is the stochastic matrix for the given Markov chain, then $A^k$ is the matrix for the subsequence in question. Why is $A^k$ also a stochastic matrix?

---

Alternatively, show by induction that for a Markov chain $$ P(X_{n+1}|X_{i_1},\ldots ,X_{i_k})=P(X_{n+1}|X_i)$$ where $0\le i_1,\ldots, i_k\le n$ and $i=\max\{i_1, \ldots, i_k\}$.

Answer 2

A good first step when doing a maths problem is to write down what you're trying to show.

We know that the process $\left(X_n\right)_{n\ge0}$ is a Markov chain, so we know that:

$$ \mathbb{P}(X_{n+1} = i_{n+1}|X_n=i_n,\dots X_0=i_0)=\mathbb{P}(X_{n+1}=i_{n+1}|X_n=i_n) $$

(you can ignore the $(\lambda, P)$ representation for now if you want).

Now you need to show that $(X_{kn})_{n\ge0}$ is a Markov chain for any $k$. So you need to check the Markov condition again. Writing $Y_n=X_{kn}$, we now need to show that:

$$ \mathbb{P}(Y_{n+1} = i_{n+1}|Y_n=i_n,\dots Y_0=i_0)=\mathbb{P}(Y_{n+1}=i_{n+1}|Y_n=i_n) $$

I.e.:

$$ \mathbb{P}(X_{kn+k} = i_{n+1}|X_{kn}=i_n,\dots,X_0=i_0)=\mathbb{P}(X_{kn+k} = i_{n+1}|X_{kn}=i_n) $$

I'm not going to tell you precisely how to do the question, except to hint that it involves two uses of mathematical induction. (The second part of Hagen's answer is an extremely nice way of doing the problem, but you should try to do it in a more routine way. How can you show that the property holds when $n=0$? And how might you show using induction that it holds for $n>0$?) Let me know if you have serious problems solving it.