Mutual information inequality

Question

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

Answer 1

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.