Section 10.6 is about maximum differential entropy distributions.

[BLANK_AUDIO]

Before we discuss section 10.6, we first

discuss section 2.9 on maximum entropy distributions,

which is the discrete version of section 10.6. We have deliberately

deferred the discussion of section 2.9 until now.

Consider the following maximization problem.

Maximize the entropy H(p), where p is a probability distribution

defined on a countable subset S of the set of real numbers.

The idea is illustrated in the figure.

So what it means is that it is not

necessary for p to be defined for all real numbers.

Rather, we only need to define p on a

countable subset S of the set of real numbers.

We impose the constraints summation x in the support of p

p(x) times r_i(x) is equal to a_i, where i is from 1 up to m.

That is there are a total of m such constraints on the distribution p,

where S_p is the support of p which is a subset of S.

And r_i is a function defined for all x in S.

Note that the summation in equation 1

is simply the expection of random variable r_i of x

with respect to the distribution p.

The most important theorem in this section is theorem 2.50

which gives the form of the p

that maximizes the entropy subject to the constraints.

Let p star of x equals e to the power minus lambda_0 minus

summation i from 1 up to m, lambda_i times r_i(x)

for all x in S,

where lambda_0, lambda_1 up to lambda_m

are chosen such that the constraints in 1 are satisfied.

Then p star maximizes H(p) over all probability

distribution p on S, subject to the constraints in 1.

Note that p star of x, because

of the exponential form is always strictly positive

and so the support of p star is equal to S.

If we let q_i equals e to the power minus lambda_i, then we can

write p star of x equals e to the power minus lambda_0, e to the

power minus lambda_1 times r_1(x) all the way to e to the power minus lambda_m

times r_m(x),

which is equal to q_0 times q_1

to the power of r_1(x), all the way to q_m to the power of r_m(x).

From this form it is clear, that q_0, that is e to power minus lambda_0, is the

normalization constant, because p star of x, summing over all x must be equal to 1.

We now give the sketch of the proof of theorem 2.50.

For the sake of convenience, we are going to use the natural logarithm.

Consider entropy of p star minus entropy of p, where p

is any distribution on S that satisfies the constraints in 1.

This is equal to minus summation x in S

p star of x log p star of x

plus summation x in S_p

p of x log p of x.

We are going to justify that we can replace p

star of x in red by p of x in blue,

and the summation over x in S, where S is in red,

by summation over all x in S_p, where S_p is in blue.

Combining these two summations, we have summation x in

S_p, p(x) log p(x) divided by p star x.

This is equal to the divergence between p and p star,

which is greater than or equal to 0.

This shows that p star is the distribution that maximizes the entropy.

We now fill in the details of the proof.

First, entropy of p star minus entropy of p is equal to this, as we have seen.

Now p star of x is equal to e to the power

minus lambda_0, minus summation i, lambda_i r_i(x).

And so the natural logarithm of p star of x is

equal to minus lambda_0, minus summation i, lambda_i r_i(x).

So we substitute this expression for log p star of x.

Now we are going to split the first summation into two.

First, we have lambda_0 multiplied by summation x in S p star of x.

And for the second summation, which is a double

summation, we first sum over summation i, lambda_i,

and then summation x in S p star of x

multiplied by r_i(x).

Now, summation p star of x over all x in S is just equal to 1.

And summation x in S p star of x r_i(x) is equal to a_i,

because lambda_0, lambda_1, up to lambda_m, are chosen,

such that p star satisfies all the constraints in equation 1.

Now, for this one, we replace it by summation p(x) over all x in S_p.

And for this a_i, we would replace it by summation

p(x) times r_i(x) over all x in S_p

because p satisfies all the m constraints in equation one.

Note that we have already replaced p star of x in red by p(x)

in blue and S in red by S_p in blue.

In the remaining, we just inverse the operations in

the second and the third steps of the proof.

To recombine the first two summations into one, we first sum over x in S_p, p(x).

With this minus sign in place, we have minus lambda_0

minus summation i, lambda_i times r_i(x).

Now, minus lambda_0, minus summation i, lambda_i, times r_i(x)

is equal to the natural logarithm of p star of x.

And so, we have summation x in S_p, p(x) log p(x) divided by

p star of x, which is the divergence between p and p star.

And this is greater than or equal to zero.

This completes the proof of the theorem.

Theorem 2.50 has the following rather subtle corollary.

Let p star be the probability distribution defined on S that we have seen before,

except that lambda_0, lambda_1 up to lambda_m, are now arbitrary constants.

Then p star maximizes the entropy of p over all probability

distribution p defined on S subject to the constraints

summation x in S_p p(x) times r_i(x) is equal to summation

x in S p star of x times r_i(x) for all i between 1 and m.

[BLANK_AUDIO]

The proof goes as follows.

Let summation x in S, p star of x, times r_i(x) be a_i for all i.

[BLANK_AUDIO]

Then, by construction, the parameters lambda_0, lambda_1 up to lambda_m

in p star of x are such that p star satisfies the constraints

