2
$\begingroup$

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?

$\endgroup$
5
  • $\begingroup$ Are you certain that what you are trying to prove is actually provable or are you trying out a new proof? $\endgroup$ Jul 25, 2021 at 1:43
  • $\begingroup$ @QuestionEverything In all honesty, this was given as an exercise in my course, so I hope my professor wasn't trolling us :-) $\endgroup$
    – user15135
    Jul 25, 2021 at 1:48
  • $\begingroup$ I see, :) I haven't seen this proof before. $\endgroup$ Jul 25, 2021 at 2:14
  • 1
    $\begingroup$ What is quantum about this? It seems to be a question about classical information theory. $\endgroup$
    – DaftWullie
    Jul 26, 2021 at 6:50
  • $\begingroup$ @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'. $\endgroup$
    – user15135
    Jul 26, 2021 at 12:59

1 Answer 1

1
$\begingroup$

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)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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