1
$\begingroup$

Let's say you have a number $x$, and a priori, you know that $x \in [0, 1)$ (each value from 0 to 1 is equally likely.) Then a wizard comes and tells you that $x \in [a, b) \subseteq [0, 1)$. How much information does this give you?

It would seem to be $-\log_2(b-a)$ bits, but I don't know how to prove this, since both a priori and a posteriori have an infinite amount of entropy.

The reason I think $-\log_2(b-a)$ bits seems reasonably is it seems to agree with examples.

$-\log_2(1-0) = 0$, which is true, since no information is conveyed.

$-\log_2(\frac12 - 0) = 1$, which seems reasonably, since it would give you the first binary digit of $x$

In general, $-\log_2(b-a=\frac1{2^n})=n$, seems reasonable, as it gives you about $n$ binary digits.

$\endgroup$
1
$\begingroup$

Your intuition is correct but your calculation of entropy is not, the differential entropy of the uniform distribution on $(0,\frac{1}{2^n})$ is $$-2^n\int_0^{\frac{1}{2^n}}\log_22^ndx=-n$$

The concept of entropy for continuous random variables (differential entropy) is not well defined, since a real number requires a theoretically infinite number of bits to precisely specify. To quote Wikipedia,

differential entropy is not a limit of the Shannon entropy for n → ∞. Rather, it differs from the limit of the Shannon entropy by an infinite offset

I believe conditional entropy is likely to give you an equally nonsensical answer.

Instead you want to look at the KL-divergence, which tells you the expected number of extra bits required to specify a random variable with distribution $p$, given that your best model for it is based on distribution $q$. Unlike entropy, the KL-divergence is well defined for continuous random variables. Thus setting $X\sim \text{Unif}(a,b)$ and assuming our best guess at its distribution is $\text{Unif}(0,1)$, we have,

$$\text{D}_{\text{KL}}(p\;||\;q)=\int p\log\frac{p}{q}=\int_a^b\frac{1}{b-a}\log_2\frac{1}{b-a}dx=-\log_2(b-a)$$

So this says that on average we expect to have to send one extra bit per transmission if $X\sim \text{Unif}(0,\frac{1}{2})$, but all the receiver knows is that it falls uniformly on $(0,1)$, since, as you say, a single bit is needed to tell the receiver which half of the unit interval the real number lies in.

$\endgroup$
0
$\begingroup$

$\def\pp{\mathbb{P}}$The usual definition of conditional entropy of $A$ given $B$ works. It is defined as the expected conditional entropy, which is the expected weighted negative log conditional probability. This corresponds to your correct intuition since in this case the weight function is uniform since every value in $[0,1)$ is equally likely. You can see more details at Wikipedia, which will also allow you to calculate the conditional entropy if the distribution is not uniform.

$\endgroup$

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.