Question

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)$.

Answer 1

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.

Answer 2

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 .