Is the data-processing inequality still true for higher-order Markov chains? The data processing inequality states that if $X_1,X_2,...,X_n$ form the first-order Markov chain:
$$
X_1 \rightarrow X_2 \rightarrow \cdots \rightarrow X_n
$$
Then for all $i \leq j \leq k \leq l$:
$$
I(X_i;X_l) \leq I(X_j;X_k)
$$
Where $I(X_i;X_l)$ is the mutual information between $X_i$ and $X_l$. However, I want to know whether this inequality is still true or not for higher order Markov chains. I will also accept online references that discuss this.
A $k^{th}$ order Markov chain is one in which $X_i$ is conditionally independent of $X_{i-(k+1)},X_{i-(k+2)},...,X_1$ given $X_{i-1},X_{i-2},...,X_{i-k}$. For example, a second-order Markov chain would look like this:

Where, for example, $X_4$ is conditionally independent of $X_1$ given $X_2$ and $X_3$.
 A: It depends on exactly what you mean by 'this inequality'. And, no, I'm not just being difficult.
First (and I think this is what @whuber was being oracular about), if $X_i$ is a second-order Markov chain with state space ${\cal S}$, then the process with state $Y_i=\langle X_i, X_{i-1}\rangle$ at time $i$ is a first-order Markov chain with state space ${\cal S}\times {\cal S}$.  It follows immediately from the result you quote that
$$I(Y_i, Y_l)\leq I(Y_j, Y_k)$$
On the other hand, it does not follow that
$$I(X_i, X_l)\leq I(X_j, X_k).$$
Suppose $X$ is actually an interlacing of two first-order Markov chains, so $X_1, X_3, X_5,\ldots$ is first-order Markov and so is $X_2, X_4, X_6,\ldots$.  To take a degenerate case, suppose the odd-times chain has a   very low probability of moving to a new state and the even-times chain has an independent choice of state at each time.
The inequality
$$I(X_i, X_l)\leq I(X_j, X_k).$$
will be true if the indices are all odd or all even, but it will not be true for $i=1$, $l=5$, $j=2$, $k=4$ as, ex hypothesi, the information about $X_1$ from $X_5$ is large -- they are very likely to be in the same state -- but the information about $X_2$ from $X_4$ is zero.
