<p>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.</p>

<p>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:</p>

<ol>
<li><p>$\mathrm{Cov}[\hat{X},\hat{Y}]=\mathrm{Cov}[X,Y]$.</p></li>
<li><p>$|\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$).</p></li>
<li><p>$I[\hat{X} : \hat{Y}] \le I[X : Y]$</p></li>
</ol>

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

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

<p>(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}]| &amp;=&amp; |d - (b+d)(c+d)| \\
|\mathrm{Cov}[\hat{X},1-\hat{Y}]| &amp;=&amp; |c - (a+c)(c+d)| \\
|\mathrm{Cov}[1-\hat{X},\hat{Y}]| &amp;=&amp; |b - (a+b)(b+d)| \\
|\mathrm{Cov}[1-\hat{X},1-\hat{Y}]| &amp;=&amp; |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).</p>

<p>(3) follows from the <a href="https://en.wikipedia.org/wiki/Data_processing_inequality" rel="nofollow noreferrer">data processing inequality</a>. 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] &amp;\ge I[\hat{X} : Y] \\
&amp;\ge I[\hat{X} : \hat{Y}]
\end{align*}$$</p>

CC BY-SA 3.0
2017-08-15T03:51:11.287Z
2017-08-15T03:51:11.287Z
Andrew Morgan
<p>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]}|. $$</p>

<p>This bound may be useful to my research if correct. What I have tried to do in order to prove it is the following:<br>
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].$$<br>
2. Similarly, let $\eta$ be the following probability space:<br>
$$\Pr_\eta[(\alpha,\beta)] = \Pr[X=\alpha] \Pr[Y = \beta].$$<br>
3. It can be seen that $D_{KL} (\mu ||\eta) = \text{I}[X,Y]$ where $D_{KL} (\mu ||\eta)$ is the Kullback–Leibler divergence (<a href="https://en.wikipedia.org/wiki/Kullback%E2%80%93Leibler_divergence" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Kullback%E2%80%93Leibler_divergence</a>).<br>
4. Now, using Pinsker's inequality (<a href="https://en.wikipedia.org/wiki/Pinsker%27s_inequality" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Pinsker%27s_inequality</a>) we get that: $$\delta(\mu,\eta) \leq \sqrt{\frac{1}{2} D_{KL}(\mu || \eta)} = \sqrt{\frac{1}{2}\text{I}[X,Y]}. $$<br>
where $\delta()$ is the total variation distance .<br>
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]| &gt; \delta(\mu, \eta)$ and other distribution where the opposite holds.<br>
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.<br>
EDIT:<br>
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.</p>

CC BY-SA 3.0
2017-08-15T00:28:09.930Z
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)$?
Clement C.
CC BY-SA 3.0
2017-08-15T04:02:32.780Z
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
CC BY-SA 3.0
2017-08-15T04:18:44.813Z
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
Rona Lee
CC BY-SA 3.0
2017-08-15T04:27:25.997Z
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
Rona Lee
CC BY-SA 3.0
2017-08-15T11:24:42.110Z
@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
CC BY-SA 3.0
2017-08-15T11:33:19.530Z
Joining the party a bit late: in the above, I find the same TV as @usul (using $\delta(\mu,\eta)=\frac{1}{2}\lVert\mu-\eta\rVert_1$), namely $1-\frac{1}{n}$.
Clement C.
CC BY-SA 3.0
2017-08-15T12:18:44.153Z
You are right,  I was wrong in the calculation. Both what you said and the answer below seem correct, wish I could accept more than one answer
Rona Lee
CC BY-SA 3.0
2017-08-15T12:23:51.983Z
@usul - I edited the post according to what you wrote. I am new to this community and have no idea how the reputation here works, but if there is a way I can help comment here
Rona Lee
CC BY-SA 3.0
2017-08-15T12:39:45.047Z
@RonaLee just for the record, maybe mention again at the end of your edit that the relation (as proven above) requires $\lvert X\rvert, \lvert Y\rvert \leq 1$.
Clement C.
CC BY-SA 3.0
2017-08-15T13:00:21.813Z
@RonaLee, it's all fine as long as the question and answer are clear to future visitors! (There are probably many possible proofs, hence many right answers.)
usul
<co.combinatorics><pr.probability><it.information-theory><shannon-entropy>
Relation between variance and mutual information
Rona Lee
# Relation between variance and mutual information

(Asked by: username_0 on 2017-08-14)

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.

**Tags:** co.combinatorics, pr.probability, it.information-theory, shannon-entropy

> **Comments:**
> **username_1**: 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)$?  
> **username_2**: 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).$  
> **username_0**: 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  
> **username_0**: In this case, $I(X,Y) = \log (n)$. @username_2 your proof seems correct; this is what I have done before I found out the distribution above; not sure where is the mistake  
> **username_2**: @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$.  
> **username_1**: Joining the party a bit late: in the above, I find the same TV as @username_2 (using $\delta(\mu,\eta)=\frac{1}{2}\lVert\mu-\eta\rVert_1$), namely $1-\frac{1}{n}$.  
> **username_0**: You are right,  I was wrong in the calculation. Both what you said and the answer below seem correct, wish I could accept more than one answer  
> **username_0**: @username_2 - I edited the post according to what you wrote. I am new to this community and have no idea how the reputation here works, but if there is a way I can help comment here  
> **username_1**: @RonaLee just for the record, maybe mention again at the end of your edit that the relation (as proven above) requires $\lvert X\rvert, \lvert Y\rvert \leq 1$.  
> **username_2**: @RonaLee, it's all fine as long as the question and answer are clear to future visitors! (There are probably many possible proofs, hence many right answers.)  

---

## 1 answers

### Answer by username_3 on 2017-08-15. Score: 4 | Accepted answer

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](https://en.wikipedia.org/wiki/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\*}$$


---

