1
$\begingroup$

Let $A$, $B$ and $C$ be 3 discrete random variables. If $A$ and $B$ are independent ($I(A;B) = 0$, where $I$ represents the mutual information), how can we prove that $I(A;B|C)=0$? When I draw a Venn diagram this seems trivially true, but I just cannot find a way to prove it.

$\endgroup$
  • 1
    $\begingroup$ Have you checked the relevant definitions? Have you tried constructing counterexamples? By the way, can you edit the question to include the definition of the notation $I$? $\endgroup$ – Apass.Jack Mar 13 at 14:14
  • $\begingroup$ @Apass.Jack I know the basic definitions of the information measures, but I am not familiar with the field and the only way I can use to tackle problems in information theory is to draw the Venn diagrams. If the statement is not true in general, could you give me some hints on how to construct the counter-example? $\endgroup$ – hklel Mar 13 at 19:23
3
$\begingroup$

$I(A;B\mid C)$ indicates "the reduction in the uncertainty of $A$ due to knowledge of $B$ when $C$ is given".

To find an example where $I(A;B\mid C)\not= 0$, we can see if the combination of $B$ and $C$ can help determine $A$ even though knowing $B$ alone does not help at all.

So let us try to create $A$ from the combination of $B$ and $C$. Let $B$ and $C$ be two simplest non-trivial independent random variables, $$P(B=0, C=0)=P(B=0, C=1)=P(B=1, C=0)=P(B=1, C=1)=1/4.$$ Let $A$ be 0 if $B$ and $C$ turns out the same and 1 otherwise.

We can check that $A$, $B$ and $C$ are pairwise independent. However, given the values of any two of them, the third one is determined. (In modulo arithmetic, $B+C=A(\bmod 2)$). When $C$ is given, we will not know anything more about $A$; if $B$ is known additionally, we will know $A$ completely. The above shows how we can find and understand an example. Beginners are encouraged to verify various "obvious" (or "obscure") claims above by using the corresponding definitions.


Exercise. Verify that $I(A;B)=0$ and $I(A;B\mid C)=1$ in the example above.

$\endgroup$
3
$\begingroup$

Your claim is false. Let $A,B,C$ range uniformly over the set $$ \{(x,y,z) \in \{0,1\}^3 : x \oplus y \oplus z = 0 \}. $$ On the one hand, $I(A;B) = 0$. On the other hand, $I(A;B|C) = 1$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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