1
$\begingroup$

The minimum description length of the realization of a random variable $x$ is given by the entropy of its probability mass function. It can be asymptotically communicated at this rate with an optimal coding. But that's for just one $x$ from the optimal coding table. How do we cover the whole support efficiently? (Of course, we'll have issues with quantization of real valued $x$-s in our code table, however optimized it's going to be.)

Viewing it differently, entropy of the representation of a generic probability distribution with CDF $F(x)$, where $F(x) \sim p(F(x))$ on some space of distributions $D$, seems to be bounded from above by entropy of uniform $p$ on space $D$: $-\int_D{p(F(x))\ln{p(F(x))}dF(x)}$. But this is clearly not a sharp maximum description length bound (probably need to introduce some reasonable restrictions).

Looks like I'm missing something obvious, any ideas would be appreciated...

Oh, and this has nothing to do with differential vs discrete entropy, the same question can be posed for the latter case.

[Updated after Peter Shor's comments; also cleaned up language and formulations a bit.]

$\endgroup$
9
$\begingroup$

You're confusing the Shannon entropy of a discrete probability distribution with the differential entropy of a continuous probability distribution. The minimum distribution length is only given by the Shannon entropy for discrete probability distributions.

What the fact that the differential entropy is 0 for this probability distribution means is that for large $k$, you can approximate this random variable with an expected error of $1/2^k$ using $k$ bits. If the differential entropy were $\ell$, you could approximate it with an error of $1/2^k$ using $k+\ell$ bits.

$\endgroup$
  • $\begingroup$ Thank you! It's clear that I can't transmit continuously distributed messages without error, so yes, my terminology is inaccurate, apologies. My bigger concern is how to represent mapping $\mathbb{R} \mapsto [0,1]$ (ie full $F(x)$) and how to bound its entropy. $\endgroup$ – Preston May 31 '14 at 4:09
  • $\begingroup$ I don't understand your concern. You're mapping the entire real line to the unit interval? How? Do maps have entropies associated with them? I thought probability distributions had entropies associated with them. $\endgroup$ – Peter Shor May 31 '14 at 12:12
  • $\begingroup$ Say, my friend asks me about the distance to the nearest gas station in meters. I know that it's represented by a certain probability distribution, e.g. Laplace. I would like to pass this information to my friend without giving the formula of the corresponding CDF (my friend hates math). The entropy we are interested in is the entropy of this message to my friend. $\endgroup$ – Preston May 31 '14 at 13:30

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.