summation x in S_p, p(x) times r_i(x) is equal to a_i for all i.

[BLANK_AUDIO]

Then the corollary is implied by theorem 2.50.

[BLANK_AUDIO]

Example 2.52 is an illustration of an application of theorem 2.50.

Let S be finite and let the set of constraints be empty.

Then p star of x is equal to e to

the power of minus lambda_0 which does not depend on x.

Therefore, p star is simply the uniform distribution over S, that

is p star of x is equal to the reciprocal of the size of S for all x in S.

This is consistent with our previous result, that over a

finite alphabet, the entropy is maximized by the uniform distribution.

[BLANK_AUDIO]

The next example is a little bit more elaborate.

Let S be the set of integers 0, 1, 2

so on and so forth.

And let the set of constraints be summation x p(x) times x equal to a

where a is greater than or equal to 0.

That is the mean of the distribution is fixed to be a.

Let q_i equals e to the power minus lambda_i

for i equals zero and one.

Then p star of x is equal to d to the power minus lambda_0

times e to the power minus lambda_1

times x which is equal to q_0 times q_1 to the power x.

Evidently,

p star is a geometric distribution so that q_1 is equal to 1 minus q_0 where q_0 is the normalizing constant.

Thus it remains to determine q_0.

Towards this end, we invoke the constraint in equation one

on p to obtain q_0 equals the reciprocal of

a plus one. This is the only choice for q_0,

such that the mean of the distribution is equal to a.

Let us now return to section

10.6 on maximum differential entropy distributions.

[BLANK_AUDIO]

Consider the maximization problem.

Maximize the differential entropy over all probability density function f,

defined on a subset S of the n-th dimensional Euclidean space

subject to the constraints, integrating r_i(x)f(x)dx

over the support of f equals a_i, for all i from 1 up to m,

where the support of f is a subset of S, and

r_i(x) is some function defined for all x in S.

Note that the integal in equation 1 is simply the expectation of the random variable r_i(x)

with respect to the distribution f.

Theorem 10.41 is the continuous version of Theorem 2.50.

It says that the differential entropy is maximized by f star of x

which has the form e to the power minus lambda_0

minus summation i equals 1 up to m, lambda_i times r_i(x)

where lambda_0, lambda_1 up to lambda_m are

chosen, such that the constraints in equation 1 are satisfied.

[BLANK_AUDIO]

Theorem 10.41 has the following corollary.

Let f star be a pdf defined on S with f

star of x being the same as we have seen before

where lambda_0 lambda_1 up to lambda_m, are arbitrary constants.

Then f star maximizes the differential entropy, over all

density function f defined on S, subject to the constraints

integrating r_i(x), f(x)dx over the

support of f is equal to integrating r_i(x)

f star of x dx over the support S

for all i from 1 up to m.

[BLANK_AUDIO]

Theorem 10.43 says the following.

Let X be a continuous random variable, with the second moment being kappa.

Then the differential entropy of X is upper

bounded by one half log 2 pi e kappa

with equality if and only if X is a

Gaussian random variable with mean 0 and variance kappa.

The proof goes as follows.

We consider maximizing the differential entropy of f subject to the constraint

integrating x square f(x)dx, that is

the expectation of X square equals kappa.

Then by theorem 10.41, f star of x has the form a times e to the power

minus b x square, which is the Gaussian distribution with 0 mean.

[BLANK_AUDIO]

In order to satisfy the second moment constraint, the only choices are a equals

1 over square root 2 pi kappa, and b equals 1 over 2 kappa.

[BLANK_AUDIO]

Next we are going to illustrate an application of corollary 10.42.

We start with a pdf of a Gaussian

random variable, with mean 0 and variance sigma square

and call this density function f star of x, which is equal to 1 over square

root 2 pi sigma square, e to the power minus x square over 2 sigma square.

We ask what are the constraints that f star maximizes the entropy for?

To answer this question, we write f star of x equals e to the

power minus lambda_0, times e to the power minus lambda_1 times x square,

[BLANK_AUDIO]

where lambda_0 is equal to 1 half log 2 pi sigma

square, and lambda_1 is equal to 1 over 2 sigma square.

Then according to Corollary 10.42, f star maximizes the differential entropy,

over all density functions, subject to the second moment equal to sigma square.

[BLANK_AUDIO]

The next theorem says that, for a continuous random variable, with mean

mu and variance sigma square, the

differential entropy is upper bounded by one half

log 2 pi e sigma square, with equality if and only if

X is a Gaussian random variable, with mean mu and variance sigma square.

[BLANK_AUDIO]

The proof goes as follows.

Let X prime equals X minus mu.

Then X prime has 0 mean, and the second

moment of X prime, is equal to the expectation

of the square of X minus mu, which is

equal to the variance of X, that is, sigma square.

Then by theorem 10.14, that is the translation property,

X and X prime have the same differential entropy.

And then by theorem 10.43, the differential entropy of X

prime, is less than or equal to one half log 2 pi e sigma square

because the second moment of x prime, is equal to sigma square.

