How to prove that the mutual information is subadditive?

Question

Let $\mathbf x=(x_1,...,x_n)$ and $\mathbf y=(y_1,...,y_n)$ be two vectors of random variables. To make things concrete, assume that Alice sends each component $x_j$ through a noisy channel to Bob, who then receives the output $y_j$. The conditional probability to obtain $\mathbf x$ given $\mathbf y$ is $$p(\mathbf y|\mathbf x)=\prod_{j=1}^np_j(y_j|x_j), $$ and for each probability $p_j(y_j|x_j)$ we may define the mutual information $I_j(x_j:y_j)$. I should prove that $$I(\mathbf x:\mathbf y)\le \sum_{j=1}^n I_j(x_j:y_j), $$ that is, the mutual information is subadditive. What is the simplest way to go about this?

Answer 1

Unlike entropy, mutual information can be either subadditive or superadditive.

1. If $A$, $B$, $C$ are bits with equal probabilities and $A=B=C$, then $$ I(A,B:C) = 1,\\ I(A:C) + I(B:C) = 2, $$ therefore $I(A,B:C) < I(A:C) + I(B:C)$.

2. On the other hand, if $A$, $B$, $C$ are bits with equal probabilities and $A \oplus B \oplus C = 0$ ($\oplus$ is XOR), then $$ I(A,B:C) = 1,\\ I(A:C) + I(B:C) = 0, $$ therefore $I(A,B: C) > I(A:C) + I(B:C)$.

source (pg.4)