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

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?

-
You can do it just using algebraic manipulation of conditional probabilities. –  Donkey_2009 Apr 7 '13 at 20:37
@Donkey_2009: Could you describe the general procedure? –  Thoth Apr 7 '13 at 21:10

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\}$.

-
Well because any power of the matrix still has rows (or columns) which add up to 1. But the Markov chain condition is more restrictive than that isn't it? –  Thoth Apr 7 '13 at 19:50
The matrix entries $a_{i,j}$ expresses the $P(X_{n+1}=i|X_n=j)$ and the fact that we have a Markov chain means precisely that $A$ is "all there is". –  Hagen von Eitzen Apr 7 '13 at 19:59
@HagenvonEitzen I think the second idea is better. Finding a transition matrix does not prove that a process is Markov. My answer here explains it: math.stackexchange.com/questions/13088/… –  Byron Schmuland Apr 7 '13 at 20:26

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.

-

I think you just need to use the independence Markov property: $X_0, X_1,...,X_m$ is independent of $(X_{m+n})_{n\geq 0}$ with respect to the probability $\mathbb{P}_{[X_m=i]}$. In this case follow that $$\mathbb{P}[X_{kn}=i_n|X_{(n-1)k}=i_{n-1},...,X_0=i_0]=$$ $$=\mathbb{P}_{[X_{(n-1)k}=i_{n-1}]}[X_{kn}=i_n|X_{(n-2)k}=i_{n-2},...,X_0=i_0]$$ $$=\mathbb{P}_{[X_{(n-1)k}=i_{n-1}]}[X_{kn}=i_n]$$ by independece. And the last quantity is $p^k(i_{n-1},i_n)$.

-