Relation between variance and mutual information

Question

Given two discrete random variables $X,Y$ such that $X,Y \in \mathbb{R}$ and $0 \leq X,Y \leq 1$, is it true that $$|\text{Cov}[X,Y] \leq \sqrt{\frac{1}{2} \text{I}[X,Y]}|. $$

This bound may be useful to my research if correct. What I have tried to do in order to prove it is the following:
1. Define the probability space $\mu$ over pairs of possible values of $X$ and $Y$: $$\Pr_\mu [(\alpha,\beta)] = \Pr[X = \alpha \text{ and } Y = \beta].$$
2. Similarly, let $\eta$ be the following probability space:
$$\Pr_\eta[(\alpha,\beta)] = \Pr[X=\alpha] \Pr[Y = \beta].$$
3. It can be seen that $D_{KL} (\mu ||\eta) = \text{I}[X,Y]$ where $D_{KL} (\mu ||\eta)$ is the Kullback–Leibler divergence (https://en.wikipedia.org/wiki/Kullback%E2%80%93Leibler_divergence).
4. Now, using Pinsker's inequality (https://en.wikipedia.org/wiki/Pinsker%27s_inequality) we get that: $$\delta(\mu,\eta) \leq \sqrt{\frac{1}{2} D_{KL}(\mu || \eta)} = \sqrt{\frac{1}{2}\text{I}[X,Y]}. $$
where $\delta()$ is the total variation distance .
5. The last step I tried is to find any connection between $\delta(\mu,\eta)$ and $|\text{Cov}[X,Y]|$ - ideally $|\text{Cov}[X,Y]| \leq \delta(\mu, \eta)$ - the problem is that seems like there is no such connection, I can find distribution where $|\text{Cov}[X,Y]| > \delta(\mu, \eta)$ and other distribution where the opposite holds.
I strongly believe that if this claim is correct, the proof goes through Pinsker's inequality, since it is very similar. Any advice will be appreciated.
EDIT:
As I was told in the comments, it holds that if $|X|, |Y| \leq 1$, $|\text{Cov}[X,Y]| \leq \delta (\mu, \eta)$ - the proof is in the comments. I was wrong when I thought I had a counter example. I also believe that the accepted answer below is correct.

Answer 1

I think you can show it as follows, and even get a better constant in the end. Forewarning, there's enough cleverness here that I'm kind of suspect that everything is right. But the basic idea is simple enough: reduce to the case where $X$ and $Y$ take values in $\{0,1\}$, where we can exploit a nice relationship between covariance and total variation distance for such variables. From there, the rest of your proof idea works out.

First, introduce $\tau_X$ and $\tau_Y$ as uniform, independent draws from $[0,1]$. Define $\hat{X} = 1$ if $X \ge \tau_X$ and $\hat{X}=0$ otherwise, and define $\hat{Y}$ similarly. Then we have the following relationships:

1. $\mathrm{Cov}[\hat{X},\hat{Y}]=\mathrm{Cov}[X,Y]$.

2. $|\mathrm{Cov}[\hat{X},\hat{Y}]| = \frac{1}{2}\hat{\delta}$ where $\hat{\delta}$ is the TVD of the joint distribution of $\hat{X},\hat{Y}$ from the product of the marginals (analogous to your $\mu$ and $\eta$).

3. $I[\hat{X} : \hat{Y}] \le I[X : Y]$

These can be combined with Pinsker's inequality to prove your claim (even halving the constant).

(1) follows easily by computing $\mathbb{E}[\hat{X}|X]=\mathbb{P}[\tau_X \le X|X] = X$, and similar for $Y$ and $XY$.

(2) can be worked out as follows. Let $a,b,c,d$ be the probabilities that $(\hat{X},\hat{Y})$ takes the values $(0,0), (0,1), (1,0), (1,1)$, respectively. We can write $|\mathrm{Cov}[\hat{X},\hat{Y}]| = |d - (c+d)(b+d)|$. But covariance is invariant under shifts of the variables, and flips sign when a variable is negated. All together, we have $$|\mathrm{Cov}[\hat{X},\hat{Y}]| = \left\{ \begin{array}{ccl} |\mathrm{Cov}[\hat{X},\hat{Y}]| &=& |d - (b+d)(c+d)| \\ |\mathrm{Cov}[\hat{X},1-\hat{Y}]| &=& |c - (a+c)(c+d)| \\ |\mathrm{Cov}[1-\hat{X},\hat{Y}]| &=& |b - (a+b)(b+d)| \\ |\mathrm{Cov}[1-\hat{X},1-\hat{Y}]| &=& |a - (a+c)(a+b)| \end{array}\right.$$ If you write out the quantity $|| \hat{\mu} - \hat{\eta} ||_1$, where $\hat{\mu}$ is the joint distribution of $(\hat{X},\hat{Y})$, and $\hat{\eta}$ is the product of the marginals, then it's the sum of the above four quantities, hence four times the covariance. Dividing through by 4 and writing $||\hat{\mu} - \hat{\eta}||_1$ as $2\hat{\delta} (= 2\delta(\hat{\mu},\hat{\eta}))$ gives (2).

(3) follows from the data processing inequality. Note that once $X$ is fixed, $\hat{X}$ depends only on $\tau_X$, which is independent of everything else (even conditioned on $X$), and similarly with all the $X$'s replaced by $Y$'s. Thus the DPI can be applied twice to give (3), as follows: $$\begin{align*} I[X : Y] &\ge I[\hat{X} : Y] \\ &\ge I[\hat{X} : \hat{Y}] \end{align*}$$