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.


1 Answer 1


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

  • $\begingroup$ Thank you for the quick counterexample! $\endgroup$
    – DeepC
    Apr 27, 2022 at 13:19
  • $\begingroup$ @DeepC : You are welcome. $\endgroup$ Apr 27, 2022 at 13:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.