3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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)$? $\endgroup$ – Clement C. Aug 15 '17 at 0:28
  • 3
    $\begingroup$ 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).$ $\endgroup$ – usul Aug 15 '17 at 4:02
  • $\begingroup$ 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 $\endgroup$ – Rona Lee Aug 15 '17 at 4:18
  • $\begingroup$ 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 $\endgroup$ – Rona Lee Aug 15 '17 at 4:27
  • $\begingroup$ @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$. $\endgroup$ – usul Aug 15 '17 at 11:24
3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.