0
$\begingroup$

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

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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ Sep 5, 2019 at 13:41
  • $\begingroup$ @Semiclassical: the advantage of "diagonal" is that it makes immediately clear that there can be only zeros beneath and next to each block... $\endgroup$
    – Cesare
    Sep 5, 2019 at 13:46
  • $\begingroup$ But that’s not what diagonal means. Diagonal matrices are zero everywhere except on the main diagonal. $\endgroup$ Sep 5, 2019 at 13:48

1 Answer 1

0
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ Thanks for your answer. I think it goes in the right direction. Obviously the solution has to do with the signal processing inequality, how could I not see that! However, there is something that does not convince me in the first equation you wrote though. Isn't that Bayes rule? $\endgroup$
    – Cesare
    Sep 5, 2019 at 15:56
  • $\begingroup$ @Cesare You could view the first equation as following from Bayes rule or the chain rule for joint distributions. $\endgroup$
    – Stelios
    Sep 5, 2019 at 17:50
  • $\begingroup$ But the Markov chain condition is more stringent. Otherwise every trivariate distribution would form a Markov chain. Or am I missing something? $\endgroup$
    – Cesare
    Sep 5, 2019 at 18:45
  • $\begingroup$ @Cesare What holds for every trivariate distribution is the first equality. It is the second equality that is more stringent and corresponds to the Markov chain property. $\endgroup$
    – Stelios
    Sep 5, 2019 at 20:43
  • $\begingroup$ Oh now I see that :-) $\endgroup$
    – Cesare
    Sep 5, 2019 at 20:45

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .