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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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