# Shannon source coding theorem and differential entropy

Loosely speaking, Shannon's source encoding theorem says that there is an encoder with rate at least $$H(x)$$ such that $$n$$ repetitions of the source can be mapped to at least $$nH(x)$$ bits, such that the message can be recovered with high probability.

More precisely, here is a screen grab from Wikipedia:

Note that $$H(X)$$ is the Shannon entropy in the discrete case.

But in the continuous case it is stated to be the differential entropy $$H(X) = -\int p(x) \log p(x) dx$$ where $$p(x)$$ is the PDF of $$X$$.

However, is the latter correct/sensible? As we know, differential entropy can be negative (see Wikipedia for an example). What does it mean to code at a negative rate?

• both the discrete and continuous entropies are like log-volumes. for discrete distributions there's a natural reference point/'zero' to normalize the log to. Commented May 22 at 2:07

For continuous random variables, source coding with finite number of bits always results in error. Lossless source coding is not possible. However there is theory called Rate distortion theory which discussed source coding for continuous random variables.

Rate Distortion Theory: Given a continuous random variable $$X$$, we compress or source code into a discrete random variable $$S$$ such that $$Distortion(X,S) \leq d$$ and $$H(S) \leq R$$. Distortion is some loss function quantifying the error.

So the limits of source coding of continuous random variable is not interms of differential entropy by as the least possible value of rate $$R$$ for the given distortion level upper bound $$d$$. Usually called rate distortion function.

Following is a standard derivation for relation between discrete and continuous entropy:

Differential Entropy: $$\int p(x) \log(p(x)) dx= \lim_{\Delta \rightarrow 0} -\log(\Delta) + H(X_{\Delta})$$

where $$H(X_{\Delta}) = \sum_i \frac{p(x_i)}{\sum_j p(x_j)} \log \left(\frac{p(x_i)}{\sum_j p(x_j)} \right)$$ $$= \sum_i p(x_i) \Delta \log \left( p(x_i) \Delta \right)$$

$$X_{\Delta}$$ can be interpreted as source coded alphabet. Something like $$X_{\Delta} \approx S$$ in Rate distortion theory definition.

In the below i use: $$\sum_j p(x_j) \Delta \rightarrow 1$$

Proof:

There is a standard derivation for this: $$\int p(x) \log(p(x)) dx = \lim_{\Delta \rightarrow 0} \sum_i p(x_i) \log(p(x_i)) \Delta$$
$$= \lim_{\Delta \rightarrow 0} \sum_j p(x_j) \times \sum_i \frac{p(x_i)}{\sum_j p(x_j)} \log \left(\frac{p(x_i)}{\sum_j p(x_j)} \times \sum_j p(x_j) \right) \Delta$$

$$= \lim_{\Delta \rightarrow 0} \sum_j p(x_j) \times \sum_i \frac{p(x_i)}{\sum_j p(x_j)} \log \left(\frac{p(x_i)}{\sum_j p(x_j)} \times \sum_j p(x_j) \right) \Delta$$ $$= \lim_{\Delta \rightarrow 0} \sum_j p(x_j) \times \log\left(\sum_j p(x_j)\right) \Delta + H(X_{\Delta})$$

$$= \lim_{\Delta \rightarrow 0} \sum_j p(x_j) \times \log\left(\Delta \sum_j p(x_j)\right) \Delta - \log(\Delta) + H(X_{\Delta})$$

$$= \lim_{\Delta \rightarrow 0} -\log(\Delta) + H(X_{\Delta})$$

The differential entropy is not exactly analogous to the discrete entropy because, as we more-and-more finely approximate a continuous random variable by a sequence of discrete ones, the discrete entropies diverge. So, differential entropy is defined instead as a difference from the "average" information inherent in the resolution of your discretization.

Negative entropies aren't really a problem, then, because differential entropies are all difference terms to begin with.

Notice that we can combine these to yield $$h(f) = h(g) - D_{KL}(f || g)$$, and from this we can interpret a negative differential entropy to mean "something very far from a normal distribution."
A non-degenerate continuous variable (say a uniform variable in $$[0,a]$$) has an infinite Shannon entropy: it provides an infinite amount of information, we need an infinite amount of bits to code a real number in $$[0,1]$$, and the same applies for $$a=0.5$$ or $$a=2$$ (in spite of three cases having zero, negative or positive differential entropies).