Thomas M. Cover, Joy A. Thomas. Elements of information theory
Подождите немного. Документ загружается.
8.2 AEP FOR CONTINUOUS RANDOM VARIABLES 245
8.2 AEP FOR CONTINUOUS RANDOM VARIABLES
One of the important roles of the entropy for discrete random variables
is in the AEP, which states that for a sequence of i.i.d. random variables,
p(X
1
,X
2
,...,X
n
) is close to 2
−nH (X)
with high probability. This enables
us to define the typical set and characterize the behavior of typical sequences.
We can do the same for a continuous random variable.
Theorem 8.2.1 Let X
1
,X
2
,...,X
n
be a sequence of random vari-
ables drawn i.i.d. according to the density f(x).Then
−
1
n
log f(X
1
,X
2
,...,X
n
) → E[−log f(X)] = h(X) in probability.
(8.10)
Proof: The proof follows directly from the weak law of large numbers.
This leads to the following definition of the typical set.
Definition For >0andanyn,wedefinethetypical set A
(n)
with
respect to f(x) as follows:
A
(n)
=
(x
1
,x
2
,...,x
n
) ∈ S
n
:
−
1
n
log f(x
1
,x
2
,...,x
n
) − h(X)
≤
,
(8.11)
where f(x
1
,x
2
,...,x
n
) =
n
i=1
f(x
i
).
The properties of the typical set for continuous random variables par-
allel those for discrete random variables. The analog of the cardinality of
the typical set for the discrete case is the volume of the typical set for
continuous random variables.
Definition The volume Vo l (A) of a set A ⊂
R
n
is defined as
Vo l (A) =
A
dx
1
dx
2
···dx
n
. (8.12)
Theorem 8.2.2 The typical set A
(n)
has the following properties:
1. Pr
A
(n)
> 1 − for n sufficiently large.
2. Vo l
A
(n)
≤ 2
n(h(X)+)
for all n.
3. Vo l
A
(n)
≥ (1 −)2
n(h(X)−)
for n sufficiently large.
246 DIFFERENTIAL ENTROPY
Proof: By Theorem 8.2.1, −
1
n
log f(X
n
) =−
1
n
log f(X
i
) → h(X) in
probability, establishing property 1. Also,
1 =
S
n
f(x
1
,x
2
,...,x
n
)dx
1
dx
2
···dx
n
(8.13)
≥
A
(n)
f(x
1
,x
2
,...,x
n
)dx
1
dx
2
···dx
n
(8.14)
≥
A
(n)
2
−n(h(X)+)
dx
1
dx
2
···dx
n
(8.15)
= 2
−n(h(X)+)
A
(n)
dx
1
dx
2
···dx
n
(8.16)
= 2
−n(h(X)+)
Vo l
A
(n)
. (8.17)
Hence we have property 2. We argue further that the volume of the typical
set is at least this large. If n is sufficiently large so that property 1 is
satisfied, then
1 − ≤
A
(n)
f(x
1
,x
2
,...,x
n
)dx
1
dx
2
···dx
n
(8.18)
≤
A
(n)
2
−n(h(X)−)
dx
1
dx
2
···dx
n
(8.19)
= 2
−n(h(X)−)
A
(n)
dx
1
dx
2
···dx
n
(8.20)
= 2
−n(h(X)−)
Vo l
A
(n)
, (8.21)
establishing property 3. Thus for n sufficiently large, we have
(1 − )2
n(h(X)−)
≤ Vo l (A
(n)
) ≤ 2
n(h(X)+)
. (8.22)
Theorem 8.2.3 The set A
(n)
is the smallest volume set with probability
≥ 1 −, to first order in the exponent.
Proof: Same as in the discrete case.
This theorem indicates that the volume of the smallest set that contains
most of the probability is approximately 2
nh
.Thisisann-dimensional
volume, so the corresponding side length is (2
nh
)
1
n
= 2
h
. This provides
8.3 RELATION OF DIFFERENTIAL ENTROPY TO DISCRETE ENTROPY 247
an interpretation of the differential entropy: It is the logarithm of the
equivalent side length of the smallest set that contains most of the prob-
ability. Hence low entropy implies that the random variable is confined
to a small effective volume and high entropy indicates that the random
variable is widely dispersed.
Note. Just as the entropy is related to the volume of the typical set, there
is a quantity called Fisher information which is related to the surface
area of the typical set. We discuss Fisher information in more detail in
Sections 11.10 and 17.8.
8.3 RELATION OF DIFFERENTIAL ENTROPY TO DISCRETE
ENTROPY
Consider a random variable X with density f(x) illustrated in Figure 8.1.
Suppose that we divide the range of X into bins of length .Letus
assume that the density is continuous within the bins. Then, by the mean
value theorem, there exists a value x
i
within each bin such that
f(x
i
) =
(i+1)
i
f(x)dx. (8.23)
Consider the quantized random variable X
, which is defined by
X
= x
i
if i ≤ X<(i+1). (8.24)
∆
f
(
x
)
x
FIGURE 8.1. Quantization of a continuous random variable.
248 DIFFERENTIAL ENTROPY
Then the probability that X
= x
i
is
p
i
=
(i+1)
i
f(x)dx = f(x
i
). (8.25)
The entropy of the quantized version is
H(X
) =−
∞
−∞
p
i
log p
i
(8.26)
=−
∞
−∞
f(x
i
) log(f (x
i
)) (8.27)
=−
f ( x
i
) log f(x
i
) −
f(x
i
) log (8.28)
=−
f ( x
i
) log f(x
i
) − log , (8.29)
since
f(x
i
) =
f(x)= 1. If f(x)log f(x) is Riemann integrable (a
condition to ensure that the limit is well defined [556]), the first term in
(8.29) approaches the integral of −f(x)log f(x) as → 0 by definition
of Riemann integrability. This proves the following.
Theorem 8.3.1 If the density f(x) of the random variable X is Rie-
mann integrable, then
H(X
) + log → h(f ) = h(X), as → 0. (8.30)
Thus, the entropy of an n-bit quantization of a continuous random vari-
able X is approximately h(X) + n.
Example 8.3.1
1. If X has a uniform distribution on [0, 1] and we let = 2
−n
,
then h = 0, H(X
) = n,andn bits suffice to describe X to n
bit accuracy.
2. If X is uniformly distributed on [0,
1
8
], the first 3 bits to the right
of the decimal point must be 0. To describe X to n-bit accuracy
requires only n − 3 bits, which agrees with h(X) =−3.
3. If X ∼
N(0,σ
2
) with σ
2
= 100, describing X to n bit accuracy
would require on the average n +
1
2
log(2πeσ
2
) = n + 5.37 bits.
8.4 JOINT AND CONDITIONAL DIFFERENTIAL ENTROPY 249
In general, h(X) + n is the number of bits on the average required to
describe X to n-bit accuracy.
The differential entropy of a discrete random variable can be considered
to be −∞. Note that 2
−∞
= 0, agreeing with the idea that the volume of
the support set of a discrete random variable is zero.
8.4 JOINT AND CONDITIONAL DIFFERENTIAL ENTROPY
As in the discrete case, we can extend the definition of differential entropy
of a single random variable to several random variables.
Definition The differential entropy of a set X
1
,X
2
,...,X
n
of random
variables with density f(x
1
,x
2
,...,x
n
) is defined as
h(X
1
,X
2
,...,X
n
) =−
f(x
n
) log f(x
n
)dx
n
. (8.31)
Definition If X, Y have a joint density function f (x, y), we can define
the conditional differential entropy h(X|Y) as
h(X|Y) =−
f (x, y) log f(x|y) dx dy. (8.32)
Since in general f(x|y) = f (x, y)/f (y), we can also write
h(X|Y) = h(X, Y ) − h(Y ). (8.33)
But we must be careful if any of the differential entropies are infinite.
The next entropy evaluation is used frequently in the text.
Theorem 8.4.1 (Entropy of a multivariate normal distribution) Let
X
1
,X
2
,...,X
n
have a multivariate normal distribution with mean µ and
covariance matrix K.Then
h(X
1
,X
2
,...,X
n
) = h(N
n
(µ, K)) =
1
2
log(2πe)
n
|K| bits, (8.34)
where |K| denotes the determinant of K.
250 DIFFERENTIAL ENTROPY
Proof: The probability density function of X
1
,X
2
,...,X
n
is
f(x) =
1
√
2π
n
|K|
1
2
e
−
1
2
(x−µ)
T
K
−1
(x−µ)
. (8.35)
Then
h(f ) =−
f(x)
−
1
2
(x − µ)
T
K
−1
(x − µ) − ln
√
2π
n
|K|
1
2
dx
(8.36)
=
1
2
E
i,j
(X
i
− µ
i
)
K
−1
ij
(X
j
− µ
j
)
+
1
2
ln(2π)
n
|K| (8.37)
=
1
2
E
i,j
(X
i
− µ
i
)(X
j
− µ
j
)
K
−1
ij
+
1
2
ln(2π)
n
|K| (8.38)
=
1
2
i,j
E[(X
j
− µ
j
)(X
i
− µ
i
)]
K
−1
ij
+
1
2
ln(2π)
n
|K| (8.39)
=
1
2
j
i
K
ji
K
−1
ij
+
1
2
ln(2π)
n
|K| (8.40)
=
1
2
j
(KK
−1
)
jj
+
1
2
ln(2π)
n
|K| (8.41)
=
1
2
j
I
jj
+
1
2
ln(2π)
n
|K| (8.42)
=
n
2
+
1
2
ln(2π)
n
|K| (8.43)
=
1
2
ln(2πe)
n
|K| nats (8.44)
=
1
2
log(2πe)
n
|K| bits. (8.45)
8.5 RELATIVE ENTROPY AND MUTUAL INFORMATION
We now extend the definition of two familiar quantities, D(f ||g) and
I(X;Y), to probability densities.
8.5 RELATIVE ENTROPY AND MUTUAL INFORMATION 251
Definition The relative entropy (or Kullback–Leibler distance) D(f ||g)
between two densities f and g is defined by
D(f ||g) =
f log
f
g
. (8.46)
Note that D(f ||g) is finite only if the support set of f is contained in
the support set of g. [Motivated by continuity, we set 0 log
0
0
= 0.]
Definition The mutual information I(X;Y) between two random vari-
ables with joint density f (x,y) is defined as
I(X;Y) =
f (x,y)log
f (x, y)
f(x)f(y)
dx dy. (8.47)
From the definition it is clear that
I(X;Y) = h(X) − h(X|Y) = h(Y ) − h(Y |X) = h(X) + h(Y ) − h(X, Y )
(8.48)
and
I(X;Y) = D(f (x, y)||f (x)f (y)). (8.49)
The properties of D(f ||g) and I(X;Y) are the same as in the dis-
crete case. In particular, the mutual information between two random
variables is the limit of the mutual information between their quantized
versions, since
I(X
;Y
) = H(X
) − H(X
|Y
) (8.50)
≈ h(X) − log − (h(X|Y)− log ) (8.51)
= I(X;Y). (8.52)
More generally, we can define mutual information in terms of finite
partitions of the range of the random variable. Let
X be the range of a
random variable X. A partition
P of X is a finite collection of disjoint
sets P
i
such that ∪
i
P
i
= X. The quantization of X by P (denoted [X]
P
)
is the discrete random variable defined by
Pr([X]
P
= i) = Pr(X ∈ P
i
) =
P
i
dF (x). (8.53)
For two random variables X and Y with partitions
P and Q, we can
calculate the mutual information between the quantized versions of X
and Y using (2.28). Mutual information can now be defined for arbitrary
pairs of random variables as follows:
252 DIFFERENTIAL ENTROPY
Definition The mutual information between two random variables X
and Y is given by
I(X;Y) = sup
P,Q
I([X]
P
;[Y ]
Q
), (8.54)
where the supremum is over all finite partitions
P and Q.
This is the master definition of mutual information that always applies,
even to joint distributions with atoms, densities, and singular parts. More-
over, by continuing to refine the partitions P and Q, one finds a mono-
tonically increasing sequence I([X]
P
;[Y ]
Q
) I .
By arguments similar to (8.52), we can show that this definition of
mutual information is equivalent to (8.47) for random variables that have
a density. For discrete random variables, this definition is equivalent to
the definition of mutual information in (2.28).
Example 8.5.1 (Mutual information between correlated Gaussian ran-
dom variables with correlation ρ)Let(X, Y ) ∼
N(0,K),where
K =
σ
2
ρσ
2
ρσ
2
σ
2
. (8.55)
Then h(X) = h(Y ) =
1
2
log(2πe)σ
2
and h(X, Y ) =
1
2
log(2πe)
2
|K|=
1
2
log(2πe)
2
σ
4
(1 − ρ
2
), and therefore
I(X;Y) = h(X) + h(Y ) − h(X, Y ) =−
1
2
log(1 − ρ
2
). (8.56)
If ρ = 0, X and Y are independent and the mutual information is 0.
If ρ =±1, X and Y are perfectly correlated and the mutual information
is infinite.
8.6 PROPERTIES OF DIFFERENTIAL ENTROPY, RELATIVE
ENTROPY, AND MUTUAL INFORMATION
Theorem 8.6.1
D(f ||g) ≥ 0 (8.57)
with equality iff f = g almost everywhere (a.e.).
Proof: Let S be the support set of f .Then
−D(f ||g) =
S
f log
g
f
(8.58)
≤ log
S
f
g
f
(by Jensen’s inequality) (8.59)
8.6 DIFFERENTIAL ENTROPY, RELATIVE ENTROPY, AND MUTUAL INFORMATION 253
= log
S
g (8.60)
≤ log 1 = 0. (8.61)
We have equality iff we have equality in Jensen’s inequality, which
occurs iff f = g a.e.
Corollary I(X;Y) ≥ 0 with equality iff X and Y are independent.
Corollary h(X|Y) ≤ h(X) with equality iff X and Y are independent.
Theorem 8.6.2 (Chain rule for differential entropy)
h(X
1
,X
2
,...,X
n
) =
n
i=1
h(X
i
|X
1
,X
2
,...,X
i−1
). (8.62)
Proof: Follows directly from the definitions.
Corollary
h(X
1
,X
2
,...,X
n
) ≤
h(X
i
), (8.63)
with equality iff X
1
,X
2
,...,X
n
are independent.
Proof: Follows directly from Theorem 8.6.2 and the corollary to Theo-
rem 8.6.1.
Application (Hadamard’s inequality) If we let X ∼ N(0,K)be a mul-
tivariate normal random variable, calculating the entropy in the above
inequality gives us
|K|≤
n
i=1
K
ii
, (8.64)
which is Hadamard’s inequality. A number of determinant inequalities
can be derived in this fashion from information-theoretic inequalities
(Chapter 17).
Theorem 8.6.3
h(X + c) = h(X). (8.65)
Translation does not change the differential entropy.
Proof: Follows directly from the definition of differential entropy.
254 DIFFERENTIAL ENTROPY
Theorem 8.6.4
h(aX) = h(X) + log |a|. (8.66)
Proof: Let Y = aX.Thenf
Y
(y) =
1
|a|
f
X
(
y
a
),and
h(aX) =−
f
Y
(y) log f
Y
(y) dy (8.67)
=−
1
|a|
f
X
y
a
log
1
|a|
f
X
y
a
dy (8.68)
=−
f
X
(x) log f
X
(x) dx + log |a| (8.69)
= h(X) + log |a|, (8.70)
after a change of variables in the integral.
Similarly, we can prove the following corollary for vector-valued ran-
dom variables.
Corollary
h(AX) = h(X) + log |det(A)|. (8.71)
We now show that the multivariate normal distribution maximizes the
entropy over all distributions with the same covariance.
Theorem 8.6.5 Let the random vector X ∈ R
n
have zero mean and
covariance K = EXX
t
(i.e., K
ij
= EX
i
X
j
, 1 ≤ i, j ≤ n). Then h(X) ≤
1
2
log(2πe)
n
|K|, with equality iff X ∼ N(0,K).
Proof: Let g(x) be any density satisfying
g(x)x
i
x
j
dx = K
ij
for all
i, j .Letφ
K
be the density of a N(0,K)vector as given in (8.35), where we
set µ = 0. Note that log φ
K
(x) is a quadratic form and
x
i
x
j
φ
K
(x)dx =
K
ij
.Then
0 ≤ D(g||φ
K
) (8.72)
=
g log(g/φ
K
) (8.73)
=−h(g) −
g log φ
K
(8.74)