Entropy of distribution with block matrix support

Question

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.

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.

Answer 1

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