MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
up vote 2 down vote accepted

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.

share|cite|improve this answer
Alberto, can you please explain how to show $E(Z)\geq I(X;Y)$? – math-Student Jan 9 '14 at 22:30

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 .

share|cite|improve this answer

Try looking at the Wyner common information.

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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