Discrete markov chains can be defined by their propterty $$\mathbb{P}(X_n = z_n | X_{n-1}=z_{n-1}, ..., X_0 = z_0) = \mathbb{P}(X_n = z_n | X_{n-1}=z_{n-1}).$$
Intuitively it should also hold for example: $$\mathbb{P}(X_n = z_n | X_{n-1}=z_{n-1}, ..., X_{n-k} = z_{n-k}) = \mathbb{P}(X_n = z_n | X_{n-1}=z_{n-1}).$$
But how can I prove this? More generally, can we say something for an expression like $\mathbb{P}((X_{n+r}, ..., X_n)\in A| (X_{n-1}, ..., X_{0})\in B)$?
Thanks in advance.
I will switch back and forth on notation for events. For example, these two expressions are the same: \begin{equation} \{X = z\}~~~\textrm{is the event}~~~\{\omega\in\Omega : X(\omega) = z\}. \end{equation}
Let $S$ be the space in which all the $X_i$ take values. Then \begin{equation} \left\{\omega\in\Omega : X_i(\omega) \in S\right\} = \Omega, \end{equation} the entire sample space. This ensures that if $A$ is an event, then $A\cap\{X_i\in S\} = A$.
Let $A$ be the event \begin{equation} A = \left\{\omega\in\Omega : X_{n-1}(\omega) = z_{n-1},\ldots,X_{n-k}(\omega)=z_{n-k}\right\}. \end{equation} Then \begin{eqnarray} && \mathsf{P}(X_n = z_n\mid X_{n-1} = z_{n-1},\ldots,X_{n-k}=z_{n-k})\\ &=& \mathsf{P}(X_n = z_n\mid A)\\ &=& \mathsf{P}(X_n = z_n\mid A\cap \{X_{n-k-1}\in S\})\\ &=& \mathsf{P}(X_n = z_n\mid A\cap \{X_{n-k-1}\in S\}\cap \{X_{n-k-2}\in S\})\\ &\vdots&\\ &=& \mathsf{P}(X_n = z_n\mid A\cap \{X_{n-k-1}\in S\}\cap\cdots\cap \{X_0\in S\}). \end{eqnarray}
We need to introduce more notation to keep equations on single lines. Let \begin{equation} \mathbf{X} = (X_{n-k-1},\ldots,X_0). \end{equation} Then the probability in the final line can be expressed as \begin{eqnarray} \sum_{\mathbf{z}\in S^{n-k}}\mathsf{P}(X_n=z_n\mid A\cap\underbrace{\{\mathbf{X} \in S^{n-k}}_{\Omega}\}). \end{eqnarray}
We decompose $\mathsf{P}(X_n=z_n\mid A\cap\{\mathbf{X}\in S^{n-k}\})$ as follows. Note that $\{\mathbf{X}\in S^{n-k}\} = \Omega$, so $A\cap\{\mathbf{X}\in S^{n-k}\} = A$. \begin{eqnarray} &&\mathsf{P}(X_n=z_n\mid A\cap\{\mathbf{X}\in S^{n-k}\})\\ &=& \mathsf{P}\left(X_n=z_n\mid A\cap\left(\cup_{\mathbf{z}\in S^{n-k}}\{\mathbf{X} = \mathbf{z}\}\right)\right)\\ &=& \mathsf{P}\left(X_n=z_n\mid \cup_{\mathbf{z}\in S^{n-k}}A\cap\{\mathbf{X} = \mathbf{z}\}\right) \end{eqnarray}
We now apply Bayes's Formula to the conditional probability. \begin{eqnarray} && \mathsf{P}\left(X_n=z_n\mid \cup_{\mathbf{z}\in S^{n-k}}A\cap\{\mathbf{X} = \mathbf{z}\}\right)\\ &=& \frac{\mathsf{P}\left(\{X_n=z_n\}\cap\left(\cup_{\mathbf{z}\in S^{n-k}}A\cap\{\mathbf{X} = \mathbf{z}\}\right)\right)}{\mathsf{P}\left(\cup_{\mathbf{z}\in S^{n-k}}A\cap\{\mathbf{X} = \mathbf{z}\}\right)}\\ &=& \frac{\mathsf{P}\left(\cup_{\mathbf{z}\in S^{n-k}}\{X_n=z_n\}\cap A\cap\{\mathbf{X} = \mathbf{z}\}\right)}{\mathsf{P}\left(\cup_{\mathbf{z}\in S^{n-k}}A\cap\{\mathbf{X} = \mathbf{z}\}\right)} \end{eqnarray}
For distinct $\mathbf{z}$, the events in the union are disjoint. The probability of the union of disjoint events is the sum of the individual probabilities.
\begin{eqnarray} && \mathsf{P}\left(\cup_{\mathbf{z}\in S^{n-k}}\{X_n=z_n\}\cap A\cap\{\mathbf{X} = \mathbf{z}\}\right)\\ &=& \sum_{\mathbf{z}\in S^{n-k}}\mathsf{P}\left(\{X_n=z_n\}\cap A\cap\{\mathbf{X} = \mathbf{z}\}\right) \end{eqnarray}
We now apply Bayes's Formula to the inidvidual probabilities: \begin{eqnarray} && \mathsf{P}\left(\{X_n=z_n\}\cap A\cap\{\mathbf{X} = \mathbf{z}\}\right)\\ &=& \mathsf{P}\left(X_n=z_n\mid A\cap\{\mathbf{X} = \mathbf{z}\}\right)\mathsf{P}\left(A\cap\{\mathbf{X} = \mathbf{z}\}\right) \end{eqnarray} In the event $A\cap\{\mathbf{X} = \mathbf{z}\}$, each $X_i$ from $i=0$ to $i=n-1$ has a specific value. By the Markov property, then, \begin{eqnarray} && \mathsf{P}\left(X_n=z_n\mid A\cap\{\mathbf{X} = \mathbf{z}\}\right)\\ &=& \mathsf{P}\left(X_n=z_n\mid X_{n-1}=z_{n-1}\right). \end{eqnarray}
When we combine these results, we have \begin{eqnarray} &&\mathsf{P}(X_n=z_n\mid A\cap\{\mathbf{X}\in S^{n-k}\})\\ &=& \frac{\sum_{\mathbf{z}\in S^{n-k}}\mathsf{P}\left(X_n=z_n\mid X_{n-1}=z_{n-1}\right)\mathsf{P}\left(A\cap\{\mathbf{X} = \mathbf{z}\}\right)}{\mathsf{P}\left(\cup_{\mathbf{z}\in S^{n-k}}A\cap\{\mathbf{X} = \mathbf{z}\}\right)}. \end{eqnarray}
Since $\mathsf{P}\left(X_n=z_n\mid X_{n-1}=z_{n-1}\right)$ has no dependence on $\mathbf{z}$ (the values of $X_{n-k-1},\ldots,X_0$), we can "bring it outside" of the sum: \begin{eqnarray} &&\mathsf{P}(X_n=z_n\mid A\cap\{\mathbf{X}\in S^{n-k}\})\\ &=& \frac{\mathsf{P}\left(X_n=z_n\mid X_{n-1}=z_{n-1}\right)\sum_{\mathbf{z}\in S^{n-k}}\mathsf{P}\left(A\cap\{\mathbf{X} = \mathbf{z}\}\right)}{\mathsf{P}\left(\cup_{\mathbf{z}\in S^{n-k}}A\cap\{\mathbf{X} = \mathbf{z}\}\right)}. \end{eqnarray}
Finally, note that \begin{eqnarray} && \sum_{\mathbf{z}\in S^{n-k}}\mathsf{P}\left(A\cap\{\mathbf{X} = \mathbf{z}\}\right)\\ &=& \mathsf{P}\left(\cup_{\mathbf{z}\in S^{n-k}}A\cap\{\mathbf{X} = \mathbf{z}\}\right). \end{eqnarray}
We have arrived at \begin{eqnarray} && \mathsf{P}(X_n = z_n\mid \overbrace{X_{n-1}=z_{n-1},\ldots,X_{n-k}=z_{n-k}}^{A})\\ &=& \mathsf{P}(X_n = z_n\mid A)\\ &=& \mathsf{P}(X_n = z_n\mid A\cap\underbrace{\{\mathbf{X}\in S^{n-k}}_{\Omega}\})\\ &=& \mathsf{P}(X_n = z_n\mid X_{n-1} = z_{n-1})\times\frac{\sum_{\mathbf{z}\in S^{n-k}}\mathsf{P}\left(A\cap\{\mathbf{X} = \mathbf{z}\}\right)}{\mathsf{P}\left(\cup_{\mathbf{z}\in S^{n-k}}A\cap\{\mathbf{X} = \mathbf{z}\}\right)}\\ &=& \mathsf{P}(X_n = z_n\mid X_{n-1} = z_{n-1}). \end{eqnarray}