# Entropy of distribution with block matrix support

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

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.

• I’m not sure why “block diagonal” is what you’re reaching for, since even visually this isn’t diagonal. But there’s nothing stopping you from calling this a block matrix. I’m tempted to call this a sparse block matrix, but it’s ambiguous whether that sparseness applies to the individual blocks or just the block structure. Sep 5, 2019 at 13:41
• @Semiclassical: the advantage of "diagonal" is that it makes immediately clear that there can be only zeros beneath and next to each block... Sep 5, 2019 at 13:46
• But that’s not what diagonal means. Diagonal matrices are zero everywhere except on the main diagonal. Sep 5, 2019 at 13:48

Consider the joint distribution of $$B_1, X_1, X_2$$ and note that it holds \begin{align} P(B_1, X_1, X_2) &= P(B_1|X_1,X_2) P(X_1,X_2)\\ &=P(B_1|X_1) P(X_1|X_2) P(X_2), \end{align} which means that $$B_1, X_1, X2$$ form a Markov chanin $$X_2 \rightarrow X_1 \rightarrow B_1$$. From the data processing inequality, it holds $$\tag{1} I(X_2;B_1)\leq I(X_2;X_1).$$
Similarly, it can be shown that $$B_1\rightarrow X_2 \rightarrow B_2$$, which means $$\tag{2} I(B_1;B_2)\leq I(B_1;X_2).$$
From (1) and (2), it follows that $$I(B_1;B_2) \leq I(X_1,;X_2).$$