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.
Best Answer
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).$$