Limiting density of discrete points

Short description: Notion in information theory

In information theory, the limiting density of discrete points is an adjustment to the formula of Claude Shannon for differential entropy.

It was formulated by Edwin Thompson Jaynes to address defects in the initial definition of differential entropy.

Definition

Shannon originally wrote down the following formula for the entropy of a continuous distribution, known as differential entropy:

[math]\displaystyle{ h(X)=-\int p(x)\log p(x)\,dx. }[/math]

Unlike Shannon's formula for the discrete entropy, however, this is not the result of any derivation (Shannon simply replaced the summation symbol in the discrete version with an integral), and it lacks many of the properties that make the discrete entropy a useful measure of uncertainty. In particular, it is not invariant under a change of variables and can become negative. In addition, it is not even dimensionally correct. Since [math]\displaystyle{ h(X) }[/math] would be dimensionless, [math]\displaystyle{ p(x) }[/math] must have units of [math]\displaystyle{ \frac{1}{dx} }[/math], which means that the argument to the logarithm is not dimensionless as required.

Jaynes argued that the formula for the continuous entropy should be derived by taking the limit of increasingly dense discrete distributions. Suppose that we have a set of [math]\displaystyle{ N }[/math] discrete points [math]\displaystyle{ \{x_i\} }[/math], such that in the limit [math]\displaystyle{ N \to \infty }[/math] their density approaches a function [math]\displaystyle{ m(x) }[/math] called the "invariant measure":

[math]\displaystyle{ \lim_{N \to \infty}\frac{1}{N}\,(\mbox{number of points in }a\lt x\lt b)=\int_a^b m(x)\,dx. }[/math]

Jaynes derived from this the following formula for the continuous entropy, which he argued should be taken as the correct formula:

[math]\displaystyle{ \lim_{N \rightarrow \infty} H_{N}(X) = \log(N) - \int p(x)\log\frac{p(x)}{m(x)}\,dx. }[/math]

Typically, when this is written, the term [math]\displaystyle{ \log(N) }[/math] is omitted, as that would typically not be finite. So the actual common definition is

[math]\displaystyle{ H(X)=- \int p(x)\log\frac{p(x)}{m(x)}\,dx. }[/math]

Where it is unclear whether or not the [math]\displaystyle{ \log(N) }[/math] term should be omitted, one could write

[math]\displaystyle{ H_{N}(X) \sim \log(N) + H(X). }[/math]

Notice that in Jaynes' formula, [math]\displaystyle{ m(x) }[/math] is a probability density. For any finite [math]\displaystyle{ N }[/math] that [math]\displaystyle{ m(x) }[/math] is a uniform density over the quantization of the continuous space that is used in the Riemann sum. In the limit, [math]\displaystyle{ m(x) }[/math] is the continuous limiting density of points in the quantization used to represent the continuous variable [math]\displaystyle{ x }[/math].

Suppose one had a number format that took on [math]\displaystyle{ N }[/math] possible values, distributed as per [math]\displaystyle{ m(x) }[/math]. Then [math]\displaystyle{ H_{N}(X) }[/math] (if [math]\displaystyle{ N }[/math] is large enough that the continuous approximation is valid) is the discrete entropy of the variable [math]\displaystyle{ x }[/math] in this encoding. This is equal to the average number of bits required to transmit this information, and is no more than [math]\displaystyle{ \log(N) }[/math]. Therefore, [math]\displaystyle{ H(X) }[/math] may be thought of as the amount of information gained by knowing that the variable [math]\displaystyle{ x }[/math] follows the distribution [math]\displaystyle{ p(x) }[/math], and is not uniformly distributed over the possible quantized values, as would be the case if it followed [math]\displaystyle{ m(x) }[/math]. [math]\displaystyle{ H(X) }[/math] is actually the (negative) Kullback–Leibler divergence from [math]\displaystyle{ m(x) }[/math] to [math]\displaystyle{ p(x) }[/math], which is thought of as the information gained by learning that a variable previously thought to be distributed as [math]\displaystyle{ m(x) }[/math] is actually distributed as [math]\displaystyle{ p(x) }[/math].

Jaynes' continuous entropy formula has the property of being invariant under a change of variables, provided that [math]\displaystyle{ m(x) }[/math] and [math]\displaystyle{ p(x) }[/math] are transformed in the same way. (This motivates the name "invariant measure" for m.) This solves many of the difficulties that come from applying Shannon's continuous entropy formula. Jaynes himself dropped the [math]\displaystyle{ \log(N) }[/math] term as it was not relevant to his work (maximum entropy distributions), and it is somewhat awkward to have an infinite term in the calculation. Unfortunately, this cannot be helped if the quantization is made arbitrarily fine, as would be the case in the continuous limit. Note that [math]\displaystyle{ H(X) }[/math] as defined here (without the [math]\displaystyle{ \log(N) }[/math] term) would always be non-positive, because a KL divergence would always be non-negative.

If it is the case that [math]\displaystyle{ m(x) }[/math] is constant over some interval of size [math]\displaystyle{ r }[/math], and [math]\displaystyle{ p(x) }[/math] is essentially zero outside that interval, then the limiting density of discrete points (LDDP) is closely related to the differential entropy [math]\displaystyle{ h(X) }[/math]:

[math]\displaystyle{ H_{N}(X) \approx \log(N) - \log(r) + h(X). }[/math]

Further reading

• Jaynes, E. T. (2003). Probability Theory: The Logic of Science. Cambridge University Press. ISBN 978-0521592710.