Let $P(X_1,X_2)$ be a discrete bivariate distribution that has the form shown in the figure below, i.e. its support can be split into blocks that do not overlap on either dimensions.

Block structure of P(X_1,X_2)

Let's build $P'(B_1,B_2)$ obtained from $P(X_1,X_2)$ by integrating (summing) the values within each block. I would like to show that the following inequality holds $$ H(X_1) + H(X_2) - H(X_1,X_2) \ge H'(B_1) + H'(B_2) - H'(B_1,B_2) $$ where $H$ denotes entropy values computed with respect to $P(X_1,X_2)$ and $H'$ entropy values computed using $P'(X_1,X_2)$. Proving the inequality will allow me to prove this theorem.

Question 1: Any suggestion on how to prove this?

Question 2: How would you call a matrix like the one above? According to wikipedia the name "block diagonal matrix" applies only if the matrix and the blocks are squares.


You'd like to show that when you "coarse grain" the values of two random variables, then the mutual information between them cannot increase: $I(B_1; B_2) \le I(X_1;X_2)$. This is true, and more generally any kind of "post-processing" can only destroy mutual information.

Lemma: If $X$ and $Z$ are independent conditional on $Y$ (e.g. if $Z$ is a function of $Y$), then $I(X;Z) \le I(X;Y)$.
Proof: By the chain rule for information (Theorem 2.5.2 of Cover and Thomas), we can express $I(X;Y,Z)$ in two different ways: $$ I(X;Z) + \underbrace{I(X;Y|Z)}_{\ge 0} = I(X;Y,Z) = I(X;Y) + \underbrace{I(X;Z|Y)}_{=0} $$ Since $X$ and $Z$ are independent conditional on $Y$, we have that $I(X;Z|Y)=0$, and all the terms (specifically $I(X;Y|Z)$) must be non-negative, so we have $I(X;Z) \le I(X;Y)$.

Since $B_1$ is a function of $X_1$ and $B_2$ is a function of $X_2$, you get the result you want by applying this lemma twice: $$ I(B_1;B_2) \le I(X_1; B_2) \le I(X_1; X_2). $$

  • $\begingroup$ It is really a quite embarassing that I have not seen the signal processing inequality in my own question, right now I want to hide myself :-) Thanks for your time and your answer. $\endgroup$
    – Cesare
    Sep 5 '19 at 18:56

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.