# A question about mutual information

Let $$A$$ and $$B$$ be two, possibly dependent, random variables, and let $$X$$ be a random variable independent of $$(A,B)$$. For simplicity, let's concern ourselves with discrete random variables. Is the following inequality always true?

$$I(A+X : B+X) \geq I(A:B) \label{eq:conj} \tag{*}$$

This is clearly true when $$A$$ and $$B$$ are independent, as the RHS is then $$0$$. At the other extreme, it is also true when $$A = B$$ since the RHS is $$H(A)$$ while the LHS is $$H(A+X)$$. And, $$H(A+X) \geq H(A+X~|~X) = H(A~|~X) = H(A)$$, where the last equality uses $$A\bot X$$. On the other hand, I cannot see a proof even when $$B = f(A)$$ for some deterministic function $$f$$.

It is not too hard to see if we added $$X$$ to only one of $$A$$ or $$B$$, the mutual information inequality would be flipped. That is, $$I(A+X: B) \leq I(A:B)$$. Intuitively this makes sense: a random variable plus noise gives less information about another random variable than without the noise. However, when we add (the same) $$X$$ to both $$A$$ and $$B$$ and ask for the mutual information between them, I have no good intuition.

The setting in which \eqref{eq:conj} arose, $$X$$ is a Bernoulli, and $$A$$ and $$B$$ are sums of iid Bernoullis with common elements. More precisely, $$X_1, \ldots, X_n$$ are iid Bernoullis, and $$A = \sum_{i\in S} X_i$$ and $$B = \sum_{j\in T} X_j$$ where $$S,T$$ are (potentially intersecting) subsets of $$\{1,2,\ldots, n\}$$. I experimentally verified \eqref{eq:conj} for small $$n$$.

Any help/pointers would be appreciated.

This is not true in general. E.g., let each of the random variables $$A,B,X$$ take values in the set $$\{1,2\}$$. Let the matrix $$(p_{a,b}\colon a=1,2,\,b=1,2)$$ of the probabilities $$p_{a,b}:=P(A=a,B=b)$$ be the following matrix: $$\frac1{10^4}\left( \begin{array}{cc} 1456 & 3987 \\ 4533 & 24 \\ \end{array} \right);$$ in particular, $$p_{1,1}=\dfrac{1456}{10^4}$$. Let $$P(X=1)=\frac{8201}{10000}=1-P(X=2).$$
Then $$I(A+X:B+X)=0.335\ldots\not\geq 0.342\ldots=I(A:B).$$