Help with a proof regarding Chapman-Kolmogorov.

Question

Let $(X_n)_{n \in \mathbb{N}_0}$ be a discrete Markov chain. Define $\mathbb{P}_x^n(A)= (A | \{X_{n} = x\})$.

Show that $p_{x,y}(n, n+k) = \sum_z \mathbb{P}_x^n(\{X_{n+l} = z\}) \cdot \mathbb{P}_x^n(\{X_{n+k} = y\} | \{X_{n+l} = z\})$.

I figured that this might be solveable if we use the law of total probability:

$\mathbb{P}(A) = \sum_{k=1}^n \mathbb{P}(B_k) \mathbb{P}(A|B_k)$ on the probability measure $\mathbb{P}_x^n$.

But I'm not able to show that the equation holds.

Answer 1

I will use a slightly different notation. Let $I$ be the state space for the Markov chain.

• (Chapman-Kolmogorov): $p_{x,y}(n,n+k)=\mathbb{P}(X_{n+k}=y|X_n=x)= \sum_{z \in I}{\mathbb{P}(X_{n+l}=z|X_n = x)\cdot \mathbb{P}(X_{n+k}=y|X_{n+l} = z)}$

Now, let's prove it:

$$\mathbb{P}(X_{n+k}=y|X_n=x) =$$ $$\mathbb{P}(X_{n+k}=y,X_{n+k-1}\in I,...,X_{n+l+1} \in I|X_{n+l} \in I,..., X_{n+1} \in I,X_n=x)\cdot \mathbb{P}(X_{n+l}\in I,...,X_{n+1}\in I|X_n=x)= $$ $$ \sum_{z \in I}\mathbb{P}(X_{n+k}=y,X_{n+k-1}\in I,...,X_{n+l+1} \in I|X_{n+l}=z,..., X_{n+1} \in I,X_n=x)\cdot \mathbb{P}(X_{n+l}=z,...,X_{n+1}\in I|X_n=x)= $$ $$ \sum_{z \in I}\mathbb{P}(X_{n+k}=y|X_{n+l}=z)\cdot \mathbb{P}(X_{n+l}=z|X_n=x) $$