L'union fait la force

That's the moral of a fable by La Fontaine, inspired by Aesop:
An old man on the point of death summoned his sons around him to give them some parting advice. He ordered his servants to bring in a faggot of sticks, and said to his eldest son: "Break it." The son strained and strained, but with all his efforts was unable to break the Bundle. The other sons also tried, but none of them was successful. "Untie the faggots," said the father, "and each of you take a stick." When they had done so, he called out to them: "Now, break," and each stick was easily broken. "You see my meaning," said their father. Union gives strength.

Oded Regev recently gave me a mathematical illustration of that principle .

Given n independent random variables x(1), x(2), ..., x(n), the mutual information between the collection of all x(i)'s taken together and some other variable m is greater than the sum of the mutual informations between each variable x(i) and m:

I(x(1)x(2)...x(n):m) ≥ Σ I(x(i):m)

For example, imagine x(1) and x(2) are independent random bits, and m=x(1) XOR x(2). Then x(1) alone gives no information about m, so I(x(1):m)=0. Similarly, x(2) alone gives no information about m, so I(x(2):m)=0. However, x(1) and x(2) together determine m, so they give full information about it: I(x(1)x(2):m)=1. It is not hard to check that 1 is indeed greater than 0+0.