2
$\begingroup$

As correlation

$\rho_{X,Y} := \frac{Cov(X,Y)}{\sigma_X \sigma_Y}$

sort of measures the linear dependence of two random variables, and mutual information

$I(X; Y) := H(X) - H(X|Y)$

measures the general dependence of two random variables, I feel like it should be possible to get an upper bound on the correlation in terms of the mutual information.

I expect that as the mutual information increases, correlation tends to 1, and as mutual information tends to 0, correlation also does.

Can anyone help me formalise this?

$\endgroup$
  • $\begingroup$ From Wikipedia: in the special case that $(X,Y)$ is bivariate Gaussian, we have the following exact relationship. $$I(X;Y) = H(X)-H(X \mid Y) = \frac{1}{2} \log(2 \pi \sigma_X^2) - \frac{1}{2} \log(2 \pi (1-\rho^2) \sigma_X^2) = - \frac{1}{2} \log(1-\rho^2).$$ I am not sure about bounds in the general setting. $\endgroup$ – angryavian Nov 29 '16 at 19:11
  • $\begingroup$ Thanks, yes, I saw that. My $X$ and $Y$ are more general, though, so I wonder if there's some other bound there. $\endgroup$ – Tariq Nov 29 '16 at 19:15
2
$\begingroup$

This answer is physicist-oriented, but it should answer your question! It has the infinity norm in the denominator, I don't know if you can do better.

Suppose we have sets $A$ and $B$, joint probability distribution $p_{ab}$, and individual probability distributions $p_a=\sum_b p_{ab}$. We have the identities:

  1. $I(A:B)=D(p_{ab} \| p_a p_b)$ (a property of Kullback-Leibler)
  2. $D(p_a\|q_a)\ge \frac{1}{2}\left(\sum_{a\in A} |p_a-q_a|\right)^2$ (Pinsker's inequality, proof here)

Then, given functions $f(a)=f_a$ and $g(b)=g_b$, we may write:

$$I(A:B)\ge \frac{1}{2}\frac{\left(\langle f g\rangle-\langle f\rangle \langle g\rangle \right)^2}{\|f\|_\infty^2 \|g\|_\infty^2}$$

Proof:

\begin{align} I(A:B)&=D(p_{ab} \| p_a p_b)\\ &\ge\frac{1}{2}\left(\sum_{ab} |p_{ab}-p_a p_b|\right)^2\\ &\ge \frac{1}{2}\left(\sum_{ab} \Big|(p_{ab}-p_a p_b)\frac{f_a g_b}{\|f\|_\infty\|g\|_\infty}\Big|\right)^2\\ &=\frac{1}{2}\frac{\left(\langle f g\rangle-\langle f\rangle \langle g\rangle \right)^2}{\|f\|_\infty^2 \|g\|_\infty^2} \end{align}

(multiplying by numbers $0\le x\le 1$ is free) $$\tag*{$\square$}$$


physics citations:

p.4 of this paper by Wolf et al

p.36 of these notes by McGreevy

$\endgroup$
1
$\begingroup$

For the mutual information, it can be useful to consider the conditional entropy instead: $$H(X|Y) = H(X,Y) - H(X)$$

However, the claim in the question is incorrect, because correlation indicates only linear dependence, while mutual information relates to dependence in general.

Going back one step to covariance, we can find the following example:

  • $Y = X^2, X$ uniform distributed in $[-1,1]$
  • $\Rightarrow \sigma(X,Y) = 0, \sigma(X)= E(X^2)\neq 0, \sigma(Y)= E(X^4) \neq 0$, thus we get $\rho_{X,Y} = 0$
  • However, as stated in conditional entropy: $H(Y|X) = 0$, because $Y$ is completely determined by the value of $X$.
  • For the mutual information, we get: $I(X;Y) = H(Y) - H(Y|X) = H(Y)$. And this does not tend to $0$, even if the correlation is $0$ already.
$\endgroup$
  • $\begingroup$ Thanks for this answer, that was helpful to clarify some things in my mind! I suppose the bit I'm interested in is getting an upper bound on the correlation in terms of the mutual information. For example, if the mutual information is small, does this imply that the correlation is also small? I feel like it does, but can't show it formally. Your example disproves the converse, that a small correlation implies a small mutual information. $\endgroup$ – Tariq Nov 29 '16 at 20:13
  • $\begingroup$ @Tariq Since mutual information always has to be considered in relation to $H(X)$ and $H(Y)$, this is quite tricky. Because, what does "small" mean? Just the limit case of $I(X;Y) = 0$ indicates statistical independence, which also implies correlation of $0$. Entropy alone does not provide the necessary values to calculate correlation. As a small example: Try to figure out those values for $X \in \{0,1\}$, $Y\in \{0,1\}$, where $(X,Y) = (1,0)$ is excluded and the other three combinations are uniform. That should have "small" mutual information but relatively high correlation. $\endgroup$ – tylo Nov 29 '16 at 20:57
  • $\begingroup$ Thanks for that--you're correct there. Perhaps I could use a normalised version of the mutual information? Such as $\bar{I} (X;Y) := I(X;Y)/\sqrt{H(X) H(Y)}$? That way both the correlation and the mutual information are in some sense normalised. And basically what I'm looking for is something like $\rho_{X,Y} \leq const \cdot \bar{I}(X;Y)$, or perhaps some function of $\bar{I}(X;Y)$. $\endgroup$ – Tariq Nov 30 '16 at 13:12

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.