# Mutual information inequality

I am trying to prove three inequalities that would help me solve the proof of a larger theorem.

Let $$P(X,Y)$$ be a discrete bivariate distribution and $$I(X;Y) = \sum_{i,j} p(x_i, y_j) \log \frac{p(x_i, y_j)}{p(x_i)p(y_j)}$$ the mutual information between $$X$$ and $$Y$$.

Let's call $$\bar{P}(X,Y)$$ the function (it is not a probability distribution) obtained by $$P(X,Y)$$ by adding $$0 \le a \le 1$$ to $$p(x_{\bar{i}}, y_{\bar{j}})$$ for a given pair $$\bar{i}, \bar{j}$$ $$\bar{p}(x_{\bar{i}}, y_{\bar{j}}) = p(x_{\bar{i}}, y_{\bar{j}}) + a \quad \Rightarrow \quad \bar{p}(x_{\bar{i}}) := \sum_j \bar{p}(x_i, y_j) = p(x_i) + a$$ and $$I^a(X;Y) := \sum_{i,j} p(x_i, y_j) \log \frac{\bar{p}(x_i, y_j)}{\bar{p}(x_i)p(y_j)}$$

Does the relationship $$0 \le I^a(X:Y) \le I(X:Y) \qquad \text{(inequality 1)}$$ hold for any $$a$$?

Furthermore, if $$0 \le a \le p(x_{\bar{i}}, y_{\bar{j}})$$, do the following relationships also hold (I use the apex $$-a$$ to indicate that $$a$$ is subtracted instead than added to $$p(x_{\bar{i}}, y_{\bar{j}})$$)? $$I(X;Y) \le I^{-a}(X;Y) \qquad \text{(inequality 2)}$$ $$I^{-a}(X;Y) - I(X;Y) \le I(X;Y) - I^a(X;Y) \qquad \text{(inequality 3)}$$

• To make sure it is not a typo: For $I^a(X;Y)$ you are only adjusting $\bar{p}(x_i)$ but still use the initial $p(y_j)$? Aug 8 '19 at 6:29
• Now that you point it out I notice that it is really crucial. Yes, $P(Y)$ has to stay the same. In the end, inequality 1 is also what happens to the MI when going from a joint $P(X_1, X_2,Y)$ to on one of the marginals. Aug 8 '19 at 6:54

## 1 Answer

First, in general $$I^a(X;Y) \geq 0$$ does not hold. One can find easy counterexamples with just two states.

The other part of inequality (1) does hold. For inequality (2), the reverse does actually hold. And with that, inequality (3) is trivially true.

We show that $$\frac{\partial I^a}{\partial a} \geq 0$$ for $$a \leq 0$$ and $$\frac{\partial I^a}{\partial a} \leq 0$$ for $$a \geq 0$$. So $$a \mapsto I^a$$ is maximal at $$a=0$$.

I write $$p(x) = p_1(x)$$ and $$p(y) = p_2(y)$$ for clarity. It holds \begin{align} \frac{\partial I^a(X;Y)}{\partial a} &= \frac{\partial}{\partial a}\Big(p(x_{\bar{i}}, y_{\bar{j}}) \log\frac{p(x_{\bar{i}}, y_{\bar{j}}) + a}{(p_1(x_{\bar{i}})+a)p_2(y_{\bar{j}})} + \sum_{j \neq \bar{j}} p(x_{\bar{i}}, y_j) \log\frac{p(x_{\bar{i}}, y_{j})}{(p_1(x_{\bar{i}})+a)p_2(y_{j})}\Big) \\ &= \Big(\frac{p(x_{\bar{i}}, y_{\bar{j}})}{p(x_{\bar{i}}, y_{\bar{j}}) + a} - \frac{p(x_{\bar{i}}, y_{\bar{j}})}{p_1(x_{\bar{i}})+ a}\Big) - \sum_{j \neq \bar{j}} \frac{p(x_{\bar{i}}, y_j)}{p_1(x_{\bar{i}})+a} \\ &= \frac{p(x_{\bar{i}}, y_{\bar{j}})}{p(x_{\bar{i}}, y_{\bar{j}})+a} - \frac{p_1(x_{\bar{i}})}{p_1(x_{\bar{i}})+a} \end{align} And since $$[0, 1] \ni x\mapsto \frac{x}{x+a}$$ is increasing for $$a \geq 0$$ and decreasing for $$a \leq 0$$, and $$p_1(x_{\bar{i}}) \geq p(x_{\bar{i}}, y_{\bar{j}})$$, the claim follows.

• Not sure about a condition for $I^a(X;Y) \geq 0$. Could you make your counterexample more concrete? I might have gotten the terms confused with $I^{-a}$, I basically calculated with $I^a$ but also allowed $a \leq 0$. Of course, there might also be an error in my calculations. Aug 8 '19 at 8:53
• Yes, that is exactly what I mean. You seem to show that for negative $a$ the (pseudo) MI would increase. So that would imply that inequality 2 holds. Am I missing something? (sorry I deleted the previous comment cause I wanted to edit it and you were faster at replying). Aug 8 '19 at 8:56
• Btw, your proof using the derivative is brilliant! Aug 8 '19 at 8:57
• Well, for negative $a$, the curve $a \mapsto I^a(X;Y)$ is increasing, so the highest value is at $a=0$, which shows the reverse of inequality (2). Aug 8 '19 at 9:02
• Why did you have to introduce the $p_1$ and $p_2$ notation? Aug 8 '19 at 12:16