Finding discrete entropy via differential entropy

Question

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?

Answer 1

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.