Using the canonical Markov property to prove an obvious fact about Markov chains

Given a Markov chain $\{X_n: n \geq 1 \}$, such that

$$\mathbb{P}(X_{n+1} = x_{n+1} | X_n = x_n) = \mathbb{P}(X_{n+1} = x_{n+1} | X_n = x_n, \ldots X_1= x_1)$$

How can I formally prove that:

$$\mathbb{P}(X_{n+1} = x_{n+1} | X_n = x_n) = \mathbb{P}(X_{n+1} = x_{n+1} | X_n = x_n, X_k = x_k )$$

for $k = 1 \ldots N-1$

-

It has been a while since I've done anything with Markov chains, so I apologize for any poor notation in advance.

Notice that $\{X_n=x_n, X_k=x_k\}$ is $\sigma$-measurable from $\{X_n=x_n, \ldots,\ X_1=x_1 \},$ for $k< n$. Really the Markov property for finite state spaces is equivalent to

$P(X_{n+1}=x_{n+1}\,|\, \sigma\{X_n,\, \ldots,\, X_1 \} )=P(X_{n+1}=x_{n+1}|\, X_n=x_n).$

-

The simplest (minimally measure-theoretic) approach that I found is the following:

First, define a history of the states in all periods except for periods $k$, $n$ and $n+1$ as follows

$$H = \Big\{ X_1(\omega_1) = x_1, \ldots, X_{k-1}(\omega_{k-1}) = x_{k-1}, X_{k+1}(\omega_{k+1}) = x_{k+1}, \ldots X_{n-1}(\omega_{n-1}) = x_{n-1} \ \Big| \ \omega_1 \in \Omega_{1},\omega_{k-1} \in \Omega_{k-1},\omega_{k+1} \in \Omega_{k+1},\omega_{n-1} \in \Omega_{n-1} \Big \}$$

where $h$ denote a particular realization of $H$.

Using, this we can see that:

\begin{align} \mathbb{P}(X_{n+1} = x_{n+1} | X_n = x_n, X_k = x_k ) &= \sum_{h \in H} \mathbb{P}(X_{n+1} = x_{n+1}, \ h \ | \ X_n = x_n, X_k = x_k) \\ &= \sum_{h \in H} \mathbb{P}(X_{n+1} = x_{n+1} \ | \ h, X_n = x_n, X_k = x_k) \mathbb{P}(h \ | \ X_n = x_n, X_k = x_k) \\ \end{align}

Now we note that:

\begin{align} \mathbb{P}(X_{n+1} = x_{n+1} \ | \ h, X_n = x_n, X_k = x_k) &= \mathbb{P}( X_{n+1} = x_{n+1} \ | \ X_n = x_n, X_{n-1} = x_{n-1},\ldots, X_1 = x_1 ) \\ &= \mathbb{P}( X_{n+1} = x_{n+1} \ | \ X_n = x_n) \end{align}

by the definition of $h$ and the Markov Property.

Similarly,

\begin{align} \mathbb{P}(h \ | \ X_n = x_n, X_k = x_k) &= \mathbb{P}( X_{n-1} = x_{n-1}, \ldots, X_{k+1} = x_{k+1}, X_{k-1} = x_{k-1}, \ldots, X_1 \ | \ X_n = x_n, X_k = x_k ) \\ &= \mathbb{P}( X_{n-1} = x_{n-1}, \ldots, X_{k+1} = x_{k+1}, X_{k-1} = x_{k-1}, \ldots, X_1 ) \\ & = \mathbb{P}(h) \end{align}

Substituting these expressions in, we get that:

\begin{align} \mathbb{P}(X_{n+1} = x_{n+1} | X_n = x_n, X_k = x_k ) &= \sum_{h \in H} \mathbb{P}(X_{n+1} = x_{n+1} \ | \ h, X_n = x_n, X_k = x_k) \mathbb{P}(h \ | \ X_n = x_n, X_k = x_k) \\ &= \mathbb{P}(X_{n+1} = x_{n+1} \ | X_n = x_n) \sum_{h \in H} \mathbb{P}(h) \\ &= \mathbb{P}(X_{n+1} = x_{n+1} \ | X_n = x_n) \\ \end{align}

which proves the desired result.

-