13
$\begingroup$

Differential entropy of Gaussian R.V. is $\log_2(\sigma \sqrt{2\pi e})$. This is dependent on $\sigma$, which is the standard deviation.

If we normalize the random variable so that it has unit variance its differential entropy drops. To me this is counter-intuitive because Kolmogorov complexity of normalizing constant should be very small compared to the reduction in entropy. One can simply devise an encoder decoder which divides/multiples with the normalizing constant to recover any dataset generated by this random variable.

Probably my understanding is off. Could you please point out my flaw?

$\endgroup$
1
  • $\begingroup$ This question is predicated on a false statement: the differential entropy does not necessarily increase when the RV is standardized. The correct effect is fully described at stats.stackexchange.com/questions/415435. $\endgroup$
    – whuber
    Nov 5 '20 at 15:16
17
$\begingroup$

I'll have a go at this, though it's a bit above my head, so treat with sprinkle of salt...

You're not exactly wrong. I think that where your thought experiment falls down is that differential entropy isn't the limiting case of entropy. I'm guessing that because of this, the parallels between it and Kolmogorov complexity are lost.

Let's say we have a discrete random variable $X$. We can calculate its Shannon entropy as follows by summing over all its possible values $x_i$, $$ H(X) = -\sum_i P(X=x_i) \log \big( P(X=x_i) \big). $$

So far so boring. Now let's say that $X$ is a quantised version of a continuous random variable - say, we have density function $p()$ which generates samples from the set of real numbers, and we turn this into a histogram. We'll have a fine enough histogram that the density function is essentially linear. In that case we're going to have an entropy something like this, $$ H(X) \approx -\sum_{i} p(X=x_i) \delta x \log \big( p(X=x_i) \delta x \big), $$ where $\delta x$ is the width of our histogram bins and $x_i$ is the midpoint of each. We have a product inside that logarithm - let's separate that out and use the property of probability distributions summing to 1 to move it outside the summation, giving us $$ H(X) \approx -\log \big( \delta x \big) -\sum_{i} p(X=x_i) \delta x \log \big( p(X=x_i) \big). $$

If we take the limit, letting $\delta x \rightarrow dx$ and turning the summation into an integration, our approximation becomes exact and we get the following, $$ H(X) = -\log \big( dx \big) -\int_x p(X=x) \log \big( p(X=x) \big)dx. $$

The term on the right hand side is the differential entropy. But look at that horrid $\log \big( dx \big)$ term. We have to ignore it to avoid all our answers being NaN. I'm afraid it means that differential entropy is not the limiting case of Shannon entropy.

So, we lose some properties. Yes, rescaling your data changes the differential entropy - differential entropy is sort of a measure of how 'closely packed' the pdf is. If you rescale it, then this changes. Another fun property is that it can go negative, unlike Shannon entropy - try setting $\sigma$ really really small and see what happens. Losing the link to Kolmogorov complexity I think is just another casualty.

Fortunately we're not entirely lost. Kullback–Leibler divergences, and by extension mutual information, are fairly well behaved as all the $\delta$'s cancel out. For example, you could calculate $$ \int_x p(X=x) \log \Bigg( \frac{p(X=x)}{q(X=x)} \Bigg) dx $$ where $q(X)$ is some reference distribution - say, a uniform one. This is always positive, and when you rescale the variable $X$ it changes both $p(X)$ and $q(X)$, so the results are far less severe.

$\endgroup$
5
  • $\begingroup$ Thanks. That's very interesting. I didn't know there was such a gimmick in the theory. $\endgroup$ Feb 18 '13 at 18:10
  • 1
    $\begingroup$ The notation $\log(\mathrm d x)$ is not really very meaningful, but we can turn some of your exposition into something a little more precise. Indeed, if the density $p(x)$ is Riemann integrable, then $-\sum_{i} p(x_i) \delta x \log p(x_i) \to h(X)$ as $\delta x \to 0$. An interpretation of this that you will often see is that an $n$-bit quantization of a continuous random variable has entropy of about $h(X) + n$. $\endgroup$
    – cardinal
    Feb 18 '13 at 18:23
  • 1
    $\begingroup$ @Cardinal. Yeah, I knew that $\log(d x)$ was a horribly odd thing to talk about when I was writing it. However I think going about it in this manner helps really drive home why differential entropy really really isn't entropy. $\endgroup$
    – Pat
    Feb 19 '13 at 9:14
  • $\begingroup$ @Cagdas - I dunno if I'd call it a gimmick. It's just measuring a different thing. And as cardinal points out, it has some uses. As for whether it'll break when applied to the binominal distribution, well, depends how you're going to apply it :). Probably worth starting a new topic if you're not sure. $\endgroup$
    – Pat
    Feb 19 '13 at 9:16
  • $\begingroup$ I thought that entropy is obviously different from Kolmogorov complexity when one considers pseudo-random number generators. $\endgroup$ Dec 23 '17 at 14:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.