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

OPmeansoriginal poster. I just thought anyone seeing this question would want to know about the other one. $\endgroup$ – Gerry Myerson Aug 14 at 13:13