Let $\{X_i\}$ be a Stationary Markov chain, $\mathcal{X} = \text{range} X_i$ and let $\phi: \mathcal{X} \to \mathcal{Y}$ be a function that gives rise to another stochastic process $\{Y_i\}$, where $Y_i = \phi(X_i)$. I want to prove that
\begin{equation*} H(Y_n | Y_{n-1},\dots,Y_1, X_1) = H(Y_n | Y_{n-1},\dots, Y_1, X_1, \color{red}{X_0, \dots , X_{-k}}), \end{equation*}
where $k$ is an arbitrary integer.
I do not have any intuition or reason about why this should be true! Can you provide some? Also, I do not know where to start for proving this.
It's just conditional independence: for any $n$, given $X_1, X_2^n$ is independent of $X_{-k}^0$ due to the Markov structure. But $Y_1^n = f(X_1^n)$, so this is also independent of $X_{-k}^0$ given $X_1$, i.e., $$ H(Y_1^n|X_1, X_{-k}^0) = H(Y_1^n|X_1).$$ But then
\begin{align*} H(Y_n|Y_1^{n-1},X_1) &= H(Y_1^n|X_1) - H(Y_1^{n-1}|X_1) \\ &= H(Y_1^n|X_1, X_{-k}^0) - H(Y_1^{n-1}|X_1,X_{-k}^0) \\ &= H( Y_n|Y_1^{n-1}, X_1, X_{-k}^0). \end{align*}