2
$\begingroup$

Let $X$,$Y$ be two stochastic variables with probability distribution $\rho(X,Y)$. The mutual information, $I(X;Y)$, represents the information shared by the two variables. This intuitive interpretation of $I(X;Y)$ suggests the following question. Given $\rho(X,Y)$, is there a process $X\rightarrow Z\rightarrow Y$ so that the entropy of $Z$ is equal to the mutual information $I(X;Y)$? Indeed, the minimal amount of information contained in $Z$ should be the information strictly necessary for reproducing the correlations between $X$ and $Y$. It is easy to show that $E(Z)\ge I(X;Y)$, but it is not clear to me if the strict equality can be reached for any $\rho(X,Y)$.

$\endgroup$

3 Answers 3

2
$\begingroup$

I have found this paper that is closely related with my question:

"The communication complexity of Correlation" by P. Harsha, R. Jain, D. McAllester, J. Radhakrishnan, IEEE Transactions on Information Theory 56, 438 (2010).

In this paper, it is shown that the communication cost required for generating correlation can be very close to the mutual information. Indeed, it is proved that the communication cost is smaller or equal to the mutual information, I, plus 2 log(I+1). The authors consider a scenario where random resources are shared by the parties.

$\endgroup$
1
  • $\begingroup$ Alberto, can you please explain how to show $E(Z)\geq I(X;Y)$? $\endgroup$ Jan 9, 2014 at 22:30
1
$\begingroup$

I don't claim to be an expert on this topic, and I apologize if the following misses the point. It seems to me that your question may be addressed by the work of Gács and Körner, "Common information is far less than mutual information" [Problems Control Inform. Theory 2 (1973) 149-162]. I haven't actually seen this paper but am relying on (the title and) the description in a paper of Hammer, Romashchenko, Shen, and Vereshchagin, "Inequalities for Shannon Entropy and Kolmogorov Complexity" at http://www.lif.univ-mrs.fr/~ashen/mathtext/inequal/final.pdf (Wayback Machine).

$\endgroup$
0
$\begingroup$

Try looking at the Wyner common information.

Link

It's not exactly the same thing, but it's a little closer to what you're discussing than the Gács-Körner common information. The measure "V" (for Virgil) between random variables $X$ and $Y$ might capture what you want. It isn't the same thing as the Wyner common information, but it might be what you want---

$V(X:Y) \equiv \min_{Q} H(Q)$ under constraint that $I(X:Y|Q)=0$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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