Bound covariance of two discrete random variables

Question

Let $X,Y$ be two random variables over a discrete probability space, such that $X \in [0,1]$ and $Y \in [0,1]$. I want to prove that $$ |\text{Cov}[X,Y]| \leq \sqrt{0.5 \; I[X,Y]}$$ where $I[]$ is the mutual information of the variables. Is there an "elegant" way to prove that? Some smart argument rather than technical analysis.

Answer 1

This follows from Pinsker's inequality. The inequality states that for any two distributions (here, discrete) $P$, and $Q$, it holds that

$$\|P-Q\| \le \sqrt{2D_{\text{KL}}(P\|Q)} $$ where $D_{\text{KL}}(\cdot \|\cdot)$ is the Kullback–Leibler divergence and $|P-Q|$ is their total variation.

For the right-hand side, recall that for any $X,Y$ random variables with joint distribution $p_{x,y}(x,y)$ and marginals $p_x(x)$, $p_y(y)$, we have $$I(X,Y) = D_{\text{KL}}(p_{x,y} \| p_x p_y).$$

So if we define $P = p_{x,y}$ and $Q=p_xp_y$, we obtain the desired right-hand side.

On the other hand, by definition, $$ \begin{align} \| P - Q\| & = \sum_{x,y}|p(x,y) - p_x(x)p_y(y)| \\ & \ge \sum_{x,y}|p(x,y) - p_x(x)p_y(y)| \cdot xy \\ & = \sum_{x,y}|p(x,y)xy - p_x(x)x\cdot p_y(y)y|\\ & \ge \left|\sum_{x,y} \left(p(x,y)xy - p_x(x)x\cdot p_y(y)y\right)\right|\\ & = \left|E[XY] - E[X]E[Y]\right| \\ &= |\text{cov}(X,Y)|. \end{align} $$ The first equality follows since $x,y \in [0,1]$ and each term is non-negative. The rest of the derivation is mostly algebra. I'm probably missing a factor 2 of the normalization of the total variation. This will give the right constant inside the square root.