# An inequality for Maximal Correlation over a Markov Chain

Let a pair of random variables $(X,Y)$ be defined over finite alphabet $\mathcal{X}\times \mathcal{Y}$ with joint distribution $P_{XY}$. The maximal correlation $\rho(X;Y)$ between $X$ and $Y$ is defined as $$\rho(X;Y):=\max_{f,g}\mathbb{E}[f(X)g(Y)],$$ where the maximization is taken over real-valued functions $f$ and $g$ such that $\mathbb{E}[f(X)]=\mathbb{E}[g(Y)]=0$ and $\mathbb{E}[f^2(X)]=\mathbb{E}[g^2(Y)]=1$. A single-function characterization of maximal correlation correlation was given by by Renyi as follows: $$\rho^2(X;Y)=\max_{f}\mathbb{E}[(\mathbb{E}[f(X)|Y])^2],$$ where $f$ satisfies the above conditions as well. One can easily see that for any arbitrary random variables $X$ and $Y$, $\rho(X;Y)\leq 1$.

For any $Z$ such that $X, Y$ and $Z$ satisfy the Markov condition $X\to Y\to Z$ (that is, $P_{XYZ}(x, y, z)=P_X(x)P_{Y|X}(y|x)P_{Z|Y}(z|y)$), it can be easily shown that $$\rho(X;Z)\leq \rho(X;Y)\rho(Y;Z),$$ which in particular implies that $\rho(X;Z)\leq \rho(X;Y)$. Using this inequality one can show that if $\rho(Y;Z)\leq \frac{\varepsilon}{\rho(X;Y)}$ for any $\varepsilon> 0$, then $\rho(X;Z)\leq \epsilon$. I would like to show the converse.

Does $\rho(X;Z)\leq \varepsilon$ imply that $\rho(Y;Z)\leq \frac{\varepsilon}{\rho(X;Y)}$ for a fixed joint distribution $P_{XY}$ and any $Z$ that satisfies the Markov condition $X\to Y\to Z$?

The answer is no. Let $B_0,B_1,B_2,\ldots$ be a sequence of i.i.d. fair bits. Then the sequence $X_k:=(B_k,B_{k+1})$ for $k=0,1,2,\ldots$ forms a Markov chain on $4$ symbols. For every $k \ge 0$, we have that $\rho(X_k,X_{k+1})=1$, yet $X_k$ is independent of $X_{k+2}$. In particular, $\rho(X_0,X_2)=0$.