# Finding discrete entropy via differential entropy

In a recent math.se question the following was asked which I have slightly edited.

" Consider a fixed and given $n$ by $n$ matrix $M$ whose elements are chosen from $\{-1,1\}$. Consider also a random vector $v$ whose elements are chosen from $\{-1,1\}$.

We know that $H(Mv) = n$ if and only if $M$ is non-singular. Here $H$ is the Shannon entropy of a discrete random variable (in bits).

[..]

The differential entropy of a multivariate Gaussian is known to be $\frac{1}{2}\log((2\pi e)^n \det(MM^T)$ bits.

There is a correction factor one has to apply when going from discrete to continuous entropy (see Theorem 9.3.1 from Cover and Thomas). However, we would need this correction term to somehow deal with the fact that the entropy is constant as long as $\det(M)>0$. That is it makes no difference to the entropy how small or large the determinant is as long as it is not zero.

What is the correction term that deals with this seeming contradiction?

"

A user called leonbloy gave an answer that he/she admitted was not rigorous. I copy it below very slightly edited.

"

We get that the entropy of a discrete (lattice) distribution with "cell size" $\Delta$ is related to the differential entropy of the continuous distribution that approximates it by

$$H_Y \to h_Z -\log \Delta$$

Now, it's a known result in multivariate analysis that the change in volume induced by a transformation $(s_1, \cdots s_n)=g(t_1, \cdots t_n)$ is measured by the Jacobian. In particular, if the transformation is linear $s =A t$ then the Jacobian is the determinant of the matrix: $J=|A|$.

In our case, we have $y=Mv$. The cells in $v$ space ($v_i \in \{-1,1\}$) have size $2^n$. Hence the cells in $y$ space have size $|M| \, 2^n$. Further, the differential entropy of a Gaussian with covariance $\Sigma=M M^t$ is $\frac{1}{2} \log[(2\pi e)^{n}|\Sigma|]= \frac{n}{2} \log(2\pi e)+\log |M|$

Then, assuming that CLT applies and that $|M|\ne 0$:

$$H_Y \to \frac{n}{2} \log(2\pi e)+\log |M| -\log (|M| \, 2^n)= \frac{n}{2} \log(\pi e/2)$$

Hence, the entropy is independent of $|M|$, as it should be.

"

This is intriguing because it gives approximately $1.047n$ instead of $n$. This got me wondering:

Can this line of argument be made both reasonably rigorous and be made to give the correct answer? That is, is it possible to get the correct entropy of $n$ for the discrete entropy $H(Mv)$ by applying Theorem 9.3.1 from Cover and Thomas in this multivariate case?

• strange, a very similar question was asked by another user (and now deleted): mathoverflow.net/questions/227434/…? Jan 5 '16 at 17:27
• @CarloBeenakker Not so strange! Is that user the author of the question my question points to and quotes? If so, I assume they deleted the question here when they got the math.se answer (although I can't see the question you are pointing to). Jan 5 '16 at 18:03

A believe that a different way to go from differential entropy to discrete entropy is the following formula.

Let $h(X_1,\dots,X_n)$ be the differential entropy of some random $n$-tuple $X_1,\dots,X_n$ and $H(Y_1,\dots,Y_n)$ be the discrete entropy; we require that $Y_1,\dots,Y_n$ be real-valued. In other words, if $p$ is the joint density of $X_1,\dots,X_n$ then $$h= -\int p(x_1,\dots,x_n) \log p(x_1,\dots,x_n ) dx_1\dots dx_n$$ and $$H = -\sum_{\vec{v}} Prob( (Y_1,\dots,Y_n)=\vec{v}) \log \left(Prob( (Y_1,\dots,Y_n)=\vec{v})\right),$$ where the sum is taken over all vectors in $\mathbb{R}^n$.

The formula is: $$H(Y_1,\dots,Y_n) = \lim_{t\to 0} h(Y_1 + tG_1,\dots,Y_n+tG_n) - n\log(t)$$ where $G_1,\dots,G_n$ are $n$ centered variance $1$ Gaussian random variables which are independent of each other and of $(Y_1,\dots,Y_n)$.

This formula explains why despite the fact that differential entropy changes when one applies a one-to-one function to $Y_1,\dots,Y_n$, the discrete entropy does not. Indeed if you set $Y_j' = F_j(Y_1,\dots,Y_n)$, then the RHS of the formula will involve a term which is (roughly) $\log \det \left(\left( \partial_i F_j\right)_{ij} \right)$, which disappears in the limit $t\to 0$ being negligible compared to $n\log t$.

(I am adding a few more details that we requested in the comments).

Take the case $n=1$ for simplicity. Then the law of $Y=Y_1$ has the form $\sum \alpha_j \delta_{x_j}$ with $\alpha_j\geq 0$, $\sum \alpha_j =1$, and $\delta_x$ denoting the point mass at $x$. Thus $H(Y)=-\sum \alpha_j \log \alpha_j$.

The law of $Y+tG$ is the convolution of the law of $Y$ and a Gaussian of variance $t^2$ centered at zero and so has density $$p_t(x) = \frac{1}{\sqrt{2\pi}} \sum_j \alpha_j t^{-1} \exp( -(x-x_j)^2/t^2)$$

Let us now compute $h(Y+tG) = - \int p_t(x) \log p_t(x) dx$:

$$-\frac{1}{\sqrt{2\pi}} \int \sum_j \alpha_j \frac{e^{ - \frac{(x-x_j)^2}{t^2} }}{t} \left[-\log t + \log \left(\sum \alpha_k e^{ - \frac{(x-x_k)^2}{t^2} }\right)\right]dx.$$

Noting that $\int \frac{1}{t} e^{ - \frac{(x-x_j)^2}{t^2} }=\sqrt{2\pi}$ the first term in the sum inside $[...]$ gives us $\sum \alpha_j \log t = \log t$. The second term is $$-\frac{1}{\sqrt{2\pi}} \int \sum_j \alpha_j \frac{e^{ - \frac{(x-x_j)^2}{t^2} }}{t} \log \left(\sum \alpha_k e^{ - \frac{(x-x_k)^2}{t^2} }\right)dx,$$ which because $-\frac{1}{\sqrt{2\pi}} \int \sum_j \alpha_j \frac{e^{ - \frac{(x-x_j)^2}{t^2} }}{t}$ converges weakly to $\sum \alpha_j \delta_{x_j}$ gives us precisely $-\sum \alpha_j \log \alpha_j$ (notice that $k=j$ gets forced as well).

Thus $h(Y+tG) -\log t \to H(Y)$.

The multi-dimensional case is essentially the same.

• Would you mind spelling out a little more what you get in the end? In particular, do you get the correct discrete entropy of $n$ this way? Jan 7 '16 at 20:50
• Thank you but I am not clear on some details. As a first trivial question, doesn't $\log{t}\to -\infty$ as $t$ tends to $0$? How do you get the entropy of $n$ from the RHS? Jan 15 '16 at 14:36
• Thank you this 1d analysis. The 1d case is clear and I was in fact happy with it before. I would be very grateful if you could show how you can apply the same reasoning to the multidimensional $Mv$. Part of my confusion is what the approach would give if $M$ had fewer rows than columns. This presumably would then depend crucially on the entries in $M$. But even understanding the $n$ by $n$ case would be a great start. Jan 18 '16 at 11:48
• I think the proof of the formula relating differential and discrete entropy in the multi-dimensional case is exactly the same -- in fact the only change needed in the argument is the replacement integration with respect to $dx$ by integration with respect to $dx_1 ... dx_n$ (the extra factor of $n$ in front of $\log t$ comes from the joint variance of $G_1,\dots,G_n$). To see the behavior when you apply your matrix $M$, just use the formula to compute $h((\sum_{i} M_{ij} Y_i)_j )$. Jan 20 '16 at 1:37