Implications from definition of discrete markov chains 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.
 A: 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}
