# Relation between variance and mutual information

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.

• For the distributions you mention to have found in 5., for which $\lvert \operatorname{Cov}(X,Y)\rvert > \delta(\mu,\eta)$, what is the value of $\lvert \operatorname{Cov}(X,Y)\rvert$ and what is the value of $I(X,Y)$? Aug 15, 2017 at 0:28
• Are you sure about your counterexample at the bottom? I think we have Cov$(X,Y) = E[XY] - E[X]E[Y] = \sum_{x,y} xy(p(x,y) - p(x)p(y))$ $\leq \sum_{x,y} \mathbf{1}[p(x,y) > p(x)p(y)]*(p(x,y) - p(x)p(y)) = \delta(\mu,\eta).$
– usul
Aug 15, 2017 at 4:02
• Take $X_n = Y_n$ where $\Pr(X_n = \frac{k}{n}) = \frac{1}{n}$ for $k= 1,...,n$. $\delta(X_n,Y_n) = |1/n - 1/n^2|$ which approaches to 0 and $\text{Cov}[X_n,Y_n]= Var(X_n)$ which approaches to positive constant ($1/12$). So there is some $n$ for which the covariance is larger Aug 15, 2017 at 4:18
• In this case, $I(X,Y) = \log (n)$. @usul your proof seems correct; this is what I have done before I found out the distribution above; not sure where is the mistake Aug 15, 2017 at 4:27
• @RonaLee, I think your total variation calculation might be wrong (and of course you mean $\delta(\mu,\eta)$ ... intuitively, these distributions put almost no weight on the same outcome so distance should be high). I get $1 - \frac{1}{n}$ witnessed by the set $S = \{(1,1),\dots,(n,n)\}$. The probability of this set under $\mu$ is $1$ but under $\eta$ it is only $\frac{1}{n}$. Can double-check using $L_1$.
– usul
Aug 15, 2017 at 11:24

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*}