The lectures of this course are based on the first 11 chapters of Prof. Raymond Yeung’s textbook entitled Information Theory and Network Coding (Springer 2008). This book and its predecessor, A First Course in Information Theory (Kluwer 2002, essentially the first edition of the 2008 book), have been adopted by over 60 universities around the world as either a textbook or reference text. At the completion of this course, the student should be able to: 1) Demonstrate knowledge and understanding of the fundamentals of information theory. 2) Appreciate the notion of fundamental limits in communication systems and more generally all systems. 3) Develop deeper understanding of communication systems. 4) Apply the concepts of information theory to various disciplines in information science.
Chapter 10 - Section 10.6
Loading...
From the course by The Chinese University of Hong Kong
Information Theory
8 ratings
Meet the Instructors
Prof. Raymond W. YeungChoh-Ming Li Professor of Information Engineering, and Co-Director, Institute of Network Coding
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.
Explore our Catalog
Join for free and get personalized recommendations, updates and offers.
Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.
© 2018 Coursera Inc. All rights reserved.