[BLANK_AUDIO]

Equality holds if and only if X prime

is the Gaussian random variable with mean 0, and

variance sigma square, or X is the Gaussian

random variable with mean mu and variance sigma square.

[BLANK_AUDIO]

The following remark is somewhat subtle.

Theorem 10.43 says that with the constraints

that the second moment is equal to kappa,

the differential entropy is maximized by the

Gaussian distribution with mean 0 and variance kappa.

[BLANK_AUDIO]

If we impose the additional constraint, that the mean is equal to 0, then both

of the variance of X and the second moment of X are equal to kappa.

[BLANK_AUDIO]

By theorem 10.44, the differential entropy is still maximized

by the Gaussian distribution with 0 mean and variance kappa.

[BLANK_AUDIO]

Now we discuss a relation between differential

entropy, and the spread of the distribution.

From theorem 10.44, we have the differential entropy of

a random variable X is less than or equal

to one half log 2 pi e sigma square, where

sigma square is equal to the variance of X.

This upper bound can be written as log sigma plus one half log 2 pi e.

Then, from this inequality, we see that the differential entropy

is at most equal to the logarithm of the standard deviation

which is a measure of the spread of the distribution,

plus a constant, that is one half log 2 pi e.

In particular, as sigma, the standard deviation, tends

to 0, the differential entropy tends to minus infinity.

[BLANK_AUDIO]

The next 2 theorems, are the vector

generalizations of theorem 10.43, and 10.44 respectively.

Let X be a vector of n

continuous random variables, with correlation matrix K tilde.

Then the differential entropy of X is upper bounded by one half log two pi e

to the power n times the determinant of the correlation matrix K tilde

with equality, if and only if X is a Gaussian

vector with mean 0 and covariance matrix K tilde.

[BLANK_AUDIO]

Theorem 10.46 says that, for a random vector with mean nu and

covariance matrix K, the differential entropy is upper bounded by one half log 2 pi e

to the power n, times the determinant of K, with equality if and

only if X is a Gaussian vector with mean mu and covariance matrix K.

[BLANK_AUDIO]

We now prove theorem 10.45.

Define the function r_{ij}(x) to be x_i times x_j, and let

the (i,j)-th element of the matrix K tilde be k tilde ij.

Then the constraints on the pdf of the random vector X,

namely the requirement that the correlation matrix is equal to K

tilde, are equivalent to setting the integral of r_{ij}(x)

f(x)dx over the support of f to k tilde ij.

[BLANK_AUDIO]

It is because r_{ij}(x) is equal to x_i times x_j, and so this

integral is equal to the expectation of X_i times X_j,

that is the correlation between X_i and X_j, and this is for all i,j between 1 and n.

[BLANK_AUDIO]

Now by theorem 10.41, the joint pdf that

maximizes the differential entropy, has the form,

f star of x equals e to the power minus lambda_0,

minus summation over all i and j, lambda_{ij} x_i times x_j,

where x_i times x_j is r_{ij}(x).

[BLANK_AUDIO]

Here, the summation over all i,j, lambda_{ij} times x_i

times x_j can be written as x transpose L times x

[BLANK_AUDIO]

where L is an n by n matrix, with the (i,j)-th element equal to lambda_{ij}.

[BLANK_AUDIO]

Thus, f star is the joint pdf

of a multivariate Gaussian distribution with 0 mean.

[BLANK_AUDIO]

To see this, we only need to compare the form of f

star of x and the pdf of a Gaussian distribution with mean 0.

[BLANK_AUDIO]

Then for all i, j between 1 and n, the covariance between X_i and X_j is

equal to expectation of X_i times X_j, minus

the expectation of X_i times the expectation of X_j,

where the expectation of X_i is equal to 0,

and the expectation of X_j is also equal to 0.

And so, we have the covariance between X_i

and X_j, equals the expectation of X_i times X_j.

Hence the covariance matrix corresponding to the pdf f star is equal to K tilde,

because the expectation of X_i times X_j has been set to k tilde ij.

[BLANK_AUDIO]

Now f star is the joint pdf of a multivariate Gaussian distribution

with 0 mean, and the covariance matrix is equal to K tilde.

Accordingly, lambda_0 and L, in f star of x, have

the unique solution, given by e to the power minus lambda_0

equals one over square root of 2 pi to the

power n, times the square root of the determinant of K tilde,

and L is equal to one half, the inverse of K tilde.

So that f star of X is equal to 1 over square

root of 2 pi to the power n, times the square root

of the determinant of K tilde, times e to the power minus

one half x transpose times the inverse of K tilde, times x,

which is a joint pdf of the Gaussian

distribution with mean 0 and variance matrix K tilde.

Hence, by theorem 10.20, which gives the differential entropy

of a Gaussian distribution, we have proved the upper

bound on the differential entropy of the random vector

X, in terms of the correlation matrix K tilde

with equality, if and only if X is a

Gaussian vector, with mean 0 and covariance matrix K tilde.

Chapter 10 - Section 10.6

Information Theory

Rencontrer les enseignants