Markov process and conditional probability

Question

Given a Markov Process, that is $$\mathbb{P}(X_{n+1}=x_{n+1}\mid X_{n}=x_{n},X_{n-1}=x_{n-1}, \dots, X_0=x_0)=\mathbb{P}(X_{n+1}=x_{n+1}\mid X_{n}=x_{n})$$I Need to prove that $$\mathbb{P}(X_{n+m}=x_{n+m}\mid X_{n}=x_{n},X_{n-1}=x_{n-1}, \dots, X_0=x_0)=\mathbb{P}(X_{n+m}=x_{n+m}\mid X_{n}=x_{n})$$ also holds (of course $\forall n\geq 0$ and $\forall m\geq 0$. My guess is that $$\mathbb{P}(X_{n+m}=x_{n+m}\mid X_{n+m-1}=x_{n+m-1},X_{n+m-2}=x_{n+m-2}, \dots, X_0=x_0)=\mathbb{P}(X_{n+m}=x_{n+m}\mid X_{n+m-1}=x_{n+m-1})=\frac{\mathbb{P}(X_{n+m}=x_{n+m}, X_{n+m-1}=x_{n+m-1})}{\mathbb{P}(X_{n+m-1}=x_{n+m-1})}$$ might help me, but it I get stuck. Is my attempt in the wrong direction or is there a next possible step?

Answer 1

The key is to consider the values of the variables $X_{n+1}, X_{n+2},\ldots, X_{n+m-1}$ that haven't been mentioned. Write: $$ \begin{align} \mathbb{P}&(X_{n+m}=x_{n+m}\mid X_{n}=x_{n},X_{n-1}=x_{n-1}, \dots, X_0=x_0)\\ &=\sum_{\bf y} \mathbb{P}(X_{n+m}=x_{n+m}, {\bf Y}={\bf y}\mid X_{n}=x_{n},X_{n-1}=x_{n-1}, \dots, X_0=x_0)\end{align} $$ where for laziness I write the vector ${\bf Y}$ to represent these unmentioned variables, and we are summing over all possible (vector) values ${\bf y}$ for these omitted variables. Now by the Markov property, in each term of the sum the event we're conditioning on can be replaced by the event $\{X_n=x_n\}$. Finally, we sum over all possible values ${\bf y}$ and attain the desired result.