2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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)$? $\endgroup$
    – Steve
    Aug 8, 2019 at 6:29
  • $\begingroup$ 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. $\endgroup$
    – Cesare
    Aug 8, 2019 at 6:54

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$
    – Steve
    Aug 8, 2019 at 8:53
  • $\begingroup$ 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). $\endgroup$
    – Cesare
    Aug 8, 2019 at 8:56
  • $\begingroup$ Btw, your proof using the derivative is brilliant! $\endgroup$
    – Cesare
    Aug 8, 2019 at 8:57
  • $\begingroup$ 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). $\endgroup$
    – Steve
    Aug 8, 2019 at 9:02
  • $\begingroup$ Why did you have to introduce the $p_1$ and $p_2$ notation? $\endgroup$
    – Cesare
    Aug 8, 2019 at 12:16

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.