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$.

Addendum 4: A suggestion from one of the authors of this paper. IMPORTANT: Note that here the notation $p(x, y, a)$ is used instead of $p(x_1, x_2, y)$! I don't want to modify the notation to avoid introducing errors to his suggestion without noticing it.

Let's say that (x1,y2) and (x2,y2) are “connected” if x1=x2 or y1=y2 (the same column or the same row in the matrix of the distribution). Further, let say take the transitive closure of the “connectedness” on the set of all (x,y) with p(x,y)>0. Now all pairs (x,y) with a positive probability are split into classes of equivalence.

Notation : let Z be a new random variable which represents the index of the class of equivalence for (X,Y).

Claim : H(Z|X) = H(Z|Y)=0. [seems to be trivial]

Question 1: Assume we are given the values of A and Z. Is it true that either X or Y is a deterministic function (a degenerated random variable with a single value)?

Question 2: If the answer to Q1 is positive, is it true that I(X:Y | A Z) = 0 and I(X : Y : A | Z) >= 0

Question 3: If the answers to Q1 and Q2 are positive, can we conclude that I(X : Y : A ) >= 0

  • $\begingroup$ I am checking whether the approach from here can also be applied to this problem. $\endgroup$ – Cesare Aug 14 at 7:07
  • $\begingroup$ OP has raised a related question, mathoverflow.net/questions/338330/… $\endgroup$ – Gerry Myerson Aug 14 at 13:09
  • $\begingroup$ Yes, actually that is my question. Since I can't prove the theorem I am starting to wonder whether the satement is wrong. $\endgroup$ – Cesare Aug 14 at 13:11
  • $\begingroup$ I know it's your question, Cesare – OP means original poster. I just thought anyone seeing this question would want to know about the other one. $\endgroup$ – Gerry Myerson Aug 14 at 13:13
  • $\begingroup$ Sorry, didn't know the meaning of OP $\endgroup$ – Cesare Aug 14 at 13:14

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.