# How to prove that the mutual information is subadditive?

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?

• Are you certain that what you are trying to prove is actually provable or are you trying out a new proof? Jul 25, 2021 at 1:43
• @QuestionEverything In all honesty, this was given as an exercise in my course, so I hope my professor wasn't trolling us :-) Jul 25, 2021 at 1:48
• I see, :) I haven't seen this proof before. Jul 25, 2021 at 2:14
• @DaftWullie Yes, it is. I hope it's not off-topic for the site... I'm posting here by default as all this was done in a course in quantum information theory. After all, the tag information-theory is also dedicated to 'information theory in the classical sense'. Jul 26, 2021 at 12:59
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)$$.