Nielsen and Chuang -- Chapter 11

Updated on January 11, 2019


Let $X, Y$ be i.i.d random variables uniformly distributed over set ${0, 1}$. Hence,

Now, let $Z = X \oplus Y$. Then,


Similarly, $I(Y:Z) = 0)$.

$\therefore$ $I(X:Z) + I(Y:Z) < I(X, Y : Z)$ in this case.

Thinking through this problem intuitively, it just says that if we’ve specified both $X,Y$, then we don’t need to send a bit for $Z$ through our channel since we can compute its value readily. However, if we send just $X$ or $Y$, the XOR function provides uniform outcomes across $Z$.

(11.9) Let r.v. $X_1$ be uniformly distributed across ${ 0, 1}$. Furthermore, require that $X_2 = Y_2 = Y_1 = X_1$ (identically).

In this case,


$\therefore$ $I(X_1 : Y_1) + I(X_2 : Y_2) > I(X_1, X_2 : Y_1, Y_2)$ in this case.

Intuitively, the random variables are distributed identically, so we always only need a single bit to communicate their distribution across a channel. Hence, there will always be a single bit of mutual information across the r.v.’s since their conditional entropy will be zero bits (we know everything we need to know given one variable’s value) and their joint entropy will be a single bit.

Conclusion from the above two exercises: mutual information is neither sub-additive nor super-additive.