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.



A question about mutual information
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).$$


