1
$\begingroup$

Consider two functions $f: \mathcal{X} \to \mathcal{Y}$ and $g: \mathcal{X} \to \mathcal{X}$. In general, I am interested in the case where these functions have a random element, but to keep things simple we can assume they are deterministic. The statement that I am interested in proving or disproving is the following:

$I[X; f(X)] > I[X; f(g(X))]$

Note that this is different from the common statement of the data processing inequality, which would be:

$I[X; g(X)] > I[X; f(g(X))]$

Here $I$ is the mutual information and $X$ is a random variable with support in $\mathcal{X}$.

I have been unable to find a counter example to this statement, though I have tried both construction and numerical simulations (for the case of discrete random variables). My intuition says it should be true, but I have been unable to prove it thus far. My thinking is something along the lines of the data processing inequality, where additional steps of processing can only remove information from the system.

So my questions are the following:

  1. Is the above statement true?

  2. If it is not always true, it seems to be true in many cases. Are there any simple conditions that would imply it is true?

  3. For cases that it is true, does the statement generalize to non-deterministic versions of $f, g$?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Take $\mathscr{X} = \{1,2,3,4\}$ with $X$ uniform on $\{1,2\}$, take $f$ to be any function which identifies $1$ and $2$ but is otherwise injective, and let $g$ be the permutation which acts as $1 \leftrightarrow 3$ and $2 \leftrightarrow 4$. Then $f(g(X))$ perfectly remembers the value of $X$, while $f(X)$ forgets it, which gives $I(X:f(g(X)) = 1$ and $I(X:f(X)) = 0$. $\endgroup$
    – Tobias Fritz
    Commented Oct 30, 2019 at 19:05
  • 1
    $\begingroup$ @TobiasFritz That is a good example, thank you. In the time between your post and my answer, I found this post, in which the OP claims what I believe to be the same statement as mine to be true. I assume that he is also incorrect then? I'm still interested in answers to the remaining two questions. In my numerical experiments I sampled thousands of transition kernels for $f, g$ and the inequality held for all of them. $\endgroup$
    – tnecniv
    Commented Oct 30, 2019 at 19:25
  • $\begingroup$ Yes, I agree that the OP's claim in the second paragraph of the linked question is wrong. I'm afraid that I don't have anything interesting to say about your other two questions. $\endgroup$
    – Tobias Fritz
    Commented Oct 31, 2019 at 0:09

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .