Consider a discrete trivariate distribution $P(X_1, X_2, Y)$, which satisfies $$ p(x_1, x_2, y) = \min( p(x_1,y), p(x_2,y) ), $$ for all $x_1$ and $x_2$ for which $p(x_1, x_2) > 0$ and for all values of $y$ (including those at which $p(x_1, x_2, y) = 0$). I am trying to show that then the interaction-information is non-negative $$ I(X_1;Y) + I(X_2;Y) - I(X_1 X_2;Y) \ge 0 $$

I need either a rigorous proof or, alternatively, a counterexample that disproves the theorem.

Addendum 1: I use the shorthand notation $p(x_1, x_2, y) := P(X_1=x_1, X_2 = x_2, Y=y)$

Addendum 2: for a similar inequality and its proof see here. This might provide some inspiration. For theoretical references on non-Shannon inequalities see here and here.

Addendum 3: Note that the canonical example of negative interaction-information, the XOR gate, does not satisfy the theorem hypothesis. For the XOR gate $p(x_1, x_2, y) = \min \left( \ p(x_1,y), \ p(x_2,y) \ \right)$ holds for all $x_1, x_2, y$ such that $p(x_1, x_2, y)>0$ but not for all $y$ once we pick $x_1, x_2$ points for which $p(x_1, x_2)>0$, i.e. also the $y$s for which $p(x_1, x_2, y)=0$.

  • 1
    $\begingroup$ Could you supply an example of such a distribution? Without an example, it looks possible that any answers could be discussing a situation that never exists and therefore will be devoid of information. Is it possible "$p$" refers to a cumulative distribution function? $\endgroup$
    – whuber
    Jun 23 '19 at 12:13
  • 2
    $\begingroup$ That's a trivial example, because conditional on $Y,$ almost surely at least one variable is constant. Can you offer any example of substance? $\endgroup$
    – whuber
    Jun 24 '19 at 12:42
  • 1
    $\begingroup$ Hint: what's the information $I(X)$ for a random variable $X$ that is almost surely a constant? $\endgroup$
    – whuber
    Jun 24 '19 at 13:58
  • 2
    $\begingroup$ Cesare, you have flagged my last comment several times. Would you mind explaining what "bigotry" or "abuse" is involved in pointing out an aspect of your question that will help you and others obtain an answer more easily? It's ok to believe my suggestion may be misleading or even wrong, but that's a far cry from the serious claims you are leveling! $\endgroup$
    – whuber
    Jun 24 '19 at 20:30
  • 1
    $\begingroup$ If this is a question from textbook or course, could you link to it somehow (eg, book & page number)? That might provide the context that would help to clarify this. $\endgroup$ Jun 24 '19 at 20:39

Your Answer

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

Browse other questions tagged or ask your own question.